PELABELAN SUPERMAGIC PADA GRAF POHON TUGAS AKHIR Diajukan sebagai syarat mengikuti sidang Sarjana Matematika Program Studi Matematika Institut Teknologi Bandung
Oleh : Haris Ruhimat 10102037
Pembimbing : Prof. Dr. Edy Tri Baskoro
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2007
Lembar Pengesahan
Pelabelan Supemagic Pada Graf Pohon
Disusun oleh : Haris Ruhimat NIM : 10102037
Telah disetujui dan disahkan sebagai Tugas Akhir Sarjana Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung
Bandung, Juni 2007 Pembimbing Tugas Akhir
Prof. Dr. Edy Tri Baskoro NIP :
Abstrak
Abstrak Pelabelan supermagic adalah salah satu variasi dari pelabelan total pada graf. Sebuah graf G = (V(G), E(G)) dengan jumlah titik n disebut supermagic jika ada sebuah pemetaan satu-satu dan pada
f : V (G ) ∪ E (G ) → ⎡⎣1, V (G ) + E (G ) ⎤⎦
sehingga
f ( x) + f ( y ) + f ( xy ) selalu bernilai konstan untuk setiap sisi xy ∈ E (G ) dan
f (V (G ) ) = [1, n] . Pemetaan f disebut pelabelan supermagic. Tugas akhir ini mengkaji pembuktikan bahwa setiap tree atau graf pohon dengan jumlah titik n terkandung dalam suatu graf pohon yang supermagic dan penulis meyusun suatu algoritma pencarian supertree yang supermagic dari sebuah graf pohon.
Kata kunci : Pelabelan supermagic, pelabelan total, tree atau graf pohon, supertree.
ii Pelabelan Supermagic pada Graf Pohon
Abstract
Abstract Supermagic labelling is a variation of total labelling in a graph. A graph G = (V(G), E(G)) of order n is said to be supermagic if there exists a bijection f : V (G ) ∪ E (G ) → ⎡⎣1, V (G ) + E (G ) ⎤⎦ such that f ( x) + f ( y ) + f ( xy ) is constant
for all edges xy ∈ E (G ) and f (V (G ) ) = [1, n] . f is called supermagic labelling. In
this book we discuss the result that every tree of order n is contained in supermagic tree and we create an algorithm for searching supertree which is supermagic from a tree
Keywords : Supermagic labelling, total labelling, tree, and supertree.
i Algoritma Pewarnaan λ – Backbone dari Suatu Graf dengan Backbone Berupa Matching
Abstract
ii Algoritma Pewarnaan λ – Backbone dari Suatu Graf dengan Backbone Berupa Matching
Prakata
Prakata Segala puji penulis panjatkan ke hadirat Allah SWT sehubungan dengan dapat diselesaikannya tugas akhir ini.
Dalam tugas akhir ini penulis mengambil topik teori graf mengenai pelabelan titik dan sisi atau biasa juga disebut pelabelan total. Jenis pelabelan total yang dibahas adalah pelabelan supermagic dan kelas graf yang dibahas adalah graf pohon. Tugas akhir ini berjudul Pelabelan Supermagic Pada Graf Pohon. Masalah yang akan dibahas adalah metode untuk mencari supertree T’ supermagic yang mengandung graf pohon T, pembuatan algoritma dan implementasi algoritma tersebut ke dalam program aplikasi komputer.
Banyak pihak yang telah memberikan bantuan kepada penulis dalam pengerjaan tugas akhir ini baik secara langsung maupun tidak langsung. Oleh karena itu, penulis ingin mengucapkan terima kasih kepada: 1. Kedua orang tua dan adik penulis yang selalu mendukung dan memberikan doanya agar penulis mendapatkan yang terbaik. 2. Prof. Dr. Edy Tri Baskoro selaku dosen pembimbing yang memberikan bimbingan dan arahan dalam mengerjakan tugas akhir ini.
iii Pelabelan Supermagic pada Graf Pohon
Prakata
3. Dr. Rinovia S, Dr Djoko S Msi, dan RAD Kooswinarsinindyah selaku dosen penguji tugas kahir ini. 4. Dr. Oki Neswan selaku dosen wali yang telah memberi masukan dan motivasi dalam bidang akademis. 5. Semua dosen yang telah mengajarkan ilmunya kepada penulis, yang tidak bisa disebutkan satu persatu. 6. Bu Diah selaku tata usaha program studi Matematika. 7. Teman – teman: Saudara Galih yang telah meminjamkan laptopnya. Saudara Tutur, Fatah Aji, Julius, dan Setiawan yang selalu mendukung dan teman diskusi bagi penulis. Saudari Wiena, dan teman-teman lain yang tidak bisa diucapkan satu-persatu terima kasih karena telah membuat masa perkuliahan penulis lebih berarti. Penulis telah berusaha untuk menyusun tugas akhir yang sempurna, akan tetapi karya manusia jauh dari kesempurnaan. Oleh karena itu penulis menghargai kritik dan saran dari pembaca tugas akhir ini.
Akhir kata, penulis berharap semoga tugas akhir ini dapat bermanfaat untuk menambah wawasan dan dapat diaplikasikan dalam kehidupan nyata. Bandung, Juni 2007
Penulis
iv Pelabelan Supermagic pada Graf Pohon
