DIMENSI METRIK PADA BEBERAPA GRAF KHUSUS DAN OPERASINYA DENGAN INDUCED SUBGRAPH YANG BEBAS TITIK TERISOLASI

Abstract

Teori graf termasuk dalam cabang ilmu matematika diskrit yang merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Teori graf merupakan salah satu cabang ilmu matematika yang dapat diterapkan pada permasalahan di dunia nyata. Beberapa aplikasi dari teori graf terdapat pada bidang sains, komputasi, dan arsitektur. Salah satu konsep ilmu dalam teori graf yang dapat menyelesaikan permasalahan adalah dimensi metrik. Pada tahun 1975, konsep dimensi metrik diperkenalkan oleh Slater (Chartrand et al). Konsep tersebut muncul dari himpunan pembeda yang dikenal dengan istilah locating set. Himpunan pembedaW didefinisikan sebagai himpunan dari vertices pada suatu graf G sedemikian sehingga untuk setiap vertex di G menghasilkan jarak yang berbeda terhadap setiap vertex di W. Dimensi metrik adalah kardinalitas terkecil dari himpunan pembeda. Himpunan resolving dengan kardinalitas minimum disebut himpunan resolving minimum, dan kardinalitas tersebut menyatakan dimensi metrik dari G serta dinotasikan dengan dim(G) (Harary, 2009). Sebuah himpunan pembeda W pada graf G dikatakan himpunan pembeda tak terisolasi (non-isolated resolving set) jika subgraf (W) diinduksi oleh titik (simpul) tak terisolasi. Kardinalitas minimum dari himpunan pembeda tak terisolasi pada suatu graf dikatakan non-isolated resolving number nr(G) (Chitra dan Arumugam, 2010). Pada penelitian ini menggunakan metode penelitian eksploratif dan terapan. Penelitian eksploratif adalah jenis penelitian yang bertujuan menggali hal-hal yang ingin diketahui oleh peneliti dan hasil penelitian dapat digunakan sebagai dasar penelitian selanjutnya. Penelitian terapan (applied research) merupakan penyelidikan yang hati-hati, sistematik dan terus-menerus terhadap suatu masalah dengan tujuan untuk digunakan dengan segera untuk keperluan tertentu. Penelitian ini bertujuan untuk mencari nilai dimensi metrik dan non-isolated resolving set pada graf khusus. Graf yang digunakan adalah graf kipas Fn, amalgamasi graf kipas amal(Fn; v = A;m), joint graf lintasan dan graf lingkaran Pn + Cm, graf parasut PCn, amalgamasi graf parasut amal(PCn; v = A;m), graf power Pn Cm, sakel graf kipas shack(Fn; v = 1;m), sakel graf parasut shack(PCn; v = 1;m), sehingga pada penelitian ini dihasilkan 8 teorema, antara lain: 1. Teorema 4.1 Untuk n ¸ 7, nilai dimensi metrik dan non-isolated resolving set graf kipas Fn adalah dim(Fn) = dn¡2 2 e dan nr(Fn) = dn 2 e; 2. Teorema 4.2 Untuk n ¸ 5, nilai dimensi metrik dan non-isolated resolving set Graf sakel parasut shack(PCn; v;m) adalah dim(shack(PCn; v;m)) = (bn 2 cm) dan nr(shack(PCn; v;m)) = (bn 2 cm) + m; 3. Teorema 4.3 Untuk n ¸ 6, nilai dimensi metrik dan non-isolated resolving set amalgamasi graf kipas amal(Fn; v = A;m) adalah: nr(amal(Fn; v = A;m)) = 8< : nm 2 ; untuk n = genap nm¡m 2 + 1; untuk n = ganjil; 4. Teorema 4.4 Untuk n ¸ 2 dan m ¸ 7, nilai dimensi metrik dan non-isolated resolving set graf joint Pn+Cm adalah dim(Pn+Cm) = bn 2 c + bm¡1 2 c dan nr(Pn+ Cm) = bn 2 c + bm¡1 2 c; 5. Teorema 4.5 Untuk n ¸ 5, nilai dimensi metrik dan non-isolated resolving set graf kipas Shack(Fn; v;m) adalah: nr(Shack(Fn; v;m)) = 8< : nm 2 + 1; untuk n = genap nm¡3m 2 + 1 + m; untuk n = ganjil; 6. Teorema 4.6 Untuk n ¸ 7, nilai dimensi metrik dan non-isolated resolving set graf parasut PCn adalah dim(PCn) = dn¡2 2 e dan nr(PCn) = dn 2 e; 7. Teorema 4.7 Untuk n ¸ 7, nilai dimensi metrik dan non-isolated resolving set graf amalgamasi parasut amal(PCn; v; n) adalah: nr(amal(PCn; v = A;m)) = 8< : nm 2 ; untuk n = genap nm¡m 2 + 1; untuk n = ganjil; 8. Teorema 4.8 Untuk n ¸ 4 dan m ¸ 6, nilai dimensi metrik dan non-isolated resolving set graf power lintasan dengan lingkaran Pn Cm adalah dim(Pn Cm) = 2n¡3 dan nr(Pn Cm) = 2n ¡ 3.