Perpustakaan Digital ITB

Penelitian ini mengkaji keberadaan graceful labeling (GL), graceful antimagic labeling (GAL), dan graceful distance–antimagic labeling (GDAL) pada graf sederhana tak berarah berorde kecil hingga orde n ? 9 menggunakan pendekatan komputasional berbasis backtracking teroptimasi. Hasil komputasi menunjukkan bahwa GL memiliki persentase eksistensi tertinggi, diikuti GAL, lalu GDAL. Selain itu, diperoleh bahwa GL tidak menjamin keberadaan GAL maupun GDAL, serta GAL dan GDAL tidak saling mengimplikasikan. Pada graf pohon, hasil komputasi menunjukkan bahwa meskipun setiap graf pohon diduga memiliki GL dan setiap graf terhubung selain K2 diduga memiliki pelabelan antimagic, keberadaan kedua sifat tersebut tidak secara langsung menjamin keberadaan GAL. Secara khusus, ditemukan beberapa graf pohon berorde kecil yang tidak memenuhi GAL, sehingga penentuan syarat perlu dan syarat cukup bagi graf pohon untuk memiliki GAL masih menjadi masalah terbuka. Selain itu, hasil komputasi menunjukkan bahwa graf pohon dengan orde 4 ? n ? 9 yang tidak memiliki dua simpul dengan himpunan tetangga yang sama memiliki GDAL. Oleh karena itu, terdapat dugaan bahwa setiap graf pohon yang tidak memiliki dua simpul dengan himpunan tetangga yang sama memiliki solusi GDAL. Algoritma teroptimasi yang dikembangkan juga terbukti lebih efisien dibandingkan pendekatan brute-force tanpa mengubah hasil pencarian pelabelan.