PELABELAN GRACEFUL DAN KONSEKUTIF PADA GRAF LINTASAN Pn
Ramdhan Fazrianto Suwarman
PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH JAKARTA 2010 M / 1431 H
PELABELAN GRACEFUL DAN KONSEKUTIF PADA GRAF LINTASAN Pn
Skripsi Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Sarjana Sains Fakultas Sains dan Teknologi Universitas Negeri Syarif Hidayatullah Jakarta
Oleh : Ramdhan Fazrianto Suwarman 106094003173
PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS NEGERI SYARIF HIDAYATULLAH JAKARTA 2010 M / 1431 H
i
PENGESAHAN UJIAN Skripsi berjudul “PELABELAN GRACEFUL DAN KONSEKUTIF PADA GRAF LINTASAN Pn” yang ditulis oleh Ramdhan Fazrianto Suwarman, NIM 106094003173 telah diuji dan dinyatakan lulus dalam Sidang Munaqosyah Fakultas Sains dan Teknologi Universitas Islam Negeri Syarif Hidayatullah Jakarta pada hari Selasa, 31 Agusuts 2010. Skripsi ini telah diterima sebagai salah satu syarat untuk memperoleh gelar sarjana Strata Satu (S1) Program Matematika.
Menyetujui,
Penguji 1,
Penguji 2,
Taufik E. Sutanto, M.ScTech. NIP. 19790530 200604 1 002
Gustina Elfiyanti, M.Si. NIP. 19820820 200901 2 006
Pembimbing 1,
Pembimbing 2,
Yanne Irene, M.Si. NIP. 19741231 200501 2 018
Nur Inayah, M.Si. NIP. 19740125 200312 2 001 Mengetahui,
Dekan Fakultas Sains dan Teknologi
Ketua Program Studi Matematika
DR. Syopiansyah Jaya Putra, M. Sis. NIP. 1968017 200112 1 001
Yanne Irene, M.Si. NIP. 19741231 200501 2 018
ii
PERNYATAAN DENGAN INI SAYA MENYATAKAN BAHWA SKRIPSI INI BENAR-BENAR HASIL KARYA SENDIRI YANG BELUM PERNAH DIAJUKAN SEBAGAI SKRIPSI ATAU KARYA ILMIAH PADA PERGURUAN TINGGI ATAU LEMBAGA MANAPUN.
Jakarta, Agustus 2010
Ramdhan Fazrianto Suwarman 106094003173
iii
PERSEMBAHAN
Kupersembahkan teruntuk Mamah dan Papah Orang yang paling kucintai di dunia Terima kasih atas segalanya …
iv
ABSTRAK Sebuah graf sederhana G = (V, E) dengan n titik dan m sisi dikatakan graceful, apabila graf G tersebut dapat dilabeli dengan pemetaan bijektif f : V(G) → {1, 2, … , n} dan g : E(G) → {1, 2, … , m}, dengan kondisi label setiap sisi merupakan selisih antara label pada dua titik ujungnya. Lebih lanjut, sebuah graf sederhana G = (V, E) dengan n titik dan m sisi yang dapat dilabeli dengan pemetaan bijektif λ : V(G) ∪ E(G) → {1, 2, 3, … , n + m}, dengan kondisi sama seperti pelabelan graceful, maka graf G tersebut dikatakan konsekutif. Pada skripsi ini, akan dikaji tentang pelabelan graceful dan konsekutif pada graf lintasan Pn untuk n ≥ 3. Kata kunci : Pelabelan Graceful, Pelabelan Konsekutif, Graf Lintasan.
v
ABSTRACT A simple graph G = (V, E) with n vertices and m edges called graceful, if that graph G can labeled with a bijection f : V(G) → {1, 2, … , n} and g : E(G) → {1, 2, … , m}, with condition label on any edge equals the difference between the labels of the two endpoints. Furthermore, a simple graph G = (V, E) with n vertices and m edges which can labeled with a bijection λ : V(G) ∪ E(G) → {1, 2, 3, … , n + m} with condition same with graceful labeling, so that graph G called consecutive. In this thesis, examined graceful labeling and consecutive labeling on path graph Pn for n ≥ 3. Keywords : Graceful Labeling, Consecutive Labeling, Graph Path.
vi
KATA PENGANTAR Segala puji hanyalah milik Allah S.W.T., karena Dia-lah Tuhan Yang Maha Esa, terhatur pula segala syukur kepada-Nya, karena atas segala nikmat-Nya lah penulis dapat menyelesaikan tulisan ini yang berjudul, “PELABELAN GRACEFUL DAN KONSEKUTIF PADA GRAF LINTASAN Pn” dengan baik. Penulis menyadari bahwa penyelesaian tulisan ini tidak terlepas pula dari untaian do’a, dukungan, dan bantuan dari berbagai pihak. Oleh karena itu pada kesempatan ini, penulis mengucapkan terima kasih kepada: 1. DR. Syopiansyah Jaya Putra, M.Sis., selaku Dekan Fakultas Sains dan Teknologi UIN Syarif Hidayatullah Jakarta. 2. Yanne Irene, M.Si., selaku Ketua Program Studi (Prodi) Matematika Fakultas Sains dan Teknologi UIN Syarif Hidayatullah Jakarta serta selaku Pembimbing 1 untuk semua waktu, semangat, nasehat, bimbingan, dan ilmu yang telah diberikan kepada Penulis. 3. Nur Inayah, M.Si., selaku Pembimbing II untuk segala waktu, semangat, nasehat, bimbingan, dan ilmunya yang telah diberikan kepada Penulis. 4. Taufik E. Sutanto, M.ScTech., selaku pembimbing akademik serta seluruh dosen dan staf Prodi Matematika untuk semua waktu, saran, ilmu, dan motivasinya.
vii
5. Mamah dan Papahku tercinta, adik-adik kecilku tersayang, Resty dan Annisa, serta seluruh keluarga besar Penulis, untuk semua do’a, bimbingan, dan semangatnya. 6. Anas, Reza, Upeh, Niken, Dwi, Zikri, Farah, Catur, Ela, Vivi, Mahmudi, Karima, Shilah, dan seluruh sahabat 2006 yang selalu memotivasi Penulis untuk segera menyelesaikan skripsinya. 7. Yunita kembaran Yuli, atas semua do’a, saran, dan ide “25 hari mengejar skripsi”, serta seluruh kakak angkatan dan adik angkatan Matematika. 8. Devi, Yasa, Gunawan, Lukman, dan semua anggota 3th generation kelas Puji Syukur SMA Insan Kamil Bogor, atas semua inspirasi dan candanya. 9. Seluruh sahabat dimanapun kalian berada yang tidak dapat disebutkan satu per satu, untuk semua do’a, dukungan, candanya. Semoga pada akhirnya tulisan ini dapat memberikan manfaat dan konstribusi yang berarti untuk siapapun dan dimanapun. Semoga pula kita senantiasa selalu dalam Lindungan-Nya dan menghadap kepada-Nya dalam keadaan khusnul khotimah. Amin.
Jakarta, Agustus 2010
Penulis
viii
DAFTAR ISI HALAMAN JUDUL ..................................................................................... i PENGESAHAN UJIAN ............................................................................... ii PERNYATAAN ............................................................................................ iii PERSEMBAHAN ......................................................................................... iv ABSTRAK .................................................................................................... v ABSTRACT .................................................................................................. vi KATA PENGANTAR .................................................................................. vii DAFTAR ISI ................................................................................................. ix DAFTAR GAMBAR .................................................................................... xi BAB I
PENDAHULUAN ................................................................ 1 1.1. 1.2. 1.3. 1.4. 1.5.
BAB II
1 3 3 3 3
LANDASAN TEORI ........................................................... 4 2.1. 2.2. 2.3. 2.4. 2.5.
BAB III
Latar Belakang ........................................................... Permasalahan ............................................................. Pembatasan Masalah .................................................. Tujuan Penulisan ....................................................... Manfaat Penulisan .....................................................
Definisi Graf .............................................................. Jalan, Lintasan, dan Lintasan Tertutup ...................... Graf Terhubung ......................................................... Jenis – Jenis Graf ....................................................... Pemetaan ....................................................................
4 5 6 7 10
PELABELAN GRAF .......................................................... 12 3.1.
Definisi Pelabelan Graceful ....................................... 13
3.2.
Definisi Pelabelan Konsekutif ................................... 14
3.3.
Graf Lintasan ............................................................. 15
ix
BAB IV
PELABELAN GRACEFUL DAN
KONSEKUTIF
PADA GRAF LINTASAN Pn ............................................. 17 BAB V
KESIMPULAN DAN SARAN ............................................ 24 5.1.
Kesimpulan ................................................................ 24
5.2.
Saran .......................................................................... 24
REFERENSI ................................................................................................ 25
x
DAFTAR GAMBAR Gambar 1.1.
Tujuh Jembatan yang Melintasi Sungai Pregel ....................... 1
Gambar 2.1.
Graf .......................................................................................... 4
Gambar 2.2.
Graf G ...................................................................................... 6
Gambar 2.3.
(a) Graf Terhubung (b) Graf Tak-Terhubung .......................... 7
Gambar 2.4.
Graf Sederhana ........................................................................ 7
Gambar 2.5.
Graf Ganda .............................................................................. 8
Gambar 2.6.
Graf Semu ................................................................................ 8
Gambar 2.7.
Graf Berarah ............................................................................ 9
Gambar 2.8.
Pemetaan Injektif ..................................................................... 10
Gambar 2.9.
Pemetaan Surjektif .................................................................. 11
Gambar 2.10.
Pemetaan Bijektif .................................................................... 11
Gambar 3.1.
Kubus Stewart ......................................................................... 12
Gambar 3.2.
(a) Pelabelan titik (b) Pelabelan total ...................................... 13
Gambar 3.3.
Pelabelan Graceful .................................................................. 14
Gambar 3.4.
Pelabelan Konsekutif ............................................................... 15
Gambar 3.5.
Graf Lintasan ........................................................................... 16
Gambar 4.1.
Graf Lintasan ........................................................................... 17
Gambar 4.2.
Pelabelan Graceful .................................................................. 17
Gambar 4.3.
Contoh Pelabelan Graceful ...................................................... 20
Gambar 4.4.
Contoh Pelabelan Konsekutif .................................................. 23
xi
BAB I PENDAHULUAN
1.1. Latar Belakang Pada awal abad ke-18 terdapat tujuh buah jembatan yang melintasi Sungai Pregel di sebelah Timur Kota Prussian Koningsberg (sekarang Kaliningrad). Dikatakan bahwa terdapat beberapa warga yang mencoba menyeberangi setiap jembatan tersebut dari sebuah rumah dan kembali ke rumah tersebut dengan hanya menyebrangi setiap jembatan-jembatan tersebut tepat sekali.
Gambar 1.1. Tujuh jembatan yang melintasi Sungai Pregel Setelah beberapa waktu, mereka mulai beranggapan bahwa pekerjaan itu tidaklah mungkin, sehingga mereka bertanya kepada Euler bahwa apakah hal tersebut mungkin terjadi. Kemudian Euler membuktikan bahwa hal tersebut tidaklah mungkin. Pembuktian dari kejadian inilah yang dijadikan sebagai permulaan dari Teori Graf [2].
1
1
Teori Graf merupakan cabang sains yang berkembang sangat pesat [13], teori graf sendiri saat ini menjadi topik yang banyak mendapat perhatian , karena model-modelnya yang berguna untuk aplikasi yang luas, seperti masalah dalam jaringan komunikasi, transportasi, ilmu komputer, dan riset operasi [3]. Teori graf juga banyak diaplikasikan dalam kehidupan sehari-hari, antara lain pada rute perjalanan, penjadwalan, dan jaringan listrik [15]. Pelabelan graf merupakan salah satu topik dalam teori graf. Secara umum objek kajiannya merupakan graf yang direpresentasikan oleh titik, sisi, dan himpunan bagian bilangan asli yang disebut label. Pertama kali diperkenalkan oleh Sadlack (1964), kemudian Stewart (1966), Kotzig dan Rosa (1970). Hingga saat ini pemanfaatan teori pelabelan graf sangat dirasakan peranannya, terutama pada sektor sistem komunikasi dan transportasi, navigasi geografis, radar, penyimpanan data komputer, dan desain integrated circuit pada komponen elektronik. Pelabelan merupakan pemetaan bijektif yang memetakan unsur himpunan titik dan atau unsur himpunan sisi ke bilangan asli yang disebut label. Hingga kini dikenal beberapa jenis pelabelan pada graf, antara lain pelabelan graceful, pelabelan harmoni, pelabelan ajaib, pelabelan anti-ajaib, dan pelabelan total tak beraturan. Dalam perkembangan terdapat pelabelan konsekutif, yaitu pelabelan yang di dapat dari pengembangan pelabelan graceful [3]. Beberapa paper yang mengkaji pelabelan graceful dan konsekutif telah dipublikasikan. Wijaya [17] mengkaji pelabelan konsekutif pada graf sikel dan
2
graf bipartit komplit, Wulandari dan Wijaya yang mengkaji Pelabelan konsekutif pada graf-graf pohon [18], Chairul Imron yang mengkaji pelabelan graceful dan konsekutif pada graf tangga, Husnul Hotimah yang mengkaji pelabelan graceful pada graf bipartisi lengkap. Pada penulisan ini, penulis melakukan kajian pelabelan graceful dan konsekutif pada graf lintasan Pn.
1.2. Permasalahan Permasalahan yang dibahas dalam penulisan ini adalah penentuan pelabelan graceful dan konsekutif pada graf lintasan Pn.
1.3. Pembatasan Masalah Pembatasan masalah pada penulisan ini adalah pelabelan graceful dan konsekutif yang dilakukan pada graf lintasan Pn dengan n ≥ 3.
1.4. Tujuan Penulisan Penulisan ini bertujuan untuk mendapatkan bentuk umum dari pelbelan graceful dan konsekutif pada graf lintasan Pn.
1.5. Manfaat Penulisan Manfaat dari penulisan ini adalah untuk mempercepat waktu pelabelan graceful dan konsekutif pada graf lintasan Pn.
3
BAB II LANDASAN TEORI
2.1.
Definisi Graf Menurut [2], secara sederhana graf merupakan kumpulan titik, yang
dihubungkan oleh sisi diantara titik tersebut. v1
e1
v2
e2 v3 v4
e3
v5
Gambar 2.1. Graf Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tak kosong dan E (mungkin kosong) adalah himpunan pasangan tak terurut dari elemen-elemen V. Elemen-elemen dari V disebut titik dari G. Sedangkan elemenelemen dari E disebut sisi dari G. Himpunan titik dari G dinotasikan V(G), himpunan sisi dari G dinotasikan E(G). Graf diatas memiliki 5 titik, yaitu v1, v2, v3, v4, v5 dan 3 sisi, yaitu v1v2, v1v3, v4v5. Setiap sisi yang menghubungkan suatu titik u dengan dirinya sendiri disebut loop. Jika dua atau lebih sisi yang menghubungkan dua titik yang sama, sisi tersebut disebut sisi ganda.
4
4
Menurut [12], dalam mempelajari graf, terdapat beberapa istilah dasar yang familiar dengan graf. Berikut beberapa istilah yang sering dipakai: a. Tetangga, Menempel, dan Titik Ujung Dua titik u dan v dalam sebuah graf tak berarah G disebut tetangga di dalam G jika uv merupakan sebuah sisi di G. Jika e = uv, sisi e tersebut disebut menempel dengan titik u dan v. Jika sisi e menghubungkan titik u dan v. Titik u dan v disebut titik ujung dari sisi e. Pada Gambar 2.1. v1 bertetangga dengan v2 tetapi tidak bertetangga dengan v5, dan e3 menempel pada v4 dan v5, sedangkan v4 dan v5 merupakan titik ujung dari e3.
b. Derajat Derajat sebuah titik pada suatu graf tak berarah merupakan jumlah dari sisi yang menempel terhadapnya, kecuali loop yang dihitung 2 pada titik tersebut. Derajat dari sebuah titik v dinotasikan sebagai d(v). Pada Gambar 2.1. d(v1) = 2 dan d(v4) = 1.
2.2.
Jalan, Lintasan, dan Lintasan Tertutup Jalan pada graf G = (V, E) merupakan sebuah barisan titik-titik v0, v1,…, vk ∈ V Sedemikian sehingga vi-1vi adalah sisi di G untuk setiap i = 1, …, k. Dengan kata lain, jalan berawal dari v0 sampai vk. Jalan yang
5
semua titiknya berbeda disebut lintasan, dan jika seluruh titik-titiknya berbeda kecuali v0 = vk, maka jalan tersebut dinamakan lintasan tertutup. 1
2
5
4
3
Gambar 2.2. Graf G Pada Graf di atas, 5 – 3 – 4 – 5 – 1 – 2 merupakan jalan tetapi bukan merupakan lintasan ataupun lintasan tertutup. Kemudian jalan 5 – 1 – 4 – 3 – 2 merupakan lintasan, dan ketika jalan 5 – 1 – 4 – 5 maka akan menjadi lintasan tertutup.
2.3.
Graf Terhubung Sebuah graf G = (V, E) disebut graf terhubung, jika untuk setiap pasang titik u dan v di dalam himpunan V terdapat lintasan dari u ke v. Jika tidak, maka graf G tersebut disebut graf tak terhubung. Graf yang hanya terdiri atas satu titik saja (tanpa sisi) tetap dikatakan terhubung, karena titik tunggalnya terhubung dengan dirinya sendiri.
6
v1
v3
v2
v4
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v5
Graf G
Graf H
(a)
(b)
Gambar 2.3. (a) Graf Terhubung (b) Graf Tak-Terhubung
2.4.
Jenis-jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori atau jenis
bergantung pada sudut pandang pengelompokkannya. Menurut [12], berdasarkan ada tidaknya loop atau sisi ganda pada suatu graf, maka secara umum graf dapat digolongkan menjadi tiga jenis:
1. Graf sederhana Sebuah graf G = (V, E) merupakan graf sederhana apabila graf tersebut tidak memiliki sisi ganda maupun loop.
Gambar 2.4. Graf Sederhana
7
2. Graf Ganda Sebuah graf G = (V, E) merupakan graf ganda apabila graf tersebut memiliki sisi ganda.
Gambar 2.5. Graf Ganda
3. Graf Semu Sebuah graf G = (V, E) merupakan graf semu apabila graf tersebut memiliki loop termasuk apabila graf tersebut memiliki sisi ganda.
Gambar 2.6. Graf Semu
Berdasarkan orientasi arah pada sisi, maka secara umum graf dapat dikelompokkan menjadi dua jenis:
8
1. Graf Tak-Berarah Graf tak-berarah adalah graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, uv = vu adalah sisi yang sama.
2. Graf Berarah Graf berarah adalah graf yang setiap sisinya diberikan orientasi arah. Pada graf berarah, (u,v) dan (v,u) menyatakan dua buah sisi yang berbeda, dengan kata lain (u,v) ≠ (v,u). Untuk sisi (u,v), simpul u dinamakan titik asal dan simpul v dinamakan titik terminal. Pada graf berarah, loop diperbolehkan, tetapi sisi ganda tidak diperbolehkan. e1
e4
e2
e2 Gambar 2.7. Graf Berarah
9
2.5.
Pemetaan Misalkan A dan B adalah dua himpunan yang tidak kosong. Suatu cara
atau aturan yang memasangkan setiap elemen dari himpunan A dengan tepat satu elemen di himpunan B disebut pemetaan dari himpunan A ke himpunan B. Pemetaan dari himpunan A ke himpunan B diberi notasi 𝜆, yaitu: 𝜆 : A → B. Selanjutnya himpunan A disebut sebagai daerah asal dan himpunan B disebut daerah kawan. Secara umum, pemetaan dapat digolongkan menjadi 3 golongan sebagai berikut :
1. Pemetaan Injektif (Pemetaan Satu-satu) Sebuah pemetaan dikatakan pemetaan injektif, jika dan hanya jika 𝜆 𝑥 = 𝜆(𝑦) mengantarkan kepada x = y untuk setiap x dan y pada domain 𝜆. Secara matematika dapat dituliskan sebagai berikut: 𝜆 : A → B satu-satu ↔ ∀𝑥, 𝑦 ∈ 𝐴, 𝜆 𝑥 = 𝜆 𝑦 → 𝑥 = 𝑦 A
B
a
1
b
2
c
3
d
4 5
Gambar 2.8. Pemetaan Injektif
10
2. Pemetaan Surjektif (Pemetaan Pada) Sebuah pemetaan dari A ke B disebut dengan pemetaan surjektif, jika dan hanya jika untuk setiap elemen b ∈ 𝐵 maka akan terdapat emelen a ∈ 𝐴 dengan 𝜆 𝑎 = 𝑏. Secara matematika dapat ditulis 𝜆 : A → B pada ↔ ∀𝑏 ∈ 𝐵, ∃ 𝑎 ∈ 𝐴, 𝜆 𝑎 = 𝑏 A
B
a
1
b
2
c
3
d
4
e
Gambar 2.9. Pemetaan Surjektif
3. Pemetaan Bijektif (Pemetaan Korespondensi Satu-Satu) Sebuah pemetaan yang memenuhi pemetaan injektif dan surjektif dinamakan pemetaan bijektif (korespondensi satu-satu). Setiap domain akan berkorespondensi secara unik ke elemen kodomain dan sebaliknya. A
B
a
1
b
2
c
3
d
4
e
5
Gambar 2.10. Pemetaan Bijektif 11
BAB III PELABELAN GRAF
Pelabelan pada suatu graf merupakan pemetaan yang memasangkan setiap titik, setiap sisi, ataupun keduanya dengan bilangan bulat positif, dengan suatu keadaan tertentu [4]. Jika domain dari pemetaan adalah himpunan titik maka dinamakan pelabelan titik, serta jika pemetaan dilakukan dengan himpunan sisi sebagai domain maka dinamakan pelabelan sisi dan jika pemetaan yang dilakukan dengan domain titik dan sisi maka dinamakan pelabelan total [10]. Satu contoh terkenal pada pelabelan adalah pelabelan yang dilakukan oleh Stewart pada sisi kubus. Perhatikan bahwa untuk setiap titik, penjumlahan sisi yang insident terhadap titik tersebut bernilai 83. Terlebih lagi, label semua sisi berbeda dan semuanya merupakan bilangan prima [4].
a
b
3 19
43
e 61
11
53
h
29 13
37
g 41
17
d
f
5
c
Gambar 3.1. Kubus Stewart
12 12
Pelabelan pada kubus yang dilakukan oleh Stewart diatas termasuk ke dalam pelabelan sisi. Sedangkan untuk pelabelan titik dan total dapat dilihat pada Gambar 3.2 di bawah ini. 7
3
2 v7
v2
v2
1 6
5
4
3
v6
v3
v1
v3
v1 5
v4
v5
4
1
(a)
6
2
(b)
Gambar 3.2. (a) Pelabelan Titik (b) Pelabelan Total Pelabelan titik diatas merupakan pelabelan titik dengan kondisi penjumlahan setiap titik yang berdekatan mempunyai beda 1 dengan penjumlahan titik yang berdekatan berikutnya. Sedangkan pada pelabelan total diatas, kondisi pelabelan yaitu penjumlahan label pada suatu titik dengan sisi yang insiden terhadapnya mempunyai beda 1 dengan titik berikutnya.
3.1.
Definisi Pelabelan Graceful Sebuah graf sederhana G = (V, E) dengan n titik dan m sisi dikatakan
graceful, apabila graf G tersebut dapat dilabeli dengan pemetaan bijektif f : V(G) → {1, 2, … , n} dan g : E(G) → {1, 2, … , m}, dengan kondisi label setiap sisi merupakan selisih antara label pada dua titik ujungnya.
13
Menurut [4], jika sebuah graf tree mempunyai sebanyak n titik dan 𝑛 − 1 sisi. Maka jika dapat melabeli setiap titik pada tree tersebut dengan 1, 2, 3, …, n dan setiap sisinya dengan 1, 2, 3, .., n – 1, dengan kondisi label setiap sisi merupakan beda (selisih) dari dua titik ujungnya, maka graf tree tersebut dinyatakan sebagai graceful. 7 6
8 6
7
5 9
8 4
1
5
3
2
2
1
3
4
Gambar 3.3. Pelabelan graceful Pelabelan graceful dari graf tree dengan jumlah 9 titik, maka pelabelan dilakukan dengan pelabelan titik adalah 1, 2, 3, .., 9 serta pelabelan sisi adalah 1, 2, 3, …, 8.
3.2.
Definisi Pelabelan Konsekutif Sebuah graf sederhana G = (V, E) dengan n titik dan m sisi dikatakan
konsekutif, apabila graf G tersebut dapat dilabeli dengan pemetaan bijektif λ : V(G) ∪ E(G) → {1, 2, 3, … , n + m}, dengan kondisi label setiap sisi merupakan selisih antara label pada dua titik ujungnya. 14
Jika setiap titik dan sisi pada graf tree diatas dapat dilabeli dengan 1, 2, 3, …, 2n – 1, dengan kondisi pelabelan sisi merupakan selisis dari label dua titik ujungnya, maka graf tree tersebut dinyatakan sebagai kosekutif. Sebagai contoh jika graf tree pada gambar 3.3 dapat dilabeli dengan pelabelan titik dan sisi 1, 2, 3, .., 17, maka graf tree tersebut disebut konsekutif. 15 14
16 10
11
9 17
12 8
5
13
2
4
3
1
6
7
Gambar 3.4. Pelabelan konsekutif Dengan demikian, perbedaan antara pelabelan graceful dan pelabelan konsekutif terletak pada himpunan asalnya.
3.3.
Graf Lintasan Graf lintasan Pn merupakan graf terhubung sederhana yang tediri dari path
tunggal. Graf lintasan dengan n titik memiliki n – 1 sisi. Graf lintasan Pn juga merupakan tree dengan 2 titik berderajat satu, serta n – 2 titik berderajat dua. Graf lintasan P1 sama dengan graf lengkap K1.
15
P1
P2
P3
P4
P5
Gambar 3.5. Graf Lintasan
16
BAB IV PELABELAN GRACEFUL DAN KONSEKUTIF PADA GRAF LINTASAN Pn
Pelabelan graceful pada graf lintasan Pn dengan n titik, maka pelabelan akan dilakukan dengan melabeli titik dengan 1, 2, 3, …, n dan melabeli sisi dengan 1, 2, 3, …, n – 1. Label sisi merupakan selisih dari titik ujungnya.
v1
v2 v1v2
⋯
v3
vn – 1
v2v3
vn
v n – 1vn
Gambar 4.1. Graf lintasan Secara umum pelabelan graceful pada graf lintasan Pn dengan n titik dapat dituliskan sebagai berikut: v1
v2
v3
|v1 – v2| |v2 – v3|
⋯
vn – 1
vn
|v n – 1 – vn|
Gambar 4.2. Pelabelan graceful Teorema berikut menunjukkan bahwa graf lintasan Pn dapat dituliskan sebagai berikut:
17
17
Teorema 4.1. Graf lintasan Pn adalah graceful untuk n ganjil. Bukti : Definisikan label untuk titik – titik dari graf lintasan Pn sebagai berikut : 𝑛−
𝑖−1 2
, 𝑖 = 1, 3, 5, … , 𝑛
1+
𝑖−2 2
, 𝑖 = 2, 4, 6, … , 𝑛 − 1
𝑓1 (𝑣𝑖 ) =
Setelah label titik diperoleh, pelabelan sisi – sisinya akan berpola sebagai berikut : 𝑓1 𝑣𝑖 𝑣𝑖+1 = 𝑛 − 𝑖
, 𝑖 = 1, 2, 3, … , 𝑛 − 1
Ambil sebarang i pada graf lintasan Pn dengan 𝑖 = 1, 2, 3, … , 𝑛 − 1. Akan dibuktikan bahwa 𝑓 𝑣𝑖 − 𝑓 𝑣𝑖+1 = |𝑛 − 𝑖| adalah benar. a.
𝑛−
𝑖−1 2
− 1+
𝑖−2 2
= 𝑛−
= 𝑛−
𝑖−1 2
− 1+
𝑖+1 −2 2
𝑖 1 𝑖 1 + −1− + 2 2 2 2
= |𝑛 − 𝑖| b.
1+
𝑖−2 2
− 𝑛−
𝑖−1 2
=| 1+
𝑖−2 2
− 𝑛−
(𝑖+1)−1 2
|
𝑖 𝑖 = 1+ −1−𝑛+ 2 2 = 𝑖 − 𝑛 = |𝑛 − 𝑖|
18
Dengan mudah dapat ditunjukkan bahwa label titik dan label sisi memenuhi pemetaan bijektif. Jadi graf lintasan Pn dengan n ganjil merupakan graf graceful.
Teorema 4.2. Graf lintasan Pn adalah graceful untuk n genap. Bukti : Definisikan label untuk titik – titik dari graf lintasan Pn sebagai berikut : 𝑛−
𝑖−1 2
, 𝑖 = 1, 3, 5, … , 𝑛 − 1
1+
𝑖−2 2
, 𝑖 = 2, 4, 6, … , 𝑛
𝑓2 (𝑣𝑖 ) =
Setelah label titik diperoleh, pelabelan sisi – sisinya akan berpola sebagai berikut : 𝑓2 𝑣𝑖 𝑣𝑖+1 = 𝑛 − 𝑖
, 𝑖 = 1, 2, 3, … , 𝑛 − 1
Ambil sebarang i pada graf lintasan Pn dengan 𝑖 = 1, 2, 3, … , 𝑛 − 1. Akan dibuktikan bahwa 𝑓 𝑣𝑖 − 𝑓 𝑣𝑖+1 = |𝑛 − 𝑖| adalah benar. a.
𝑛−
𝑖−1 2
− 1+
𝑖−2 2
= 𝑛−
= 𝑛−
𝑖−1 2
− 1+
𝑖+1 −2 2
𝑖 1 𝑖 1 + −1− + 2 2 2 2
= |𝑛 − 𝑖|
19
b.
1+
𝑖−2 2
− 𝑛−
𝑖−1 2
𝑖−2 2
=| 1+
(𝑖+1)−1 2
− 𝑛−
|
𝑖 𝑖 = 1+ −1−𝑛+ 2 2 = 𝑖 − 𝑛 = |𝑛 − 𝑖| Dengan mudah dapat ditunjukkan bahwa label titik dan label sisi memenuhi pemetaan bijektif. Jadi graf lintasan Pn dengan n genap merupakan graf graceful. Contoh pelabelan graceful
3
1
2
2
1 P3
4
1 3
3 2
2 1
P4 5
1 4
4 3
2 2
3 1
P5 6
1 5
5 4
2 3
4 2
3 1
P6 Gambar 4.3. Contoh Pelabelan Graceful
20
Teorema 4.3. Graf lintasan Pn adalah konsekutif untuk n ganjil. Bukti : Definisikan label untuk titik – titik dari graf lintasan Pn sebagai berikut : 2𝑛 − 1 −
𝑖−1 2
, 𝑖 = 1, 3, 5, … , 𝑛
𝑓3 (𝑣𝑖 ) = 𝑛+
𝑖−2 2
, 𝑖 = 2, 4, 6, … , 𝑛 − 1
Setelah label titik diperoleh, pelabelan sisi – sisinya akan berpola sebagai berikut : 𝑓3 𝑣𝑖 𝑣𝑖+1 = 𝑛 − 𝑖
, 𝑖 = 1, 2, 3, … , 𝑛 − 1
Ambil sebarang i pada graf lintasan Pn dengan 𝑖 = 1, 2, 3, … , 𝑛 − 1. Akan dibuktikan bahwa 𝑓 𝑣𝑖 − 𝑓 𝑣𝑖+1 = |𝑛 − 𝑖| adalah benar. a.
(2𝑛 − 1) −
𝑖−1 2
− 𝑛+
𝑖−2 2
= (2𝑛 − 1) −
𝑖−1 2
− 𝑛+
𝑖+1 −2 2
𝑖 1 𝑖 1 = 2𝑛 − 1 − + − 𝑛 − + 2 2 2 2 = |𝑛 − 𝑖| b.
𝑛+
𝑖−2 2
− (2𝑛 − 1) −
𝑖−1 2
= 𝑛+
= 𝑛+
𝑖−2 2
− (2𝑛 − 1) −
(𝑖+1)−1 2
𝑖 𝑖 − 1 − 2𝑛 + 1 + 2 2
= 𝑖 − 𝑛 = |𝑛 − 𝑖|
21
Dengan mudah dapat ditunjukkan bahwa label titik dan label sisi memenuhi pemetaan bijektif. Jadi graf lintasan Pn dengan n ganjil merupakan graf konsekutif.
Teorema 4.4. Graf lintasan Pn adalah konsekutif untuk n genap. Bukti : Definisikan label untuk titik – titik dari graf lintasan Pn sebagai berikut : 2𝑛 − 1 −
𝑖−1 2
, 𝑖 = 1, 3, 5, … , 𝑛 − 1
𝑓4 (𝑣𝑖 ) = 𝑛+
𝑖−2 2
, 𝑖 = 2, 4, 6, … , 𝑛
Setelah label titik diperoleh, pelabelan sisi – sisinya akan berpola sebagai berikut : 𝑓4 𝑣𝑖 𝑣𝑖+1 = 𝑛 − 𝑖
, 𝑖 = 1, 2, 3, … , 𝑛 − 1
Ambil sebarang i pada graf lintasan Pn dengan 𝑖 = 1, 2, 3, … , 𝑛 − 1. Akan dibuktikan bahwa 𝑓 𝑣𝑖 − 𝑓 𝑣𝑖+1 = |𝑛 − 𝑖| adalah benar. a.
(2𝑛 − 1) −
𝑖−1 2
− 𝑛+
𝑖−2 2
= (2𝑛 − 1) −
𝑖−1 2
− 𝑛+
𝑖+1 −2 2
𝑖 1 𝑖 1 = 2𝑛 − 1 − + − 𝑛 − + 2 2 2 2 = |𝑛 − 𝑖|
22
b.
𝑛+
𝑖−2 2
− (2𝑛 − 1) −
𝑖−1 2
= 𝑛+
= 𝑛+
𝑖−2 2
− (2𝑛 − 1) −
(𝑖+1)−1 2
𝑖 𝑖 − 1 − 2𝑛 + 1 + 2 2
= 𝑖 − 𝑛 = |𝑛 − 𝑖| Dengan mudah dapat ditunjukkan bahwa label titik dan label sisi memenuhi pemetaan bijektif. Jadi graf lintasan Pn dengan n genap merupakan graf konsekutif. Contoh pelabelan konsekutif
5
3
4
2
1 P3
7
4 3
6 2
5 1
P4 9
5 4
8 3
6 2
7 1
P5 11
6 5
10 4
7 3
9 2
8 1
P6 Gambar 4.4. Contoh Pelabelan Konsekutif
23
BAB V KESIMPULAN DAN SARAN
5.1.
Kesimpulan Hasil utama dari penulisan ini adalah graf lintasan Pn untuk n ganjil dan n
genap merupakan pelabelan graceful dan konsekutif. Semua hasil tersebut terdapat pada Teorema (4.1), (4.2), (4.3), dan (4.4).
5.2.
Saran Penulisan ini dapat dilanjutkan dengan mencari bentuk (pola) umum dari
pelabelan graceful atau konsekutif pada graf lintasan mPn ataupun pada kelas-kelas graf lainnya, seperti graf bintang, graf kipas dan graf roda. Lebih lanjut lagi penulisan ini dapat dilanjutkan dengan membuat suatu aplikasi khusus untuk memeriksa apakah suatu graf dapat dilabeli secara graceful maupun konsekutif untuk beberapa kelas graf.
24
REFERENSI
[1].
Anderson, Ian., A First Course in Discrete Mathematics. Springer. London: 2001.
[2].
Chen, W.W.L., Discrete Mathematics. 1982.
[3].
Gafur, Abdul. Eksentrik Digraf dari Graf Star, Graf Double Star, Graf Komplit Bipartit dan Pelabelan Konsekutif Pada Graf Sikel dan Graf Bipartit Komplit. Institut Teknologi Bandung.
[4].
Hartsfield, Nora., Ringer, Gerhard.
Pearls in graph theory a
comprehensive introduction. Academic press: San Diego. 1990. [5].
Hotimah, Husnul. Pelabelan Graceful pada Graf Bipartisi Lengkap Km,n. UMN. 2006.
[6].
Imron, Chaerul. Pelabelan Graceful dan Konsekutif pada Graf Tangga. ITS. 2009
[7].
Iqbal, Muhammad, Algoritma Pelabelan Total (a, d)-C3-antiajaib pada Graf Kipas Fn.
[8].
Kurniawan, Dede, Aplikasi Pelabelan Total (a, d)-sisi-antiajaib pada graf lingkaran Cn berbasis GUI. 2009.
[9].
Kusumawardhana, Marhadiasha., Aplikasi Teori Graf pada Analisis Jejaring Sosial. ITB. Bandung: 2009.
[10].
Muntiani, Pelabelan Total Sisi Anti Ajaib Pada Graf 5 nP , 2007.
25
25
[11].
Purcell, Edwin J., Verberg, Dale, and Rigdon, Steven E., Kulkulus Jilid 1, Edisi Kedelapan. Penerbit Erlangga : Jakarta. 2003.
[12].
Rosen, Kenneth H., Discrete Mathematics and Its Applications, Fourth Edition. McGraw-Hill Companies. 1998.
[13].
Suryadi, H.S., Teori Graf Dasar. Gunadarma. Jakarta: 1994.
[14].
Suryadi, H.S., Pengantar Teori dan Algoritma Graph Seri Diklat Kuliah. Gunadarma. Jakarta:1993.
[15].
Susmikanti, Mike, Komputasi Komponen Terhubung dan Jalur Terpendek dalam Algoritma Graf Paralel. Pusat Pengembangan Informatika Teknologi Nuklir, BATAN, 2006
[16].
Weisstein, Eric W., “Path Graph.” From Math World—A Wolfram Web Recource. http://mathworld.wolfram.com/PathGraph.html
[17].
Wijaya K., Pelabelan Konsekutif pada Graf Sikel dan Graf Bipartit Komplit, Jurnal ILMU DASAR vol.5.1:1-7, 2004.
[18].
Wulandari D., Wijaya K., Pelabelan Konsekutif Pada Graf-graf Pohon. Majalah Ilmiah Matematika dan Statistika.
26
