TUGAS AKHIR SM 1330 PELABELAN SUPER EDGE GRACEFUL PADA WHEEL GRAPH WICAK BUDI LESTARI SOLICHAH NRP 1203 109 025 Dosen Pembimbing Drs. CHAIRUL IMRON, MIkomp JURUSAN MATEMATIKA Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Surabaya 2009
FINAL PROJECT SM 1330 STUDY ANALYSIS OF SUPER EDGE GRACEFUL LABELING ON WHEEL GRAPH WICAK BUDI LESTARI SOLICHAH NRP 1203 109 025 Supervisor Drs. CHAIRUL IMRON, MIKomp DEPARTMENT OF MATHEMATICS Faculty of Mathematics and Natural Science Sepuluh Nopember Institute of Technology Surabaya 2009
LEMBAR PENGESAHAN
STUDI ANALISIS PELABELAN SUPER EDGE GRACEFUL PADA WHEEL GRAPH
TUGAS AKHIR Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Pada Bidang Minat Ilmu Komputer Program Studi S-1 Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Teknologi Sepuluh Nopember Oleh : WICAK BUDI LESTARI SOLICHAH Nrp. 1203 109 025
Disetujui oleh Pembimbing Tugas Akhir :
Drs. Chairul Imron, MIKomp
(..............................)
NIP 131 688 310
SURABAYA, JULI 2009
STUDI ANALISIS PELABELAN SUPER EDGE GRACEFUL PADA WHEEL GRAPH
Nama Mahasiswa
: Wicak Budi Lestari Solichah
NRP
: 1203 109 025
Jurusan
: Matematika FMIPA-ITS
Dosen Pembimbing : Drs. Chairul Imron, MIKomp
Abstrak Dalam memberi label pada suatu graph dapat dilakukan dengan berbagai tipe. Salah satu tipe dalam pelabelan graph adalah dengan Super Edge Graceful. Untuk mendapatkan Pelabelan Super Edge Graceful dilakukan metode coba-coba sesuai definisi pelabelannya atau dengan menggunakan Teorema yang diperoleh dari keteraturannya. Pelabelan pada Wheel Graph dilakukan untuk p gasal dan genap dengan p adalah banyak vertex. Setelah dilakukan proses pelabelan didapatkan hasil bahwa p gasal diperoleh keteraturan dalam pelabelannya sehingga dapat dinyatakan dalam bentuk umum dan Algoritma pelabelannya. Sedangkan Wheel Graph dengan p genap tidak semuanya dapat dilabelkan. Untuk p = 4 tidak dapat dilabelkan menjadi Super Edge Graceful. Kata kunci : Pelabelan graph, Edge Graceful, Super Edge Graceful, Wheel Graph.
STUDY ANALYSYS OF SUPER EDGE GRACEFUL LABELING ON WHEEL GRAPH
Name
: Wicak Budi Lestari Solichah
NRP
: 1203 109 025
Departement of
: Matematika FMIPA-ITS
Supervisor
: Drs. Chairul Imron, MIKomp
Abstrak Labeling on a graph can be done with various types. One of types of labeling graph is Super Edge Graceful. For getting labeling of Super Edge Graceful is done with trial and error method according to its labeling definition or Theorem from regularity . Labeling on Wheel Graph is done for odd and even p which is the number of vertex. Odd p is gotten regularity in its labeling after labeling process so it can be expressed generally in Theorem and Algorithm of its labeling. Not all Fan Graph with even p can be labeled. For p = 4 can not be labeled Super Edge Graceful. Keywords: Graph Labeling, Edge Graceful, Super Edge Graceful, Wheel Graph.
KATA PENGANTAR Alhamdulillah, segala puji dan syukur penulis panjatkan puji syukur kehadirat Allah SWT atas segala berkah, limpahan rahmat, karunia dan hidayah-Nya, sehingga penulis dapat menyelesaikan Tugas Akhir yang judul “Studi Analisis Pelabelan Super Edge Graceful Pada Wheel Graph”. Tugas Akhir ini disusun sebagai salah satu persyaratan lulus Strata I (S1) Sarjana Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam di Institut Teknologi Sepuluh Nopember Surabaya. Dalam penyusunan Tugas Akhir ini tidak terlepas dari bantuan dan dukungan dari berbagai pihak. Oleh karena itu, penulis mengucapkan terima kasih yang sedalam-dalamnya dan penghargaan yang besar kepada yang terhormat ; 1. Drs. Chairul Imron, MIkomp selaku Dosen Pembimbing yang telah banyak memberi bimbingan dalam penyusunan Tugas Akhir ini. 2. Ibu dan Bapakku tercinta, keluargaku, mas Yunus, adekku Habibah, mbak Utami, dan Eyang kakungku yang tak pernah berhenti memberikan kasih sayang, doa, semangat, dukungan dan semua bantuannya untukku. 3. Ketua Jurusan Matematika ITS, Bapak Prof. Dr. Basuki Widodo, MSc beserta seluruh Dosen dan Karyawan Jurusan Matematika ITS. 4. Drs. Sumarno, DEA, Drs. Daryono BU, M.Si, dan Drs Suhud W, M.Si, Selaku dosen penguji atas saran-saran yang diberikan. 5. Dra. Farida Agustini W, MS selaku Dosen Wali selama menjadi mahasiswa. 6. Koordinator Tugas Akhir Dra. Rinurwati, MSi. 7. Irwan Agung Satrianto, ST atas kasih, perhatian, motivasi, doa, trimakasih sudah menjadi pelipur lara penulis disaat gundah dan putus asa.
8. Sahabatku Nur, Pitut, Tangguh, Layla, Etik, Maya, Fenty, Farida, Sigie, Adri, Radit thank’s atas semua bantuan, support, doa dan sharing yang banyak memberikan pencerahan buatku. 9. Sahabatku Coty, Vira, Vina, Anggara, Andry Bonthank, Iwan, Dewi, Thanks untuk dukungannya dari jauh, sudah menghiasi malam-malamku dengan
dering
telpon
kalian
dan
teman-teman
Ekstensi
2003
seperdjoangan. 10. Blog Jhe people, Dina, Syl, Najma, Ephi, Putri, dan Icha, thanks atas persahabatan, dan kemeriahan dikos yang slalu bikin hidup lebih hidup. Tak terkecuali Mr. Gatot and the gank, atas tumpangan tidur selama merantau di kota Pahlawan. 11. Semua pihak yang tidak bisa penulis sebutkan satu-persatu. Semoga semua kebaikan dan segala bentuk bantuan yang telah diberikan penulis mendapat balasan dari Allah SWT. Penulis menyadari dalam penyusunan Tugas Akhir ini masih jauh dari sempurna. Oleh karena itu, penulis mengharapkan kritik dan saran dari pembaca. Harapan penulis semoga Tugas Akhir ini bermanfaat bagi semua pihak yang berkepentingan.
Surabaya, Juli 2009
DAFTAR ISI
Halaman HALAMAN JUDUL……………………………………….…...……… i HALAMAN PENGESAHAN…………………………………….…… v ABSTRAK…………………………………………………………….… vii KATA PENGANTAR……………….…………..……………………... xi DAFTAR ISI……………………………………..…………………..…. xiii DAFTAR GAMBAR……………………………….………………...… xv DAFTAR NOTASI…………………………………………………...… xix
BAB I PENDAHULUAN 1.1. Latar Belakang Masalah………..………………………………….. 1 1.2. Rumusan Masalah………………………..………………………… 2 1.3. Batasan Masalah…………………………………..……………….. 2 1.4. Tujuan………………..…………………………………………….. 2 1.5. Manfaat………………..…………………………………………… 3 1.6. Sistematika Penulisan…………….………………………………... 3
BAB II DASAR TEORI 2.1. Graph………………………………..……………………...……… 5 2.1.1. Pengertian Graph………………..…………………...…….. 5 2.1.2. Pengertian Pelabelan………………..……………................ 6 2.2. Jenis-jenis Graph…………………………………………………... 7 2.3. Pelabelan pada Graph……………………….…………………..…. 9 2.3.1. Pelabelan Verteks (Vertex Labeling)……………..………… 9 2.3.2. Pelabelan Edge (Edge Labeling)…………………..….……. 9 2.3.3. Pelabelan Total (Total Labeling)……………….………….. 9
2.4. Jenis-jenis Pelabelan (Type Labeling)………………………..….… 9 2.4.1. Pelabelan Graceful…………….……………………............ 9 2.4.2. Pelabelan Edge Graceful………….……………….……….. 12 2.4.3. Pelabelan Super Edge Graceful………………….…………. 13 2.5. Pelabelan pada Cycle Graph………………………….……….…… 16 2.6. Pelabelan pada Star Graph………………………………………… 18
BAB III METODE PENELITIAN 3.1. Langkah-langkah Penelitian…………………………………..…….. 21 3.2. Diagram Alur Penelitian……………………………………..……… 23
BAB VI PELABELAN SUPER EDGE GRACEFUL PADA WHEEL GRAPH 4.1. Pelabelan pada Wheel Graph…………….……………….…….…… 25 4.2. Pelabelan Super Edge Graceful………………………..………….… 26 4.2.1 Pelabelan Super Edge Graceful dengan p gasal........................ 26 4.2.2 Pelabelan Super Edge Graceful dengan p genap…………….. 37
BAB V KESIMPULAN DAN SARAN 5.1. Kesimpulan…………….………….………………………………… 43 5.2. Saran………………….………………………………………….….. 43 DAFTAR PUSTAKA.………………………………..……………...…. 45
DAFTAR GAMBAR
GAMBAR
Halaman
Gambar 2.1 Graph G……………………………………………………. 5 Gambar 2.2 Graph G dengan 5 Vertex dan 8 Edge……………………... 6 Gambar 2.3 Super Edge Graceful pada Path Graph (P6)………...…….. 6 Gambar 2.4 Star Graph (S7)…………………………………………….. 7 Gambar 2.5 Cycle Graph (C6)..…………………….…………………… 8 Gambar 2.6 Wheel Graph (W6)….………………………………...……. 8 Gambar 2.7 Pelabelan Graceful pada Complete Graph (Kn)…………… 10 Gambar 2.8 Edge Graceful pada Path Graph (P3)……………………… 13 Gambar 2.9 Super Edge Graceful pada Path Graph (P6)…………...….. 14 Gambar 2.10 Super Edge Graceful untuk Graph G ……………………. 15 Gambar 2.11 Edge Graceful untuk Graph G …………………………... 15 Gambar 2.12 Edge Graceful untuk Star Graph
…..……………..… 16
Gambar 2.13 Edge Graceful untuk Star Graph
..........................… 17
Gambar 2.14 Super Edge Graceful untuk Star Graph
…………… 17
Gambar 2.15 Super Edge Graceful untuk Star Graph
…………… 18
Gambar 2.16 Edge Graceful untuk Cycle Graph (C3) dan (C5)…….…. 18 Gambar 2.17 Super Edge Graceful untuk Cycle Graph (C3) dan (C5)… 19 Gambar 3.1 Diagram Alur Penelitian………..………………………..... 23 Gambar 4.1 Wheel Graph (W6)……………...…………………….……. 25 Gambar 4.2 Edge Graceful untuk Path Graph
…………………... 26
Gambar 4.3 Super Edge Graceful untuk Path Graph (P3)……………… 26 Gambar 4.4 Super Edge Graceful pada Wheel Graph (W5) dan (W7)….. 28 Gambar 4.5 Super Edge Graceful pada Wheel Graph (W5) dan (W7)..… 30 Gambar 4.6 Super Edge Graceful pada Wheel Graph (W9)…………..… 31 Gambar 4.7 Super Edge Graceful pada Wheel Graph (W9)…………..… 31 Gambar 4.8 Super Edge Graceful pada Wheel Graph (W11)………….… 32 Gambar 4.9 Super Edge Graceful pada Wheel Graph (W11)………….… 32
Gambar 4.10 Super Edge Graceful pada Wheel Graph (W5) dengan core = 0……………………….………………………...... 35 Gambar 4.11 Super Edge Graceful pada Wheel Graph (W5) dengan core = 1…………………………………………….…..… 35 Gambar 4.12 Super Edge Graceful pada Wheel Graph (W5) dengan core = 2………………………………………………....... 36 Gambar 4.13 Super Edge Graceful pada Wheel Graph (W5) dengan core = -2………………………………………………..… 36 Gambar 4.14 Super Edge Graceful pada Wheel Graph (W7)…………… 37 Gambar 4.15 Super Edge Graceful pada Wheel Graph (W6)…………… 41 Gambar 4.16 Super Edge Graceful pada Wheel Graph (W6)…………… 42 Gambar 4.17 Super Edge Graceful pada Wheel Graph (W8)…………….42
DAFTAR NOTASI
V(G)
: Himpunan vertex
E(G)
: Himpunan edge
P
: Himpunan vertex
Q
: Himpunan edge
p
: Banyaknya vertex
q
: Banyaknya edge
u,v
: Vertex
e
: Edge
n
: Bilangan bulat
Sn
: Star Graph
Cn
: Cycle Graph
Wn
: Wheel Graph
K1,n
: Complete Bipartite Graph
f
: Fungsi dari edge
f
+
: Fungsi dari vertex
∑
: Jumlahan
≡
: Kongruen
Zp
: Bilangan bulat modulo p
