Perpustakaan Digital ITB

Misalkan G = (V;E) adalah graf sederhana, berhingga dan terhubung. Suatu himpunan D V disebut himpunan dominasi dari G jika untuk setiap titik v 2 V ????D bertetangga dengan suatu titik di D. Kardinalitas terkecil dari himpunan dominasi di G disebut bilangan dominasi dari G. Selanjutnya, representasi suatu titik v 2 V (G) terhadap himpunan R V dinyatakan sebagai vektor jarak titik v tersebut terhadap R. Himpunan R dinamakan himpunan pembeda dari G jika setiap titik di G memiliki representasi yang berbeda terhadap R. Kardinalitas terkecil dari himpunan pembeda di G disebut dimensi metrik. Lebih lanjut, suatu himpunan dominasi yang merupakan himpunan pembeda di G disebut himpunan dominasilokasi- metrik dari G. Kardinalitas terkecil dari himpunan dominasi-lokasi-metrik di G disebut bilangan dominasi-lokasi-metrik dari G. Konsep bilangan dominasi-lokasi-metrik suatu graf terhubung diperkenalkan pertama kali oleh Brigham dkk. (2003). Konsep ini merupakan gabungan konsep bilangan dominasi dan dimensi metrik. Gabungan konsep ini merupakan kajian untuk mencari suatu himpunan yang merupakan himpunan dominasi dan juga merupakan himpunan pembeda. Brigham dkk. (2003) telah dapat menunjukkan hubungan antara bilangan dominasi (G), dimensi metrik (G), dan bilangan dominasi-lokasi-metrik M(G), yaitu maxf (G); (G)g M(G) minf (G) + (G); n ???? 1g. Hasil ini sekaligus memberikan batas bawah dan batas atas dari bilangan dominasi-lokasi-metrik suatu graf. Meskipun telah diketahui batas bawah dan batas atas bilangan dominasi-lokasimetrik sebarang graf, namun penentuan bilangan dominasi-lokasi-metrik suatu graf adalah suatu permasalahan yang sulit. Hal ini disebabkan oleh beragamnya struktur graf. Oleh karena, itu kajian bilangan dominasi-lokasi-metrik dilakukan dengan membatasi pada keluarga graf tertentu atau dengan mengkarakterisasi graf dengan bilangan dominasi-lokasi-metrik tertentu. Sampai saat ini, telah dikarakterisasi semua graf berorde n yang mempunyai bilangan dominasi-lokasi-metrik 1, n ???? 2, dan n ???? 1. Penentuan himpunan dominasi-lokasi-metrik suatu graf tidak bisa terlepas dari pencarian himpunan dominasi dan himpunan pembeda suatu graf. Pada suatu graf, jika suatu himpunan pembeda termuat pada suatu himpunan dominasi minimumnya maka himpunan dominasi minimum tersebut dapat bertindak sebagai himpunan pembedanya. Sebaliknya, jika suatu himpunan dominasi termuat pada suatu himpunan pembeda minimum maka himpunan pembeda minimum tersebut dapat bertindak sebagai himpunan dominasinya. Dengan demikian, untuk graf dengan kondisi ini, dapat dirumuskan bilangan dominasi-lokasi-metrik dari G adalah sama dengan batas bawah, yaitu M(G) = maxf (G); (G)g. Sedangkan jika setiap himpunan dominasi minimum dan setiap himpunan pembeda minimum saling lepas maka bilangan dominasi-lokasi-metrik suatu graf G mencapai batas atas yaitu M(G) = minf (G) + (G); n ???? 1g. Pada disertasi ini dilakukan kajian tentang graf dengan bilangan dominasi-lokasimetrik berada pada batas bawah atau pada batas atas. Selain itu, secara khusus ditentukan bilangan dominasi-lokasi-metrik dari graf k-lintasan, graf hasil operasi korona, dan pohon. Lebih lanjut, juga ditentukan syarat cukup dan syarat perlu dari graf hasil operasi korona dan pohon dengan bilangan dominasi-lokasi-metriknya mencapai batas bawah atau mencapai batas atas. Selain itu, pada disertasi ini dilakukan karakterisasi graf dengan bilangan dominasilokasi- metrik kecil. Pada bagian ini dilakukan karakterisasi graf dengan bilangan dominasi-lokasi-metrik 2, karakterisasi pohon dengan bilangan dominasi-lokasimetrik 3 dan karakterisasi graf unisiklik dengan bilangan dominasi-lokasi-metrik 3. Pada disertasi ini juga dikaji graf dengan bilangan dominasi-lokasi-metrik setengah dari ordenya. Sebagaimana diketahui kondisi antara himpunan pembeda dan himpunan dominasi suatu graf memberikan pengaruh besar pada penentuan himpunan dominasi-lokasi-metrik suatu graf. Dalam hal ini kajian difokuskan pada graf G berorde n pada kelas graf tertentu yang memenuhi M(G) = 1 2n.