ALGORITMA PELABELAN TOTAL SISI-AJAIB SUPER PADA GRAF BINTANG YANG DIPERUMUM
TUGAS AKHIR
Diajukan untuk memenuhi persyaratan Sidang Sarjana Matematika
Disusun Oleh : Allan Muhammad Taufik NIM : 10102039
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2008
ALGORITMA PELABELAN TOTAL SISI-AJAIB SUPER PADA GRAF BINTANG YANG DIPERUMUM
TUGAS AKHIR
Diajukan untuk memenuhi persyaratan Sidang Sarjana Matematika
Disusun Oleh : Allan Muhammad Taufik NIM : 10102039
Dosen Pembimbing : Dr. M. Salman A.N.
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2008
Lembar Pengesahan
ALGORITMA PELABELAN TOTAL SISI-AJAIB SUPER PADA GRAF BINTANG YANG DIPERUMUM
Disusun Oleh : Allan Muhammad Taufik NIM : 10102039
Telah disetujui dan disahkan sebagai Tugas Akhir Sarjana Program Studi Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Bandung
Bandung, Februari 2008 Pembimbing Tugas Akhir
Dr. M. Salman A.N. NIP. 132084478
Abstrak Algoritma Pelabelan Total Sisi-Ajaib Super pada Graf Bintang yang Diperumum Oleh Allan Muhammad Taufik NIM : 10102039
Misalkan G = (V,E) adalah suatu graf sederhana dan berhingga dengan himpunan titik V dan himpunan sisi E. Suatu pelabelan total sisi-ajaib super pada G adalah fungsi injektif f dari V ∪ E ke himpunan bilangan asli {1,2,...,|V|+|E|} dengan f(V)={1,2,...,|V|} sedemikian sehingga terdapat bilangan bulat positif k, dinamakan konstanta ajaib, yang memenuhi f(x)+f(xy)+f(y) = k untuk setiap xy ∈ E. Graf yang mempunyai pelabelan total sisi-ajaib super disebut graf total sisi ajaibsuper.
Pada tugas akhir ini dikaji tentang pelabelan total sisi-ajaib super pada graf bintang yang diperumum S mn untuk n ≥ 3 dan m ≥ 0. Fokus pengkajian diutamakan pada pengkonstruksian pelabelan total sisi-ajaib super yang mungkin dengan menggunakan algoritma pelabelan yang diimplementasikan pada bahasa pemrograman tertentu.
Kata kunci: graf bintang yang diperumum, pelabelan total sisi-ajaib super, konstanta ajaib.
i
Abstract Algorithm to find a Super Edge-Magic Total Labeling of an Expansion of Stars By Allan Muhammad Taufik NIM : 10102039
Let G = (V,E) be a simple and finite graph with a vertex-set V and an edge-set E. A super edge-magic total labeling of a graph G is an injective function from V ∪ E to {1,2,...,|V|+|E|} with f(V)={1,2,...,|V|} such that there exists a constant k, named a magic constant, satisfying f(x)+f(xy)+f(y) = k for each xy ∈ E. A graph having a super edge-magic total labeling is called a total super edge-magic graph.
In this final project we consider a super edge-magic total labeling of an expansion of the star S mn for n ≥ 3 and m ≥ 0. The main focus is constructing a super edgemagic total labeling using a labeling algorithm, which will be implemented in a language program.
Keywords: expansion of star, super edge-magic total labeling, magic constant.
ii
…niscaya Allah akan meninggikan orang-orang yang beriman di antaramu dan orang-orang yang diberi ilmu pengetahuan beberapa derajat… (QS. Al-Mujadilah:11).
iii
Kata Pengantar Puji dan syukur penulis haturkan ke hadirat Allah SWT atas rahmat dan karuniaNya sehingga penulis dapat menyelesaikan tugas akhir ini.
Penulis mengucapkan terima kasih kepada pihak-pihak yang telah memberikan bantuan dan dorongan selama pengerjaan tugas akhir ini, baik secara langsung maupun tidak langsung, khususnya kepada: 1. Segenap keluarga yang senantiasa memberikan dorongan yang penuh kepada penulis dan doa, agar penulis selalu mendapatkan yang terbaik. Khususnya orangtua yang selalu mendoakan rizki, keselamatan, dan kesehatan kepada penulis. 2. Dr. M. Salman A. N., sebagai dosen pembimbing yang sabar memberikan petunjuk, bimbingan, dan saran sehingga terwujudnya tugas akhir ini. 3. Dr. M. Syamsuddin, M.Com, sebagai dosen wali yang sangat memperhatikan penulis selama menempuh pendidikan di ITB. 4. Seluruh dosen Program Studi Matematika ITB yang telah memberikan ilmu yang luas kepada penulis. 5. I.W Sudarsana, mahasiswa Program S3 Matematika ITB yang telah memberikan nasihat-nasihat bermanfaat seputar tugas akhir. 6. Kunarto dan M. Zaki Mubarak mahasiswa S1 Matematika ITB yang telah membantu penulis dalam mengenal lebih jauh bahasa pemrograman. 7. Teman-teman kuliah S1 Matematika ITB angkatan 2002, khususnya M Fajar Siddik, Rangga Ganzar, dan Alessandra. atas semangat dan dukungan selama penulis menempuh pendidikan di ITB. 8. Teman-teman lain yang sering memberi penulis inspirasi, harapan, dan kebersamaan, khususnya Aaf, Feblil Huda, dan Nasrul.
iv
Penulis menyadari bahwa tugas akhir ini sangat jauh dari kesempurnaan. Karena itu penulis berharap adanya masukan dan saran dari pembaca untuk memperbaiki segala kekurangan yang ada. Semoga bermanfaat.
Bandung, Februari 2008
Penulis
v
Daftar Isi Abstrak ………………………………………………………………………...
i
Abstract ………………………………………………………………………..
ii
Kata Pengantar ………………………………………………………………...
iv
Daftar Isi ………………………………………………………………………
vi
Daftar Gambar ………………………………………………………………...
vii
Daftar Lambang ……………………………………………………………….
ix
Bab I Pendahuluan .……………………………………………………………
1
1.1 Latar belakang ……………………………………………………….
1
1.2 Rumusan masalah ……………………………………………………
2
1.3 Tujuan penelitian dan batasan masalah ……………………………...
2
1.4 Metode dan teknik penelitian ………………………………………..
2
1.5 Sistematika penulisan ………………………………………………..
3
Bab II Graf dan Pelabelan Total Sisi-Ajaib Super …………………………….
4
2.1 Graf dan beberapa definisi dasar …………………………………….
4
2.2 Beberapa kelas graf ………………………………………………….
7
2.3 Pelabelan total sisi-ajaib super ………………………………………
9
2.4 Hasil-hasil peneliti terdahulu ………………………………………... 10 Bab III Algoritma Pelabelan Total Sisi-Ajaib Super ………………….………
14
3.1 Algoritma dan penjelasannya ……..…………………………………
14
3.2 Implementasi algoritma ……………………………………………...
21
3.3 Hasil simulasi …..……………………………………………………
25
Bab IV Kesimpulan dan Masalah Terbuka ........................................................ 30 4.1 Kesimpulan .......................................................................................... 30 4.2 Masalah terbuka ................................................................................... 30 Daftar Pustaka ………………………………………………………………… 31 Indeks …………………………………………………………………………. 32
vi
Daftar Gambar Hal. Gambar 2.1
G1=(V1,E1)
4
Gambar 2.2
G2=(V2,E2)
5
Gambar 2.3
G3=(V3,E3)
5
Gambar 2.4
G4=(V4,E4) ⊆ G3
5
Gambar 2.5
G5=(V5,E5)
6
Gambar 2.6
G3 ∪ G5
6
Gambar 2.7
Graf lintasan P5
6
Gambar 2.8
Graf lingkaran C5
6
Gambar 2.9
Graf pohon T5
7
Gambar 2.10
Graf katerpilar Ĉ9
7
Gambar 2.11
Graf bintang S8
8
Gambar 2.12
Graf pohon pisang BT(5,4,3)
8
Gambar 2.13
Graf bintang yang diperumum S 82
9
Gambar 2.14.a S4 total sisi-ajaib
10
Gambar 2.14.b S4 total sisi-ajaib
10
Gambar 2.15
Pelabelan dual super dari S4 pada Gambar 2.14.b
12
Gambar 2.16
Pelabelan total sisi-ajaib super pada S 24 , S 62 ,dan S 82
13
Gambar 3.1
Graf bintang yang diperumum S mn
15
Gambar 3.2
Matriks Anx(m+2) representasi dari S mn
15
Gambar 3.3
Graf bintang yang diperumum S 81 terlabeli
16
Gambar 3.4
Matriks A8x3 representasi dari S 18
Gambar 3.5
Matriks Cnx(m+1) yang diperoleh dari Anx(m+2)
17
Gambar 3.6
Matriks C8x2 yang diperoleh dari A8x3 pada Gambar 3.4
18
vii
Gambar 3.7
Bagan alir algoritma pelabelan total sisi-ajaib super pada graf bintang yang diperumum
20
Gambar 3.8
Antar muka perangkat lunak sebelum simulasi
25
Gambar 3.9.a
Antar muka perangkat setelah diperoleh pelabelan total sisi-ajaib super
26
Gambar 3.9.b
Antar muka perangkat setelah diperoleh pelabelan total sisi-ajaib super
27
Gambar 3.10
Pelabelan total sisi-ajaib super pada S 33 , S 34 , dan S 34
28
viii
Daftar Lambang
Lambang
Penjelasan singkat
Pendefinisian pertama kali di halaman
Graf G
4
V
Himpunan titik dari graf
4
E
Himpunan sisi dari graf
4
|V|
Kardinalitas dari V
4
|E|
Kardinalitas dari E
4
d(v)
Derajat titik v
5
Pn
Graf lintasan berorde n
6
Cn
Graf lingkaran berorde n
6
Tn
Graf pohon berorde n
7
Ĉn
Graf katerpilar berorde n
7
Sn
Graf bintang berorde n+1
7
S mn
Graf bintang yang diperumum berorde nm+n+1
8
G=(V,E)
BT(n1,n2,…,nk). Graf pohon pisang k
Konstanta ajaib
8 10
ix