Perpustakaan Digital ITB

Misalkan ????(????,????) adalah graf sederhana dan terhubung. Jarak antara dua titik ???? dan ???? di ???? adalah panjang lintasan terpendek antara dua titik ini, dan dilambangkan dengan ????(????,????). Misalkan ????={????1,????2,?,????????} merupakan himpunan bagian dari ????(????). Untuk ?????????, representasi dari titik ???? terhadap ???? adalah ????(????|????)=(????(????,????1),????(????,????2),?,????(????,????????)). Himpunan ???? disebut sebagai himpunan pembeda dari ???? jika semua titik memiliki representasi yang berbeda. Himpunan pembeda dengan kardinalitas terkecil dari graf ???? disebut sebagai basis dari ????. Dimensi metrik dari ???? adalah kardinalitas dari suatu basis dari ???? dan dinotasikan dengan ????????????(????). Graf pohon adalah suatu graf yang terhubung dan tidak memiliki siklus. Graf simetrik kubik adalah graf beraturan berderajat tiga yang bersifat arc-transitif. Foster (1932) melakukan sensus dari semua graf simetrik kubik berorde ???? dengan ?????512. Sensus ini kemudian dilanjutkan oleh Conder dkk. (2006) dan diperoleh daftar lengkap semua graf simetrik kubik dengan orde ?????768. Graf hypercube ???????? adalah graf dengan himpunan semua vektor biner panjang ???? sebagai himpunan titiknya, dan dua titik bertetangga bila kedua vektor tersebut berbeda tepat pada satu posisi (koordinat). Dalam penelitian ini, dirancang algoritma untuk menentukan dimensi metrik dan basis dari graf pohon, graf simetrik kubik, dan graf hypercube. Algoritma graf pohon didasarkan atas himpunan daun dan titik stem yang dimiliki. Sebagai hasilnya, diperoleh semua dimensi metrik dan semua basis yang mungkin untuk setiap pohon ???????? dengan 4??????21. Sedangkan algoritma untuk graf simetrik kubik dan hypercube dikembangkan sebagai algoritma greedy yang mengkonstruksi himpunan pembeda mulai dari himpunan satu elemen dengan cara menambahkannya satu elemen baru hingga semua representasi titiknya berbeda. Sebagai hasilnya, himpunan pembeda optimal lokal diperoleh untuk graf simetrik kubik dan basis serta dimensi metrik untuk semua graf hypercube ???????? dengan 2??????11.