Perpustakaan Digital ITB

Misalkan ???? suatu graf dengan himpunan titik ????(????) dan himpunan sisi ????(????). Lintasan yang menghubungkan dua titik ????,?????????(????) adalah barisan titik yang berawal di ???? dan berakhir di ???? tanpa adanya pengulangan titik. Jarak ????(????,????) adalah banyaknya sisi pada lintasan?(????,????) terpendek. Graf sirkulan ????????(????1,????2,…,????????) adalah graf dengan titik-titik ????0,????1,????2,…,?????????1 dan sisi-sisi ????????????????+???????? untuk ????=0,12,…,?????1, ????=1,2,…,???? dengan indeksnya diambil modulo ????. Koordinat suatu titik ?????????(????) terhadap suatu ????={????1,????2,…,????????}, ?????????(????) didefinisikan sebagai suatu vektor ?????tuple, yaitu ????(????|????)=(????(????,????1),????(????,????2),…,????(????,????????)). Jika untuk setiap ????????,?????????????(????),????????? berlaku ????(????????|????)?????(????????|????), maka ???? disebut sebagai himpunan pembeda untuk graf ????. Jika ???? minimum, maka |????| disebut dimensi metrik graf ????, ????(????). Sepasang titik ????,???? memiliki indeks beda ????(????,????)=???? jika terdapat ?????????(????), |????|=???? sehingga ????(????,????)?????(????,????) untuk setiap ?????????. Jika ????(????,????)=2, pasangan titik ????,???? disebut titik kembar. Pada tugas akhir ini, dibahas masalah dimensi metrik untuk graf sirkulan dengan 2 dan 3 generator, ????????(1,????2) dan ????????(1,2,????3), dengan ????2=2,3,????2 dan ????3=3,4,5. Dengan memanfaatkan indeks beda, dibentuk suatu algoritma untuk menentukan himpunan pembeda serta dimensi metrik untuk graf-graf tersebut. Hasil yang diperoleh akan dibandingkan dengan hasil analisis yang sudah ada sebelumnya. Hasil ini ada yang bersesuaian dengan hasil sebelumnya, dan untuk sebagian kasus ada juga yang memperoleh himpunan pembeda yang lebih baik.