Algoritma pelabelan total simpul ajaib pada graf lingkaran, matahari, dan kecebong
| Format: | Bachelors |
|---|---|
| Terbitan: |
Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia
, 2010
|
| Subjects: | |
| Online Access: |
http://lib.ui.ac.id/file?file=digital/20339941-S-Alfa Isti Ananda.pdf |
Daftar Isi:
- Misalkan G adalah graf dengan himpunan simpul V = V(G) dan himpunan busur E = E(G), dimana |V(G)| dan |E(G)| menyatakan banyaknya simpul dan busur pada G. Suatu pemetaan dari V E ke himpunan bilangan bulat 1, 2, ..., |V|+|E| disebut pelabelan total simpul ajaib pada G jika merupakan pemetaan bijektif dengan sifat bahwa untuk setiap simpul vV, (v) + uN(v) (uv) = k dimana N(v) adalah himpunan semua simpul yang bertetangga dengan v. Nilai k disebut konstanta ajaib dari . Algoritma pelabelan sembarang graf secara umum bersifat NP-complete. Baker dan Sawada telah memberikan algoritma pelabelan total simpul ajaib pada graf lingkaran Cn dan graf roda Wn. Pada skripsi ini, algoritma lingkaran tersebut akan dibahas. Selain itu, akan dibangun algoritma pelabelan total simpul ajaib pada graf matahari Cn ⊙ dan graf kecebong Tm,n. Menggunakan algoritma-algoritma tersebut dapat dihasilkan semua pelabelan total simpul ajaib pada graf yang terkait. Algoritma-algoritma ini akan diimplementasikan menggunakan program. Sebagai hasil implementasi dilakukan simulasi yang memberikan banyaknya pelabelan total simpul ajaib yang berbeda dari graf lingkaran Cn dengan 3 ≤ n ≤ 10, graf matahari Cn ⊙ dengan 3 ≤ n ≤ 7, dan graf kecebong Tm,n dengan 3 ≤ m ≤ 7, 1 ≤ n ≤ 5 untuk setiap nilai k yang mungkin.