Algoritma pelabelan total (a, d)- simpul antiajaib pada graf lintasan dan graf lingkaran
| Format: | Bachelors |
|---|---|
| Terbitan: |
Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia
, 2010
|
| Subjects: | |
| Online Access: |
http://lib.ui.ac.id/file?file=digital/20340200-S-Milla Rachmawati.pdf |
Daftar Isi:
- Misalkan G adalah graf dengan himpunan simpul V dan himpunan busur E, dimana |V(G)| dan |E(G)| menyatakan banyaknya simpul dan busur pada G. Suatu pemetaan λ : V  E  {1, 2 , ..., |V| + |E|} disebut pelabelan total (a, d)-simpul antiajaib jika λ merupakan pemetaan bijektif sedemikian sehingga semua bobot simpul x, yaitu wλ(x) = λ(x) + yN(x) λ(xy),  x  V membentuk barisan aritmatika {a, a+d,..., a+(n−1)d} dengan suku awal a dan beda d dimana N(x) merupakan himpunan semua simpul yang bertetangga dengan x. Jika d = 0 maka disebut pelabelan total simpul ajaib. Jika label simpulnya adalah 1, 2, ..., |V| maka disebut pelabelan total super (a, d)-simpul antiajaib. Algoritma pelabelan sembarang graf secara umum adalah bersifat NP-complete. Dalam skripsi ini diberikan algoritma untuk menghasilkan semua pelabelan total (a, d)-simpul antiajaib dan pelabelan total super (a, d)-simpul antiajaib yang tidak isomorfik pada graf lintasan Pn dan graf lingkaran Cn untuk semua d ≥ 0 yang mungkin. Algoritma-algoritma ini kemudian diimplementasikan dalam program. Diberikan juga simulasi banyak pelabelan total (a,d)-simpul antiajaib dan pelabelan total super (a, d)-simpul antiajaib yang tidak isomorfik untuk semua nilai a dan d yang mungkin sampai nilai n tertentu.