Dimensi Metrik Graf Lintasan dan Graf Lengkap

24
Teori Aplikasi Graf Teori Aplikasi Graf Dimensi Metrik Hasil Operasi Antara Graf Lintasan Dengan Graf Lengkap (P n K m ) Dan Graf Sikel Dengan Graf Lintasan (C n mP 2 ) Oleh: Petrus Fendiyanto (1213201002) Imamatul Ummah (1213201003)

Transcript of Dimensi Metrik Graf Lintasan dan Graf Lengkap

Page 1: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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)

Page 2: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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)).

Page 3: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 4: Dimensi Metrik Graf Lintasan dan Graf 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.

Page 5: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 6: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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 .

Page 7: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 8: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 9: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 10: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 11: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 12: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 13: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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).

Page 14: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 15: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 16: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 17: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 18: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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)

Page 19: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 20: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 21: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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

Page 22: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 23: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.

Page 24: Dimensi Metrik Graf Lintasan dan Graf Lengkap

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.