dimensi metrik graf lintasan dan graf lengkap

Click here to load reader

Post on 26-Jul-2015

296 views

Category:

Education

7 download

Embed Size (px)

TRANSCRIPT

1. Teori Aplikasi Graf Teori Aplikasi Graf Dimensi Metrik Hasil Operasi Antara Graf Lintasan Dengan Graf Lengkap (Pn Km) Dan Graf Sikel Dengan Graf Lintasan (Cn mP2) Oleh: Petrus Fendiyanto (1213201002) Imamatul Ummah (1213201003) 2. Teori Aplikasi Graf Pendahuluan Pendahuluan Graf merupakan pasangan (V , E), dengan V adalah himpunan simpul tak kosong dan E adalah himpunan sisi, yaitu pasangan simpul dari V . Graf biasa dinotasikan dengan G. Setiap sisi menghubungkan tepat dua simpul, dan setiap simpul dapat memiliki banyak sisi yang menghubungkan dengan simpul yang lainnya. Graf yang dibahas dalam paper ini adalah: Graf Lintasan (Pn) Graf Sikel (Cn) Graf Lengkap (Kn) Dimensi metrik (dim(G)) adalah kardinalitas minimum dari semua himpunan pembeda pada G. Misalkan u dan v adalah dua simpul pada graf terhubung G maka jarak dari u ke v adalah panjang lintasan terpendek antara u dan v pada G (d(u, v)). 3. Teori Aplikasi Graf Pendahuluan Beberapa paper yang mengkaji dan membahas mengenai dimensi metrik pada Graf Lintasan (Pn), Graf Sikel (Cn), dan Graf Lengkap (Kn): Johanes (2009) melakukan penelitian tentang dimensi metrik dari pengembangan graf kincir dengan pola K1 + mKn. Hindayani (2011) mengembangkan dan mengkaji penelitian pada dimensi metrik dengan graf Kr + mKs Septiana dan Budi (2013) mengkaji penelitian dimensi merik pada graf lintasan, graf lengkap, graf sikel, graf bintang, dan graf bipartit lengkap 4. Teori Aplikasi Graf Pendahuluan Contoh 1 Dipilih W1 = {v1}, representasi setiap simpul pada G terhadap 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 G terhadap 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 G terhadap 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). Karena u = v dan r(u|W3) = r(v|W3), maka dim(G) = 3. 5. Teori Aplikasi Graf Pendahuluan Operasi korona pada dua buah graf G dan graf H dinotasikan dengan G H, dideniskan sebagai graf yang diperoleh dari salinan psimpul graf G dan p salinan H1, H2, , Hp dari H, yang kemudian bergabung dengan i simpul dari G untuk setiap simpul di Hi . Contoh 6. Teori Aplikasi Graf Pendahuluan Teorema-teorema yang berkaitan dengan yang di bahas dalam paper ini antara lain: 1 Teorema 1.1 (Chartrand, Eroh, Johnson, dan Oellermann, 2000) Misalkan G adalah graf terhubung dengan diameter k dan order n 2, dimana k < n maka berlaku f (n, k) dim(G) n k. 2 Teorema 1.2 (Chartrand dkk, 2000) Misalkan G adalah sebuah 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 jika G = Kr,s, (r, s 1), G = Kr + Ks, (r 1, s 2) atau G = 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 satu dari vertex u atau v harus menjadi dim W . 7. 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} dan graf lengkap Km dengan himpunan simpul V (Km) = {v1, v2, , vm}. Kontruksi dimensi metrik antara Dimensi Metrik graf Pn 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 8. 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) = 4 Hasil operasi korona antara graf lintasan order 1 (P1) dengan graf lengkap (Km) akan menghasilkan graf baru berupa graf lengkap dengan order m + 1. 9. 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. 10. 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. 11. Teori Aplikasi Graf Dimensi Metrik graf Pn Km Misalkan W = {v1,1, v2,1, v1,2, v2,2}, maka representasi tiap simpul: 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 12. 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 dan Km graf lengkap order m, maka dim(Pn Km) = n(m 1) dengan n 2, m 2. 13. Teori Aplikasi Graf Dimensi Metrik graf Pn Km Bukti: Himpunan simpul dalam graf korona Pn Km adalah V (Pn Km) = V (Pn ivPn V (Km), dengan himpuan simpul V (Pn) = {u1, u2, , un} dan himpunan simpul V (Km) = {v1,i , v2,i , v3,i , , vm,i }. Sehingga V (Pn Km = {i {v1,i , v2,i , v3,i , , vm,i }} dengan 1 i n. Jika untuk setiap simpul va, vb Km dan simpul ui Pn maka diketahui bahwa d(va, vi ) = d(vb, vi ) = 1. Sehingga himpunan pembeda merupakan simpul-simpul dari graf lengkap Km, untuk itu diperlukan sebanyak m 1 simpul sebagai himpunan pembeda. Terdapat sejumlah n subgraf Km,i dalam graf Pn Km, maka kardinalitas minimum himpunan pembeda graf Pn Km adalah n(m 1) atau dim(Pn Km) n(m 1). Apabila direduksi simpul v1 mengakibatkan r(v1|W ) = r(vm|W ), sehingga n(m 1) dim(Pn Km) n(m 1). Dengan demikian dim(Pn Km) = n(m 1). 14. 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} dan graf lintasan dengan orde 2 disebut P2 dengan himpunan simpul V (P2) = {a1, b1}. a. C1 2P2 Batas atas Jika W = {a1,1, a1,2} maka representasi dari tiap simpulnya 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) 2 15. Teori Aplikasi Graf Dimensi Metrik graf Cn mP2 Batas bawah jika 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 bawah dim (C1 2P2) 2. Sehingga dim(C1 2P2) = 2 b. C2 P2 Batas atas Jika W = {a1,1, a2,1} maka representasi dari tiap simpulnya 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) 2 16. Teori Aplikasi Graf Dimensi Metrik graf Cn mP2 Batas bawah jika 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 17. Teori Aplikasi Graf Dimensi Metrik graf Cn mP2 Batas atas Jika W = {a1,1, a1,2, a2,1, a2,2} maka representasi dari tiap simpulnya 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) 4 Batas bawah jika W = {a1,1, a1,2, a2,1} maka r(a2,2|W ) = r(b2,2|W ) sehingga W bukan resolving set, batas bawah dim(C2 2P2) 4. Sehingga dim(C2 P2) = 4. 18. Teori Aplikasi Graf Dimensi Metrik graf Cn mP2 d. C3 2P2 Batas atas Jika W = {a1,1, a1,2, a2,1, a2,2, a3,1, a3,2} maka representasi dari tiap 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) 19. 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 atas dim(C3 2P2) 6 Batas bawah jika W = {a1,1, a1,2, a2,1, a2,2, a3,1} maka r(a3,2|W ) = r(b3,2|W ) sehingga W bukan resolving set, batas bawah dim(C3 2P2) 6. Sehingga dim(C3 2P2) = 6. 20. 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. 21. Teori Aplikasi Graf Dimensi Metrik graf Cn mP2 Bukti: Batas atas Menurut teorema 1.3 maka setiap simpul dari P2 diambil salah satu simpulnya untuk menjadi himpunan terurut dari W . Misal W = {a1,1, a1,2, a1,3, , an,m} untuk m 2, maka diperoleh pasangan k-tuple dengan jarak terpendek simpul ke-n yaitu n 2 + 1, untuk n bilangan genap 4 dan n + 1 2 untuk n bilangan ganjil 3. Batas bawah Jika kardinalitas |W | = nm 1, maka bukan resolving set. Karena pasti ditemukan sedikitnya dua titik dengan representasi yang sama. Misal W = {a1,1, a1,2, a1,3, , an,m1} maka r(anm|W ) = r(bnm|W ). Jelas bahwa W bukan resolving set dari graf Cn mP2. Jadi batas bawah dari dimCn mP2 adalah |W | nm atau dimCn mP2 nm 22. Teori Aplikasi Graf Kesimpulan Kesimpulan Berdasarkan pembahasan yang telah dipaparkan dapat diambil kesimpulan sebagai berikut: a. Jika G adalah graf hasil Pn Km dengan n 2, m 2, maka dim(G) = n(m 1). b. Jika G adalah graf hasil Cn mP2 dengan n, m N, m 2, maka dim(G) = nm. 23. Teori Aplikasi Graf Daftar Pustaka Darmaji. (2011). Dimensi Partisi Graf Multipartit dan Graf Hasil Korona Dua Graf Terhubung. Disertasi, Program Studi Matematika ITB: Bandung. Hindayani. 2011. Dimensi Metrik Graph Kr + mKs. Jurusan Matematika