Perpustakaan Digital ITB

Misalkan G(V;E) adalah suatu graf terhubung. Dimensi metrik dari G adalah kardinalitas dari suatu himpunan bagian terkecil S dari V (G) sedemikian sehingga semua titik mempunyai representasi yang berbeda terhadap S: Dalam hal ini, representasi dari suatu titik dinyatakan oleh jarak titik tersebut ke semua titik pada S: Bilangan kromatik lokasi dari G didefinisikan sebagai kardinalitas dari suatu partisi minimum dari himpunan titik V (G) sedemikian sehingga semua titik mempunyai koordinat yang berbeda terhadap partisi tersebut dan setiap dua titik yang bertetangga di G berada dalam kelas partisi yang berbeda. Dalam hal ini, koordinat titik dinyatakan oleh jarak titik tersebut ke semua kelas partisi. Penentuan dimensi metrik untuk sebarang graf merupakan permasalahan NPcomplete. Karena itu, pendekatan secara heuristics banyak dikembangkan untuk menentukan bilangan tersebut. Selain itu, banyak kajian penentuan dimensi metrik dan bilangan kromatik lokasi graf yang dilakukan dengan membatasinya pada kelas-kelas graf tertentu, seperti kelas graf lintasan, siklus, pohon tertentu dan sebagainya. Studi karaketerisasi dari graf yang mempunyai dimensi metrik atau bilangan kromatik lokasi tertentu juga telah dilakukan. Namun, hasilnya masih sangat sedikit dan belum memuaskan. Pada disertasi ini dikaji tentang dimensi metrik dan bilangan kromatik lokasi untuk graf Halin. Graf Halin adalah graf planar yang dibentuk dari suatu gambar planar graf pohon, yang mempunyai paling sedikit empat titik dan tanpa titik berderajat dua, dengan menghubungkan semua titik berderajat satu pada pohon tersebut sedemikian sehingga membentuk suatu siklus tanpa mengubah gambar planar pohonnya. Penentuan dimensi metrik untuk graf planar juga merupakan permasalahan NP-complete. Graf Halin memiliki banyak keistimewaan. Graf Halin merupakan graf 3-terhubung dan 3-terhubung sisi minimal. Setiap graf Halin merupakan graf Hamilton dan setiap sisinya termasuk ke dalam suatu siklus Hamilton. Lebih jauh, sebarang graf Halin masih tetap Hamilton setelah dihapus satu titiknya. Lebih kuat lagi, setiap graf Halin hampir pansiklik, bahkan setelah dikontraksi satu sisinya. Setiap graf Halin memiliki treewidth 3. Oleh karena itu, banyak masalah optimasi graf yang i NP-lengkap untuk sebarang graf planar, dapat diselesaikan dalam waktu linear pada graf Halin. Dalam disertasi ini, akan ditunjukkan bahwa dimensi metrik dari suatu graf Halin terbatas di atas oleh jumlah dari dimensi metrik semua subgraf kipas penyusunnya. Selain itu, basis dari graf Halin tersebut dapat dibentuk oleh basis dari graf-graf kipas yang berukuran lebih besar dari tujuh. Dalam disertasi ini, juga diberikan dimensi metrik graf Halin yang dibentuk dari pohon tertentu, seperti graf bintang ganda, graf amalgamasi bintang, dan graf ulat. Lebih jauh, juga diturunkan hubungan antara dimensi metrik graf Halin dengan dimensi metrik graf hasil subdivisinya. Pembahasan serupa juga dilakukan untuk bilangan kromatik lokasi. Sebagai bagian dari hasil utama, diperoleh batas atas dari bilangan kromatik lokasi untuk graf Halin sebarang dengan mengkonstruksi suatu pewarnaan lokasi pada graf Halin tersebut sedemikian sehingga terdapat satu warna tunggal pada setiap subgraf kipasnya. Selain itu, bilangan kromatik lokasi graf Halin terbatas di bawah oleh bilangan kromatik lokasi dari subgraf kipas terbesarnya. Dalam disertasi ini, juga diberikan bilangan kromatik lokasi graf Halin yang dibentuk dari pohon tertentu, yaitu graf bintang ganda dan graf ulat. Selain itu, dikaji juga bilangan kromatik lokasi dari graf Halin dengan banyak muka dalam tertentu. Lebih jauh, juga diberikan hubungan antara bilangan kromatik lokasi suatu graf dengan bilangan kromatik lokasi graf hasil subdivisinya.