Perpustakaan Digital ITB

Pelabelan graceful dan antimagic merupakan dua jenis pelabelan graf yang banyak dikaji dalam teori graf. Sebuah graf G dengan q sisi dikatakan graceful apabila terdapat fungsi injektif f : V (G) ? {0, 1, . . . , q} sedemikian sehingga himpunan label sisi { |f(u) ? f(v)| : uv ? E(G) } tepat sama dengan {1, 2, . . . , q}. Suatu pelabelan sisi dikatakan antimagic apabila bobot setiap simpul, yaitu jumlah label sisi yang berinsiden dengan simpul tersebut, bernilai berbeda untuk setiap simpul. Penelitian ini memperkenalkan konsep graceful antimagic embedding, yaitu mengonstruksi supergraf H ? G dari sebuah graf terhubung G sehingga H memenuhi syarat pelabelan graceful dan antimagic secara bersamaan. Untuk mengonstruksi H, dirancang algoritma berbasis stochastic heuristic yang bekerja melalui dua strategi, yaitu internal filling (menambahkan sisi antar simpul yang telah ada) dan external filling (menyematkan simpul baru), dengan evaluasi antimagic secara look-ahead pada setiap langkah. Eksperimen dilakukan terhadap seluruh kelas isomorfisme graf terhubung dengan banyak sisi q = 3 hingga q = 12, dengan total 40.962 tipe graf. Algoritma yang diusulkan berhasil menyelesaikan seluruh kasus uji dengan tingkat keberhasilan 100%, dengan waktu komputasi meningkat seiring bertambahnya q, dari 0,002 detik pada q = 3 hingga 131,587 detik pada q = 12. Berdasarkan hasil tersebut, diajukan konjektur bahwa setiap graf terhubung G dapat di-embed ke dalam suatu supergraf H ? G yang memenuhi pelabelan graceful dan antimagic secara bersamaan.