Algoritma pelabelan total simpul ajaib pada graf friendship, kipas, dan jahangir yang diperumum
| Format: | Bachelors |
|---|---|
| Terbitan: |
Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia
, 2010
|
| Subjects: | |
| Online Access: |
http://lib.ui.ac.id/file?file=digital/20340000-S-Budi Utami.pdf |
Daftar Isi:
- Misalkan adalah graf dengan himpunan simpul dan himpunan busur , dimana dan menyatakan banyaknya busur dan simpul pada . Suatu pemetaan bijektif dari ke himpunan disebut pelabelan total simpul ajaib (PTSA) jika terdapat konstanta sedemikian sehingga untuk setiap berlaku , dimana adalah himpunan simpul yang bertetangga dengan . Nilai disebut bobot . Algoritma pelabelan sembarang graf secara umum adalah bersifat NP-complete. Dalam skripsi ini diberikan algoritma-algoritma untuk menghasilkan semua PTSA yang tidak isomorfik pada graf friendship, kipas, dan jahangir yang diperumum. Algoritma-algoritma tersebut kemudian diimplementasikan dalam bentuk program. Diberikan juga simulasi banyak PTSA yang berbeda untuk setiap nilai k yang mungkin dari ketiga kelas graf tersebut untuk beberapa nilai n dan m. Untuk graf kipas dengan dan graf jahangir yang diperumum dengan dan , dan , serta dan .