Perpustakaan Digital ITB

Suatu graf ????=(????????,????????) terdiri dari dua himpunan hingga, ???????? adalah himpunan tak kosong yang anggotanya disebut dengan titik dan ???????? adalah himpunan yang anggotanya disebut dengan sisi, yaitu himpunan pasangan tak terurut dari anggota ????????. Jika ????????????? menghubungkan titik ???????? dan ???????? maka bisa ditulis ????=???????????????? dan ???????? dan ???????? dikatakan saling bertetangga. Misalkan ????=|????????| dan ????(????) adalah himpunan titik yang bertetangga dengan titik ????. Suatu graf memiliki pelabelan jarak ajaib jika terdapat konstanta ajaib ???? dan pemetaan bijektif ???? dari himpunan titik ke himpunan {1,2,...,????}, sehingga untuk setiap titik ???? di ???? berlaku ?????(????)?????????(????)=????. Graf yang memiliki pelabelan jarak ajaib dinamakan graf jarak ajaib. Tugas akhir ini bertujuan untuk mendapatkan pelabelan jarak ajaib dari graf regular yang tidak saling isomorfik dan memiliki titik sampai dengan 13. Banyak sekali pemetaan yang berbeda dari himpunan titik ke himpunan {1,2,...,????}, sehingga untuk mendapatkan pemetaan yang merupakan pelabelan jarak ajaib membutuhkan waktu yang sangat lama. Sehingga pada tugas akhir ini akan menggunakan program nauty untuk mencari semua graf non isomorfik yang kemudian akan dicari pelabelan jarak ajaib pada graf tersebut dengan menggunakan algoritma simulated annealing. Algoritma simulated annealing ini digunakan untuk mempercepat waktu iterasi pencarian pemetaan yang merupakan pelabelan jarak ajaib. Pencarian menggunakan algoritma simulated annealing diperoleh 14 graf jarak ajaib dengan titik sampai dengan 13, 1 diantaranya merupakan konstruksi baru yang belum diketahui sebelumnya.