Teori Aplikasi Graf
Teori Aplikasi Graf
Dimensi Metrik Hasil Operasi Antara Graf Lintasan DenganGraf Lengkap (Pn � Km) Dan Graf Sikel Dengan Graf Lintasan
(Cn �mP2)
Oleh:Petrus Fendiyanto (1213201002)Imamatul Ummah (1213201003)
Teori Aplikasi Graf
Pendahuluan
Pendahuluan
Graf merupakan pasangan (V ,E ), dengan V adalah himpunansimpul tak kosong dan E adalah himpunan sisi, yaitu pasangansimpul dari V . Graf biasa dinotasikan dengan G . Setiap sisimenghubungkan tepat dua simpul, dan setiap simpul dapatmemiliki banyak sisi yang menghubungkan dengan simpul yanglainnya. Graf yang dibahas dalam paper ini adalah:
Graf Lintasan (Pn)
Graf Sikel (Cn)
Graf Lengkap (Kn)
Dimensi metrik (dim(G )) adalah kardinalitas minimum dari semuahimpunan pembeda pada G . Misalkan u dan v adalah dua simpulpada graf terhubung G maka jarak dari u ke v adalah panjanglintasan terpendek antara u dan v pada G (d(u, v)).
Teori Aplikasi Graf
Pendahuluan
Beberapa paper yang mengkaji dan membahas mengenai dimensimetrik pada Graf Lintasan (Pn), Graf Sikel (Cn), dan Graf Lengkap(Kn):
Johanes (2009) melakukan penelitian tentang dimensi metrikdari pengembangan graf kincir dengan pola K1 + mKn.
Hindayani (2011) mengembangkan dan mengkaji penelitianpada dimensi metrik dengan graf Kr + mKs
Septiana dan Budi (2013) mengkaji penelitian dimensi merikpada graf lintasan, graf lengkap, graf sikel, graf bintang, dangraf bipartit lengkap
Teori Aplikasi Graf
Pendahuluan
Contoh
1 Dipilih W1 = {v1}, representasi setiap simpul pada Gterhadap W1 adalah r(v1|W1) = (0), r(v2|W1) =(1), r(v3|W1) = (1), r(v4|W1) = (1).
2 Dipilih W2 = {v1, v2}, representasi setiap simpul pada Gterhadap W2 adalah r(v1|W2) = (0, 1), r(v2|W2) =(1, 0), r(v3|W2) = (1, 1), r(v4|W2) = (1, 1).
3 Dipilih W3 = {v1, v2, v3}, representasi setiap simpul pada Gterhadap W3 adalah r(v1|W3) = (0, 1, 1), r(v2|W3) =(1, 0, 1), r(v3|W3) = (1, 1, 0), r(v4|W3) = (1, 1, 0). Karenau 6= v dan r(u|W3) 6= r(v |W3), maka dim(G ) = 3.
Teori Aplikasi Graf
Pendahuluan
Operasi korona pada dua buah graf G dan graf H dinotasikandengan G � H, didefiniskan sebagai graf yang diperoleh darisalinan p−simpul graf G dan p salinan H1,H2, · · · ,Hp dari H,yang kemudian bergabung dengan i− simpul dari G untuk setiapsimpul di Hi .Contoh
Teori Aplikasi Graf
Pendahuluan
Teorema-teorema yang berkaitan dengan yang di bahas dalampaper ini antara lain:
1 Teorema 1.1 (Chartrand, Eroh, Johnson, dan Oellermann,2000) Misalkan G adalah graf terhubung dengan diameter kdan order n > 2, dimana k < n maka berlakuf (n, k) 6 dim(G ) 6 n − k .
2 Teorema 1.2 (Chartrand dkk, 2000) Misalkan G adalahsebuah graf terhubung dengan order n > 2.
dim(G ) = 1 jika dan hanya jika G = Pn.dim(G ) = n − 1 jika dan hanya jika G = Kn.Untuk n > 3, dim(Cn) = 2.Untuk n > 4, dim(G ) = n − 2 jika dan hanya jikaG = Kr ,s , (r , s > 1),G = Kr + Ks , (r > 1, s > 2) atauG = Kr + (K1 ∪ Ks).
3 Teorema 1.3 (Chartrand dkk, 2000) Jika u, v ∈ V (G ),d(u, x) = d(v , x) dan x ∈ V (G )− {u, v} maka salah satudari vertex u atau v harus menjadi dim W .
Teori Aplikasi Graf
Dimensi Metrik graf Pn � Km
Dimensi Metrik Hasil Korona Graf Lintasan dan Graf Lengkap
Graf Pn dengan himpunan simpul V (Pn) = {u1, u2, · · · , un} dangraf lengkap Km dengan himpunan simpul V (Km) = {v1, v2, · · · ,vm}. Kontruksi dimensi metrik antara Dimensi Metrik grafPn � Km dengan n = 1
a. P1 � K1
Graf P1 � K1 = P2, sehingga dim(P1 � K1) = dim(P2) = 1.
b. P1 � K2
dim(P1 � K2) = dim(K3) = 2
Teori Aplikasi Graf
Dimensi Metrik graf Pn � Km
c. P1 � K3
dim(P1 � K3) = dim(K4) = 3
d. P1 � K4
dim(P1 � K4) = dim(K5) = 4Hasil operasi korona antara graf lintasan order 1 (P1) dengangraf lengkap (Km) akan menghasilkan graf baru berupa graflengkap dengan order m + 1.
Teori Aplikasi Graf
Dimensi Metrik graf Pn � Km
e. P2 � K1
Graf P2 � K1= P4, sehingga dim(P4) = 1
f. P2 � K2
Diambil W = {v1,1, v2,1}, maka representasi tiap simpulnya:
r(u1|W ) = (1, 2) r(u2|W ) = (2, 1)
r(v1,2|W ) = (1, 3) r(v2,2|W ) = (3, 1)
Sehingga dim(P2 � K2)=2.
Teori Aplikasi Graf
Dimensi Metrik graf Pn � Km
g. P2 � K3
Diambil W = {v1,1, v2,1}, maka representasi tiap simpulnya:
r(u1|W ) = (1, 2) r(u2|W ) = (2, 1) r(v1,2|W ) = (1, 3)
r(v2,2|W ) = (3, 1) r(v1,3|W ) = (1, 3) r(v2,3|W ) = (3, 1)
W = {v1,1, v2,1} bukan himpunan pembeda.Misalkan W = {v1,1, u1, v2,1}, maka representasi tiap simpul:
r(u2|W ) = (2, 1, 1) r(v2,2|W ) = (3, 2, 1) r(v1,3|W ) = (1, 1, 3)
r(v1,2|W ) = (1, 1, 3) r(v2,3|W ) = (3, 2, 1)
Sehingga W = {v1,1, u1, v2,1} bukan himpunan pembeda.
Teori Aplikasi Graf
Dimensi Metrik graf Pn � Km
Misalkan W = {v1,1, v2,1, v1,2, v2,2}, maka representasi tiapsimpul:
r(u1|W ) = (1, 1, 2, 2) r(v1,3|W ) = (1, 1, 3, 3)
r(u2|W ) = (2, 2, 1, 1) r(v2,3|W ) = (3, 3, 1, 1)
Representasi tiap simpul berbeda, maka dim(P2 � K3) = 4.
Bentuk Umum dari graf Pn � Km
Teori Aplikasi Graf
Dimensi Metrik graf Pn � Km
Pola bilangan dimensi metrik graf Pn � Km
Teorema 2.1 Misalkan Pn adalah graf lintasan dengan order n danKm graf lengkap order m, maka
dim(Pn � Km) = n(m − 1)
dengan n > 2,m > 2.
Teori Aplikasi Graf
Dimensi Metrik graf Pn � Km
Bukti:Himpunan simpul dalam graf korona Pn � Km adalahV (Pn � Km) = V (Pn
⋃∪i∈vPnV (Km), dengan himpuan simpul
V (Pn) = {u1, u2, · · · , un} dan himpunan simpulV (Km) = {v1,i , v2,i , v3,i , · · · , vm,i}. SehinggaV (Pn � Km = {∪i
⋃{v1,i , v2,i , v3,i , · · · , vm,i}} dengan 1 6 i 6 n.
Jika untuk setiap simpul va, vb ∈ Km dan simpul ui ∈ Pn makadiketahui bahwa d(va, vi ) = d(vb, vi ) = 1. Sehingga himpunanpembeda merupakan simpul-simpul dari graf lengkap Km, untuk itudiperlukan sebanyak m − 1 simpul sebagai himpunan pembeda.Terdapat sejumlah n subgraf Km,i dalam graf Pn � Km, makakardinalitas minimum himpunan pembeda graf Pn � Km adalahn(m − 1) atau dim(Pn � Km) 6 n(m − 1). Apabila direduksisimpul v1 mengakibatkan r(v1|W ) = r(vm|W ), sehinggan(m − 1) 6 dim(Pn � Km) 6 n(m − 1). Dengan demikiandim(Pn � Km) = n(m − 1).
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
Dimensi Metrik Hasil Korona Graf Sikel dan Graf Lintasan
Graf Cn dengan himpunan simpul V (Cn) = {v1, v2, · · · , vn} dangraf lintasan dengan orde 2 disebut P2 dengan himpunan simpulV (P2) = {a1, b1}.
a. C1 � 2P2
Batas atas Jika W = {a1,1, a1,2} maka representasi dari tiapsimpulnya
r(v1|W ) = (1, 1) r(a1,1|W ) = (0, 2) r(b1,1|W ) = (1, 2)
r(a1,2|W ) = (2, 0) r(b1,2|W ) = (2, 1)
batas atas dim(C1 � 2P2) 6 2
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
Batas bawahjika W = {v1} maka r(a1,1|W ) = r(b1,1|W ) = r(a1,2|W ) =r(b1,2|W ), sehingga W bukan resolving set. Jadi batas bawahdim (C1 � 2P2) > 2.
Sehingga dim(C1 � 2P2) = 2
b. C2 � P2
Batas atas Jika W = {a1,1, a2,1} maka representasi dari tiapsimpulnya
r(v1|W ) = (1, 2) r(b1,3|W ) = (1, 3) r(a1,1|W ) = (0, 3)
r(v2|W ) = (2, 1) r(b2,1|W ) = (3, 1) r(a2,1|W ) = (3, 0)
batas atas dim(C2 � P2) 6 2
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
Batas bawahjika W = {v1} maka r(a1,1|W ) = r(b1,1|W ) = r(v2|W ) =dan r(a2,1|W ) = r(b2,1|W ), sehingga W bukan resolving set.Jadi batas bawah dim (C2 � P2) > 2.
Sehingga dim(C2 � P2) = 2
c. C2 � 2P2
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
Batas atasJika W = {a1,1, a1,2, a2,1, a2,2} maka representasi dari tiapsimpulnya
r(v1|W ) = (1, 1, 2, 2) r(b1,1|W ) = (1, 2, 3, 3)
r(v2|W ) = (2, 2, 1, 1) r(b1,2|W ) = (2, 1, 3, 3)
r(a2,1|W ) = (3, 3, 0, 2) r(b2,1|W ) = (3, 3, 1, 2)
r(a2,2|W ) = (3, 3, 2, 0) r(b2,2|W ) = (3, 3, 2, 1)
r(a1,1|W ) = (0, 2, 3, 3) r(a1,2|W ) = (2, 0, 3, 3)
batas atas dim(C2 � 2P2) 6 4
Batas bawahjika W = {a1,1, a1,2, a2,1} maka r(a2,2|W ) = r(b2,2|W )sehingga W bukan resolving set, batas bawahdim(C2 � 2P2) > 4.
Sehingga dim(C2 � P2) = 4.
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
d. C3 � 2P2
Batas atasJika W = {a1,1, a1,2, a2,1, a2,2, a3,1, a3,2} maka representasi daritiap simpulnya
r(v1|W ) = (1, 1, 2, 2, 2, 2) r(b2,1|W ) = (3, 3, 1, 2, 3, 3)
r(v2|W ) = (2, 2, 1, 1, 2, 2) r(a2,2|W ) = (3, 3, 2, 0, 3, 3)
r(v3|W ) = (2, 2, 2, 2, 1, 1) r(b2,2|W ) = (3, 3, 2, 1, 3, 3)
r(a1,1|W ) = (0, 2, 3, 3, 3, 3) r(a3,1|W ) = (3, 3, 3, 3, 0, 2)
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
r(b1,1|W ) = (1, 2, 3, 3, 3, 3) r(b3,1|W ) = (3, 3, 3, 3, 1, 2)
r(a1,2|W ) = (2, 0, 3, 3, 3, 3) r(a3,2|W ) = (3, 3, 3, 3, 2, 0)
r(b1,2|W ) = (2, 1, 3, 3, 3, 3) r(b3,2|W ) = (3, 3, 3, 3, 2, 1)
r(a1,1|W ) = (0, 2, 3, 3, 3, 3)
Karena W merupakan resolving set, maka batas atasdim(C3 � 2P2) 6 6
Batas bawahjika W = {a1,1, a1,2, a2,1, a2,2, a3,1} makar(a3,2|W ) = r(b3,2|W ) sehingga W bukan resolving set, batasbawah dim(C3 � 2P2) > 6.
Sehingga dim(C3 � 2P2) = 6.
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
e. Cn �mP2
Teorema 3.1 Misalkan Cn adalah graf sikel dengan order n dan P2
graf lintasan order 2, maka
dim(Cn �mP2) = nm
dengan n,m ∈ N dan m > 2.
Teori Aplikasi Graf
Dimensi Metrik graf Cn � mP2
Bukti:
Batas atasMenurut teorema 1.3 maka setiap simpul dari P2 diambilsalah satu simpulnya untuk menjadi himpunan terurut dari W .Misal W = {a1,1, a1,2, a1,3, · · · , an,m} untuk m > 2, makadiperoleh pasangan k-tuple dengan jarak terpendek simpul
ke-n yaitun
2+ 1, untuk n bilangan genap > 4 dan
n + 1
2untuk n bilangan ganjil > 3.Batas bawahJika kardinalitas |W | = nm − 1, maka bukan resolving set.Karena pasti ditemukan sedikitnya dua titik denganrepresentasi yang sama. MisalW = {a1,1, a1,2, a1,3, · · · , an,m−1} makar(anm|W ) = r(bnm|W ). Jelas bahwa W bukan resolving setdari graf Cn �mP2.Jadi batas bawah dari dimCn �mP2 adalah |W | > nm ataudimCn �mP2 > nm
Teori Aplikasi Graf
Kesimpulan
Kesimpulan
Berdasarkan pembahasan yang telah dipaparkan dapat diambilkesimpulan sebagai berikut:
a. Jika G adalah graf hasil Pn � Km dengan n > 2,m > 2, makadim(G ) = n(m − 1).
b. Jika G adalah graf hasil Cn �mP2 dengan n,m ∈ N,m > 2,maka dim(G ) = nm.
Teori Aplikasi Graf
Daftar Pustaka
Darmaji. (2011). Dimensi Partisi Graf Multipartit dan GrafHasil Korona Dua Graf Terhubung. Disertasi, Program StudiMatematika ITB: Bandung.
Hindayani. 2011. Dimensi Metrik Graph Kr + mKs . JurusanMatematika UIN Maulana Malik Ibrahim: Malang.
Johanes, P. 2009. Dimensi Metrik Pada Pengembangan GraphKincir Dengan Pola K1 + mKn. Tugas Akhir, JurusanMatematika ITS: Surabaya.
Septiana dan Budi. 2013. Dimensi Metrik Pada Graf Lintasan,Graf Komplit, Graf Sikel, Graf Bintang, dan Graf BipartitKomplit. Jurusan Matematika Universitas Negeri Surabaya.
H. Iswadi, E. T Baskoro, R, Simanjuntak, A.N.M. Salman.2012. The Metric Dimention of Graph With Pendant Edge.Faculty of Mathematic and Natural Science. ITB: Bandung.
Teori Aplikasi Graf
Daftar Pustaka
G. Chartrand, Linda Eroh, Mark A. Johnson, O. R Oellermann,2000. Resolvability in Grapgh and The Metric Dimension of aGraph. Discrete Applied Mathematics 105, 99-113.
G. Chartrand, Erwin D, Johns G, dan Zhang P. 2003.Boundary vertices in Graph. Discrete Mathematics 263, 25-34.