UNIVERSITAS INDONESIA PELABELAN GRACEFUL-BUSUR PADA GRAF CATERPILLAR REGULER SKRIPSI RENDY AHMAD TRIPUTRA

UNIVERSITAS INDONESIA

PELABELAN GRACEFUL-BUSUR PADA GRAF CATERPILLAR REGULER

SKRIPSI

RENDY AHMAD TRIPUTRA 0606067755

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK JUNI 2011

Pelabelan graceful ..., Rendy Ahmad Triputra, FMIPA UI, 2011

UNIVERSITAS INDONESIA

PELABELAN GRACEFUL-BUSUR PADA GRAF CATERPILLAR REGULER

SKRIPSI Diajukan sebagai salah satu syarat untuk memperoleh gelar sarjana sains

RENDY AHMAD TRIPUTRA 0606067755

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM PROGRAM STUDI SARJANA MATEMATIKA DEPOK JUNI 2011

ii


HALAMAN PERNYATAAN ORISINALITAS

Skripsi ini adalah hasil karya saya sendiri, dan semua sumber baik yang dikutip maupun dirujuk telah saya nyatakan dengan benar.

Nama

: RENDY AHMAD TRIPUTRA

NPM

: 0606067755

Tanda Tangan

:

Tanggal

: 16 JUNI 2011

iii


HALAMAN PENGESAHAN

Skripsi ini diajukan oleh Nama NPM Program Studi Judul Skripsi

: : : : :

Rendy Ahmad Triputra 0606067755 Matematika Pelabelan Graceful-Busur pada Graf Caterpillar Reguler

Telah berhasil dipertahankan di hadapan Dewan Penguji dan diterima sebagai bagian persyaratan yang diperlukan untuk memperoleh gelar Sarjana Sains pada Program Studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia

DEWAN PENGUJI

Pembimbing

: Dr. Kiki Ariyanti S., M.Si.

(

)

Penguji

: Prof. Dr. Djati Kerami

(

)

Penguji

: Dra. Nora Hariadi, M.Si.

(

)

Penguji

: Dr. Hengki Tasman, M.Si.

(

)

Ditetapkan di Tanggal

: Depok : 27 Mei 2011

iv


KATA PENGANTAR

Alhamdulillah wa syukurilah penulis panjatkan kepada Allah SWT, atas berkat, rahmat, dan izin-Nya, penulis dapat menyelesaikan skripsi ini. Penulisan skripsi ini dilakukan dalam rangka memenuhi salah satu syarat untuk mencapai gelar Sarjana Sains Departemen Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Indonesia. Penulis menyadari bahwa, tanpa bantuan dan bimbingan dari berbagai pihak, dari masa perkuliahan sampai pada penyusunan skripsi ini, sangatlah sulit bagi penulis untuk menyelesaikan skripsi ini. Oleh karena itu, penulis mengucapkan ribuan terima kasih kepada: 1) Ibu Dr. Kiki Ariyanti Sugeng selaku pembimbing skripsi sekaligus pembimbing akademis penulis. Terima kasih sebesar-besarnya untuk semua senyum, omelan, kritik, bimbingan, dan dukungan yang sangat luar biasa yang diberikan kepada penulis dalam menyelesaikan tugas akhir ini. 2) Bapak Dr. Yudi Satria, Ibu Rahmi Rusin, S.Si, M.ScTech dan Ibu Dr. Dian Lestari sebagai kepala departemen, sekertaris departemen, dan koordinator pendidikan atas bantuan dan dukungannya dalam mempermudah prosedur penyelesaian tugas akhir dan sampai wisuda. 3) Seluruh staf pengajar di departemen Matematika UI, terima kasih atas segala ilmu yang telah diberikan. Semoga penulis dapat menggunakan ilmu tersebut dengan sebaik-baiknya. 4) Mba Santi, Pak Saliman, Mba Rusmi, Mas Ansori, dan Seluruh karyawan di Departemen Matematika UI, terima kasih atas segala bantuan dan kemudahan yang telah diberikan untuk penulis. 5) Mama dan Papa orang tua terbaik yang dengan tulus dan ikhlas melimpahkan kasih sayang yang tidak terbatas. 6) Mas Bayu, Mas Reza, Teh Denti, Qila, keluarga besar Usman dan keluarga besar Ukar sebagai keluarga penulis yang selalu memberikan doa, dukungan, dan nasehat.

v


7) Rita, Syaf, Lee, Yuri, Aliman, Yuko, Ojak, Budi, Bara, Cimz, Mekel, Bekti terima kasih atas semua kegembiraan, keseruan, kejahatan, curhatan, cacian, makian, celaan, dan keindahan lain yang sangat luar biasa. Lima tahun yang sangat hebat kawan. 8) Penghuni Pondok Anugrah Om Moel, Tante Fitri, Djenar, Sinyo, Herman, Sidick, Yoyo, Sangap, Adi, Kardo, Anip, Esha, Akbar, Ucin, Andi, Rudi, Ando, Gembel, Fahri, Adit, Edwin, Andri, Andra, Satrio, Eko, dan semua orang yang pernah menghuni pondok anugrah. Terima kasih banyak atas semua pelatihan mental yang kalian berikan. 9) Teman-teman yang selalu menemani penulis berdiskusi di depan gedung Matematika UI. 10) Teman-teman 2006: Anggha, Oppie, Mei, Inne, Rizkyatul, Rahanti, Stefani, Alfa, Mella, Milla, Tami, Annisa, Widya, Latief, Hot, Noor, Farah, Putri Helmet, Dian, Purwita, Nurgi, Lena, Nadia, Reza, Rifza, Yunita, Indra, Puspa, Febrian, Stefano, Poe, Tasya, Billy, Rahmanita, Kiki, Nobo, Tika, Rontu, Lani, Dita, Teguh, Tino, Muhardani, Rama, Dodi, Rafly, Ali, Sutisna, Pangky, Rita, untuk kebersamaan yang telah dijalani. 11) Teman-teman Matematika UI angkatan 2004, 2005, 2007, 2008, 2009, 2010 12) Teman-teman di Scout Nasa SMP 1 Tangerang. Salam Pramuka. 13) Dan semua orang yang namanya tidak bisa penulis sebutkan satu persatu yang telah mendoakan, mendukung, mengingatkan, mengajarkan, menegur, menginspirasi penulis baik dalam penulisan skripsi ini maupun dalam kehidupan penulis sehari-hari. Akhir kata, penulis berharap Allah SWT berkenan membalas segala kebaikan semua pihak yang telah membantu. Semoga skripsi ini membawa manfaat bagi pengembangan ilmu.

Penulis

2011

vi


HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI TUGAS AKHIR UNTUK KEPENTINGAN AKADEMIS

Sebagai sivitas akademik Universitas Indonesia, saya yang bertanda tangan di bawah ini: Nama NPM Program Studi Departemen Fakultas Jenis karya

: Rendy Ahmad Triputra : 0606067755 : Matematika : Matematika : FMIPA : Skripsi

demi pengembangan ilmu pengetahuan, menyetujui untuk memberikan kepada Universitas Indonesia Hak Bebas Royalti Noneksklusif (Non-exclusive Royalty Free Right) atas karya ilmiah saya yang berjudul : Pelabelan Graceful-Busur pada Graf Caterpillar Reguler beserta perangkat yang ada (jika diperlukan). Dengan Hak Bebas Royalti Noneksklusif ini Universitas Indonesia berhak menyimpan, mengalihmedia/format-kan, mengelola dalam bentuk pangkalan data (database), merawat, dan memublikasikan tugas akhir saya selama tetap mencantumkan nama saya sebagai penulis/pencipta dan sebagai pemilik Hak Cipta. Demikian pernyataan ini saya buat dengan sebenarnya.

Dibuat di : Depok Pada tanggal : 16 Juni 2011 Yang menyatakan

(Rendy Ahmad Triputra)

vii


ABSTRAK

Nama : Rendy Ahmad Triputra Program Studi : Matematika Judul : Pelabelan Graceful-Busur pada Graf Caterpillar Reguler

Graf adalah suatu sistem yang terdiri dari himpunan tak kosong simpul dan himpunan busur . Pelabelan pada graf adalah penetapan nilai pada simpul, busur, atau simpul dan busur dengan aturan tertentu. Pelabelan graceful-busur pada graf adalah fungsi bijektif yang menginduksi pemetaan bijektif yang didefinisikan oleh dengan . Pada skripsi ini dibuktikan bahwa graf caterpillar reguler, dimana dan , dengan sejumlah ganjil simpul pusat ( ) dan sejumlah genap simpul daun pada tiap pusatnya ( ) memiliki pelabelan graceful-busur.

Kata Kunci : pelabelan graceful-busur, graf caterpillar reguler. xii+40 halaman : 26 gambar, 1 tabel Daftar Pustaka : 10 (1988-2010)

viii


ABSTRACT

Name : Rendy Ahmad Triputra Program Study : Mathematics Title : Edge-Graceful Labeling on Regular Caterpillar Graphs

Graph is a system contains of a nonempty set of vertices and a set of edges . Labeling on a graph is an assignment of a nonnegative integer on each vertex, edge, or both under a certain condition. A edge-graceful labeling on graph is a bijection which induce a bijection defined by where . The proof that regular caterpillar graphs, where and with odd vertex center ( ) and even leaf ( ) has an edge-graceful is shown in this skripsi.

Key Words xii+40 pages Bibliography

: edge-graceful labeling, regular caterpillar ; 26 pictures, 1 table : 10 (1988-2010)

ix


DAFTAR ISI

HALAMAN PERNYATAAN ORISINALITAS .................................................. iii HALAMAN PENGESAHAN ............................................................................... iv KATA PENGANTAR ............................................................................................ v HALAMAN PERNYATAAN PERSETUJUAN PUBLIKASI ............................ vii ABSTRAK ........................................................................................................... viii ABSTRACT ........................................................................................................... ix DAFTAR ISI ........................................................................................................... x DAFTAR GAMBAR ............................................................................................. xi DAFTAR TABEL ................................................................................................. xii BAB 1 PENDAHULUAN ..................................................................................... 1 1.1 Latar Belakang .............................................................................................. 1 1.2 Perumusan Masalah dan Ruang Lingkupnya ................................................ 2 1.3 Tujuan Penulisan ........................................................................................... 3 1.4 Jenis Penelitian dan Metode yang Digunakan ............................................... 3 BAB 2 LANDASAN TEORI ................................................................................ 4 2.1 Teori Graf ...................................................................................................... 4 2.2 Jenis-jenis Graf .............................................................................................. 5 2.3 Pelabelan Graf ............................................................................................... 8 2.4 Hasil-Hasil yang Telah Diketahui ............................................................... 10 BAB 3 PELABELAN GRACEFUL-BUSUR PADA GRAF CATERPILLAR REGULER ........................................................................................................... 12 3.1 Pelabelan Graceful-Busur pada Graf Lintasan ............................................ 14 3.2 Pelabelan Graceful-Busur pada Graf Bintang ............................................. 19 3.3 Pelabelan Graceful-Busur pada Graf Bintang Ganda .................................. 23 3.4 Pelabelan Graceful-Busur pada Graf Caterpillar Reguler ........................... 25 3.5 Bentuk Lain Pelabelan Graceful-Busur pada Graf Caterpillar Reguler ...... 35 3.5.1 Pelabelan Graceful-Busur Untuk

dan

................................ 35

3.5.2 Pelabelan Graceful-Busur Untuk

dan

............................. 36

BAB 4 KESIMPULAN ....................................................................................... 39 DAFTAR PUSTAKA .......................................................................................... 40

x


DAFTAR GAMBAR

Gambar 2. 1 Graf lintasan P5 ................................................................................. 5 Gambar 2. 2 Graf lingkaran . ............................................................................. 5 Gambar 2. 3 Graf pohon ........................................................................................ 6 Gambar 2. 4 Graf bintang ................................................................................. 6 Gambar 2. 5 Graf caterpillar .................................................................... 7 Gambar 2. 6 Graf caterpillar reguler . ....................................................... 8 Gambar 2. 7 (a) Graf bintang ganda dan (b) graf bintang ganda reguler .8 Gambar 2. 8 Pelabelan graceful-busur pada graf caterpillar reguler . ........... 9 Gambar 2. 9 Pelabelan graceful-busur pada graf grid . ........................... 10 Gambar 2. 10 Pelabelan graceful-busur pada graf lengkap . .......................... 11 Gambar 2. 11 Pelabelan graceful-busur pada (a) graf lintasan , (b) graf lingkaran , dan (c) graf bintang . ........................................... 11 Gambar 3. 1 Pelabelan graceful-busur pada graf lintasan (a) , (b) , (c) , dan (d) ....................................................................................... 19 Gambar 3. 2 Pelabelan graceful-busur graf bintang (a) dan (b) ................. 22 Gambar 3. 3 Pelabelan graceful-busur graf bintang (a) dan (b) ................. 22 Gambar 3. 4 Pelabelan graceful-busur graf bintang (a) dan (b) . .............. 22 Gambar 3. 5 Pelabelan graceful-busur pada graf bintang ganda ( ). .. 24 Gambar 3. 6 Pelabelan graceful-busur pada graf bintang ganda ( ). .. 25 Gambar 3. 7 Pelabelan graceful-busur pada graf bintang ganda ( ). 25 Gambar 3. 8 Pelabelan graceful-busur pada graf caterpillar reguler . ....................................................................................................... 33 Gambar 3. 9 Pelabelan graceful-busur pada graf caterpillar reguler . 34 Gambar 3. 10 Pelabelan graceful-busur pada graf caterpillar reguler . ....................................................................................................... 34 Gambar 3. 11 Pelabelan graceful-busur pada graf caterpillar reguler . .. 34 Gambar 3. 12 Pelabelan graceful-busur pada graf caterpillar reguler . ....................................................................................................... 36 Gambar 3. 13 Pelabelan graceful-busur pada graf caterpillar reguler .. 36 Gambar 3. 14 Pelabelan graceful-busur pada graf caterpillar reguler . .. 38 Gambar 3. 15 Pelabelan graceful-busur pada graf caterpillar reguler . .. 38

xi


DAFTAR TABEL

Tabel 4. 1 Pelabelan graceful-busur yang dibahas pada skripsi ini ...................... 39

xii


BAB 1 PENDAHULUAN

1.1 Latar Belakang

Teori graf adalah salah satu cabang matematika yang masih sangat muda bila dibandingkan dengan cabang matematika lain. Meskipun demikian, teori graf telah banyak digunakan dalam sejumlah bidang terapan, seperti riset operasi, ilmu komputer, ilmu kimia, dan analisis jaringan sosial. Pada penerapannya, teori graf digunakan untuk menyederhanakan suatu masalah, sehingga lebih mudah untuk diselesaikan dan dipahami. Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736, ketika mencoba membuktikan kemungkinan untuk melewati empat daerah yang terhubung dengan tujuh jembatan di atas sungai Pregel di Kőnigsberg, Rusia, dalam satu perjalanan yang melintasi setiap jembatan tepat satu kali dan kembali ke daerah awal. Masalah jembatan Kőnigsberg tersebut dapat dinyatakan dalam bentuk graf dengan merepresentasikan keempat daerah itu sebagai simpul (vertex) dan ketujuh jembatan sebagai busur (edge) yang menghubungkan pasangan simpul yang sesuai. Pembuktian Euler ditulis dalam karya tulisnya yang berjudul Solutio Problematis ad geometriam situs pertinensi. Pada pembuktiannya tersebut, Euler menyatakan bahwa permasalahan tersebut tidak memiliki solusi (Rosen, 1991). Suatu graf

adalah pasangan himpunan

merupakan suatu himpunan tak kosong, dan

dengan merupakan himpunan (mungkin

kosong) dari pasangan-pasangan tak terurut dari anggota-anggota himpunan Anggota dari dari

disebut simpul dari , dan anggota dari

Banyaknya anggota

banyaknya anggota dengan order dari

ditulis

disebut busur

dan

. Banyaknya anggota

di graf

.

untuk biasa disebut

(Hartsfield & Ringel, 1990). Beberapa jenis graf telah banyak

dikenal seperti graf lingkaran, graf lengkap, graf lintasan, graf pohon, graf

1

Universitas Indonesia


2

bipartit, graf kubik, graf Petersen, graf roda, graf caterpillar, dan masih banyak jenis lainnya. Pada perkembangannya graf menjadi salah satu cabang matematika yang berkembang pesat dan menyebabkan banyaknya penemuan baru mengenai graf. Salah satu cabang yang berkembang adalah pelabelan graf. Pelabelan graf pertama kali diperkenalkan secara formal oleh Kotzig dan Rosa (1967). Pelabelan pada graf

adalah pemberian nilai (biasanya bilangan bulat) pada simpul, busur, atau

keduanya pada graf (Gallian, 2010). Sampai saat ini banyak jenis pelabelan yang telah dikenal, salah satunya adalah pelabelan graceful-busur. Sebuah graf

disebut graf

graceful-busur jika terdapat fungsi bijektif sedemikian sehingga menginduksi pemetaan bijektif yang didefinisikan oleh . Nilai graf dengan

dengan

juga disebut sebagai bobot simpul . Syarat perlu sebuah

simpul dan

busur dapat dilabelkan secara graceful-busur adalah (Lee, Seah, & Wang, 1990).

Kajian mengenai graf yang memiliki pelabelan graceful-busur, belum banyak dilakukan. Masih banyak graf yang belum diketahui apakah dapat dilabelkan secara graceful-busur atau tidak. Beberapa contoh graf yang telah diteliti adalah graf grid (Lee dkk, 2002), graf lengkap (Lee, Lee, & Murthy, 1988), graf lintasan, graf lingkaran, graf bintang, dan graf superstar (Alifah, 2005). Salah satu contoh kelas graf yang belum diteliti adalah graf caterpillar. Oleh karena itu dalam skripsi ini akan dicari konstruksi pelabelan graceful-busur pada graf caterpillar.

1.2 Perumusan Masalah dan Ruang Lingkupnya

Bagaimanakah konstruksi pelabelan graceful-busur pada kelas graf caterpillar? Dalam skripsi ini pembahasan dibatasi hanya untuk pelabelan gracefulbusur pada graf caterpillar reguler

dengan

dan

.



3

1.3 Tujuan Penulisan

Tujuan penulisan skripsi ini adalah untuk menganalisa dan mengkonstruksi pelabelan graceful-busur pada kelas graf caterpillar reguler.

1.4 Jenis Penelitian dan Metode yang Digunakan

Penelitian dilakukan dengan studi pustaka yang dikembangkan untuk menganalisa dan mengkonstruksi pelabelan graceful-busur pada kelas graf caterpillar reguler.



BAB 2 LANDASAN TEORI

Pada bab ini akan dijelaskan konsep dasar dari teori graf, seperti jenisjenis graf, dan pelabelan graf beserta beberapa hasil yang telah diketahui dan akan digunakan pada bab-bab selanjutnya.

2.1 Teori Graf

Suatu graf

adalah pasangan himpunan

merupakan suatu himpunan tak kosong, dan

dengan merupakan himpunan (mungkin

kosong) dari pasangan-pasangan tak terurut dari anggota-anggota himpunan Anggota dari dari

Jika

dengan

disebut simpul dari , dan anggota dari dan

merupakan simpul dari graf , maka

jika terdapat busur yang menghubungkan

dengan busur

atau

. Banyaknya anggota

untuk banyaknya anggota

merupakan titik ujung dari . Simpul

disebut busur dikatakan bertetangga

dan , biasanya ditulis ditulis

dan

. Banyaknya anggota

biasa disebut dengan order dari . Busur

.

di graf

dikatakan hadir pada simpul , jika

dikatakan hadir pada busur

merupakan titik ujung dari . Derajat dari sebuah simpul

jika

adalah banyaknya

busur yang hadir pada . Simpul dengan derajat 0 disebut simpul terpencil dan simpul berderajat 1 disebut simpul ujung atau daun. Graf dengan derajat , atau -reguler, jika setiap simpul di

dikatakan reguler

berderajat . (Hartsfield

& Ringel, 1990). Subgraf dari graf

adalah suatu graf

pakan simpul dari

dan setiap busur dari

lain,

dan

dan

yang setiap simpul dari

meru-

merupakan busur dari . Dengan kata

. Diberikan graf , gabungan dari graf

dimana

dan

ditulis

dan

(Hartsfield & Ringel, 1990).

4



5

2.2 Jenis-jenis Graf

Pada sub bab ini akan dibahas tentang beberapa jenis graf yang sudah dikenal secara umum dan akan banyak dipakai pada bab selanjutnya. Graf lintasan (path), dengan busur

, adalah graf dengan n simpul yaitu . Simpul

disebut sebagai simpul awal dan

sebagai simpul akhir. Semua simpul berderajat dua kecuali untuk simpul awal dan simpul akhir. Suatu graf dan

pada

dikatakan terhubung jika untuk sembarang dua simpul

terdapat lintasan dari

lintasan memiliki contoh graf lintasan

ke

(Hartsfield & Ringel, 1990). Graf

dan

. Pada Gambar 2.1 diberikan

dengan banyak simpul 5 dan banyak busur 4.

Gambar 2. 1 Graf lintasan

Graf lingkaran (cycle) dengan panjang

adalah graf dengan

dan busur-busur

simpul

(Hartsfield & Ringel,

1990). Graf lingkaran adalah graf reguler karena semua simpulnya berderajat 2. Graf unicyclic adalah graf yang memuat satu lingkaran (Gallian, 2010). Jadi graf lingkaran merupakan graf unicyclic. Untuk semua graf unicyclic berlaku . Pada Gambar 2.2 diberikan contoh graf lingkaran yaitu graf lingkaran dengan jumlah simpul 4 dan jumlah busur 4.

Gambar 2. 2 Graf lingkaran

. Universitas Indonesia


6

Graf pohon adalah graf terhubung yang tidak mengandung subgraf lingkaran. Pada graf pohon, simpul berderajat 1 disebut simpul daun (Hartsfield & Ringel, 1990). Gambar 2.3 memberikan contoh graf pohon dengan banyak simpul 23, dan banyak busur 22.

Gambar 2. 3 Graf pohon

Graf bintang

adalah graf yang dibangun dari satu simpul pusat

kemudian menambahkan sejumlah simpul daun pada simpul pusat tersebut. Graf bintang memiliki

simpul dan

graf bintang terdapat

busur (Choudum & Kishore, 1996). Pada

simpul ujung atau daun, dan 1 simpul pusat, yaitu simpul

yang terhubung ke setiap simpul ujung. Graf bintang merupakan subkelas dari pohon, karena graf bintang tidak mempunyai subgraf lingkaran. Gambar 2.4 memberikan contoh graf bintang

yaitu graf bintang dengan 6 simpul, dan 5

busur.

Gambar 2. 4 Graf bintang

.



7

Graf caterpillar

adalah graf yang dibangun dari suatu lintasan

dengan menambahkan sejumlah daun pada setiap simpul pada lintasan - yang disebut tulang belakang atau backbone - yaitu dimana

,

daun pada simpul

,

.

.

(Sugeng, dkk, 2005). Simpul

disebut sebagai simpul pusat dan simpul

;

disebut simpul daun untuk pusat

diberikan graf caterpillar

. Pada Gambar 2.5

yaitu graf caterpillar dengan 19 simpul (5

simpul pusat, dan 5,3,3,1,2 simpul-simpul daun yang terhubung pada tiap simpul pusat secara berurutan) dan 18 busur.

x1 2

x1 1

c3

c2

c1

x1 3

x4 1

x22

x2 1

x1

4

x1 5

x2 3

x3 1

c5

c4

x51

x3 3

x5 2

x32

Gambar 2. 5 Graf caterpillar

.

Sebuah graf caterpillar dikatakan reguler jika banyaknya simpul daun untuk setiap simpul pusatnya sama. Dengan kata lain

dikatakan reguler Universitas Indonesia


8

jika dan hanya jika

dan

diberikan contoh graf caterpillar reguler

x1 1

x1 2

. Pada Gambar 2.6

.

x3 2

x3 1 c2

x51 x52 c4

c1

c5

c3 x2 1 x2 2

x41 x42

Gambar 2. 6 Graf caterpillar reguler

Graf bintang ganda Sebuah graf bintang ganda

.

adalah graf caterpillar

dengan

.

dikatakan reguler jika kedua graf bintang yang

membentuk graf bintang ganda memiliki simpul daun yang sama. Dengan kata lain,

dikatakan reguler jika

bintang ganda

. Pada Gambar 2.7 diberikan contoh graf

dan graf bintang ganda reguler

(a)

(b)

Gambar 2. 7 (a) Graf bintang ganda

dan (b) graf bintang ganda reguler

.

2.3 Pelabelan Graf

Pelabelan graf pertama kali dikenalkan secara formal oleh Kotzig dan Rosa (1967). Pelabelan pada graf

adalah pemberian nilai bilangan bulat pada Universitas Indonesia


9

simpul, busur, atau keduanya pada graf . Sampai saat ini banyak jenis pelabelan yang telah dikenal, salah satunya adalah pelabelan graceful (Gallian, 2010). Menurut Gallian (2010), Rosa mendefinisikan graf graceful pada tahun 1967. Sebuah graf

disebut graceful jika terdapat fungsi injektif sedemikian sehingga menginduksi pemetaan

bijektif

yang didefinisikan oleh

untuk setiap

.

Pada tahun 1985, Lo memperkenalkan sebuah konsep graf graceful-busur. Sebuah graf

dikatakan graceful-busur jika terdapat fungsi

bijektif

sedemikian sehingga menginduksi pemetaan

bijektif

yang didefinisikan oleh dengan

. Nilai

bobot simpul . Syarat perlu sebuah graf dengan

juga disebut sebagai simpul dan

busur dapat

dilabelkan secara graceful-busur adalah

. Konsep dari

graf graceful-busur ini dapat dilihat sebagai konsep dual dari graf graceful (Lee, Seah, & Wang, 1990). Dual yang dimaksud di sini adalah pada graf graceful melibatkan pelabelan simpul yang menginduksi label busur yang merupakan selisih antara dua buah simpul yang hadir pada busur tersebut, sedangkan pada graf graceful-busur melibatkan pelabelan busur yang menginduksi label simpul yang merupakan penjumlahan dari label busur yang hadir modulo banyaknya simpul. Pada Gambar 2.8 diberikan contoh pelabelan graceful-busur pada graf caterpillar reguler

.

4

3 4

3 8

8

2 1

0

5 5

2

1

6 6

7 7

Gambar 2. 8 Pelabelan graceful-busur pada graf caterpillar reguler

.



10

Busur-busur pada graf

(Gambar 2.8) diberikan label

dimana

menyatakan banyak busur. Jika dihitung bobot simpulnya, maka dapat dilihat bahwa bobot simpul tersebut membentuk himpunan

dimana

menyatakan banyak simpul dikurangi .

2.4 Hasil-Hasil yang Telah Diketahui Berikut ini diberikan hasil-hasil yang telah diketahui dari pelabelan graceful-busur untuk beberapa kelas graf. Dalam sebuah makalah, Lee, dkk. (2002) membuktikan bahwa untuk sebuah nilai

terdapat sejumlah hingga

sedemikian sehingga graf grid

dapat dilabelkan secara graceful-busur. Pada Gambar 2.9 diberikan contoh pelabelan graceful-busur pada graf grid

1

16

17

14

18

8

15

13

5

11

5

13

6 14

12

2

9 6

4 23

24

19

10 7

12

20

15

11

7

3

.

10

8 21

0

22 2

9

3 1

4

Gambar 2. 9 Pelabelan graceful-busur pada graf grid

.

Pada tahun 1988, Lee, dkk melakukan penelitian mengenai pelabelan graceful-busur pada graf lengkap

yang membuktikan bahwa graf lengkap

dapat dilabelkan secara graceful-busur jika dan hanya jika

Pada

Gambar 2.10 diberikan contoh pelabelan graceful-busur pada graf lengkap

.



11

4

1

7

3

0

5

6

10

3

4

2

1

8 2

9

Gambar 2. 10 Pelabelan graceful-busur pada graf lengkap

.

Pada tahun 2005, Alifah membuktikan beberapa kelas graf memiliki pelabelan graceful-busur, antara lain : graf lintasan, graf lingkaran, dan graf bintang. Graf lintasan

memiliki pelabelan graceful-busur jika

adalah bilangan

ganjil. Graf lingkaran


adalah

bilangan ganjil. Graf bintang


adalah bilangan ganjil. Pada Gambar 2.11 diberikan contoh pelabelan pada graf lintasan, graf lingkaran dan graf bintang.

1 3

1 1

1

3

2

0

3

2

4

4

0

5

3 4

6

3

3

4

5

2

5

4 (c)

Gambar 2. 11 Pelabelan graceful-busur pada (a) graf lintasan , dan (c) graf bintang

0

6

(b)

lingkaran

2

1

1

4 (a)

2

2

, (b) graf

.



BAB 3 PELABELAN GRACEFUL-BUSUR PADA GRAF CATERPILLAR REGULER

Pada bab ini akan diberikan kontruksi pelabelan graceful-busur dari kelas graf lintasan, graf bintang, graf bintang ganda dan graf caterpillar reguler. Pada Bab 2 telah dijelaskan bahwa sebuah fungsi bijektif dikatakan pelabelan graceful-busur, jika sebuah pemetaan bijektif oleh

menginduksi yang didefinisikan

dengan

(Lee, Seah, & Wang,

1990). Untuk mengkonstruksi pelabelan dan menunjukan bahwa konstruksi yang dibuat adalah graceful-busur, maka secara garis besar pembuktian dilakukan dengan alur sebagai berikut : definisikan fungsi pelabelan untuk busur, lalu ditunjukan bahwa semua bobot simpul yang diperoleh dari pelabelan tersebut merupakan penjumlahan bobot-bobot busur yang hadir membentuk barisan

dan

, pada akhirnya akan ditunjukan bahwa

fungsi pelabelan tersebut adalah fungsi bijektif. Dalam beberapa makalah, Lee dkk (2006) dan Venkatesan & Sattanathan (2010) menyebutkan bahwa, Lo memberikan syarat perlu sebuah graf

dapat

dilabelkan secara graceful-busur. Syarat perlu tersebut dituangkan dalam sebuah teorema. Teorema ini biasa dikenal dengan kondisi Lo.

Teorema 1. Kondisi Lo (Venkatesan & Sattanathan, 2010) : Syarat perlu sebuah graf terhubung , dengan

simpul dan

busur, dapat dilabelkan secara graceful-

busur adalah :

Kondisi ini, dalam penggunaannya biasa dinyatakan sebagai tergantung pada nilai

12

atau

bilangan genap atau ganjil.



13

Bukti : Misalkan

merupakan graf terhubung, dengan

.

dan

merupakan himpunan simpul di , dan merupakan himpunan busur di .

Jika di

dapat dilabelkan secara graceful-busur, maka label himpunan busur

adalah

dan label himpunan simpul di

adalah

. Karena setiap busur menghubungkan dua simpul, maka :

Sedemikian sehingga,

Jadi,

Maka syarat perlu sebuah graf terhubung , dengan

simpul dan

dilabelkan secara graceful-busur adalah

busur, dapat .

Selanjutnya, Lee meneliti penggunaan kondisi Lo pada kelas graf pohon. Dari penelitian tersebut, Lee mendapatkan sebuah conjecture mengenai pelabelan graceful-busur pada kelas graf pohon.

Conjecture 1. (Lee dkk, 2006) Semua pohon dengan order ganjil dapat dilabelkan secara graceful-busur.

Dalam usaha untuk menjawab bagian dari conjecture di atas, maka pada bab ini dibahas mengenai pelabelan graceful-busur untuk subkelas dari pohon yaitu graf lintasan, graf bintang, graf bintang ganda, dan graf caterpillar reguler yang semuanya berorder ganjil. Graf caterpillar dibangun dari graf bintang yang simpul pusatnya dihubungkan oleh sebuah lintasan. Pada Subbab 3.1 akan dibahas mengenai Universitas Indonesia


14

konstruksi pelabelan graceful-busur pada kelas graf lintasan. Pada Subbab 3.2 akan dibahas mengenai konstruksi pelabelan graceful-busur pada kelas graf bintang. Selanjutnya dari pelabelan graceful-busur pada graf bintang tersebut, pada Subbab 3.3 dijelaskan mengenai konstruksi pelabelan graceful-busur pada graf bintang ganda. Akhirnya, pada Subbab 3.4 akan dijelaskan mengenai konstruksi pelabelan graceful-busur pada graf caterpillar reguler.

3.1 Pelabelan Graceful-Busur pada Graf Lintasan

Seperti yang telah dijelaskan pada Bab 2, sebuah graf lintasan sebanyak

simpul dan

memiliki

busur. Untuk melihat apakah terdapat pelabelan

graceful-busur pada kelas graf lintasan akan digunakan kondisi Lo. Dengan menggunakan kondisi Lo pada graf lintasan, akan didapatkan sebuah persamaan yang memberikan syarat banyaknya simpul pada graf lintasan agar dapat dilabelkan secara graceful-busur. Persamaan ini, didapatkan dengan mensubstitusikan banyaknya busur dan banyaknya simpul pada graf lintasan ke dalam kondisi Lo, sehingga didapatkan :

Karena

, jadi

Observasi 1 : Graf lintasan

, dengan

merupakan bilangan genap (order

genap), tidak mempunyai pelabelan graceful-busur. Jika sedangkan dengan

merupakan bilangan genap, maka , dimana

. Dengan demikian, graf lintasan

merupakan bilangan genap (order genap) tidak dapat memenuhi kondisi

Lo, sehingga tidak dapat dilabelkan secara graceful-busur.



15

Observasi 2 : Graf lintasan

, dengan

merupakan bilangan ganjil (order

ganjil), memenuhi kondisi Lo. Jika

merupakan bilangan ganjil, maka

Dengan demikian, graf lintasan

, dengan

.


ganjil), memenuhi kondisi Lo.

Selanjutnya akan dibahas mengenai konstruksi pelabelan graceful-busur pada graf lintasan dengan order ganjil. Alifah pada tahun 2005 telah membuktikan konstruksi pelabelan graceful-busur pada graf lintasan dengan order ganjil, namun pada teorema berikut diberikan pembuktian dengan memodifikasi rumus pelabelan graceful-busur pada graf lintasan, sehingga dapat digunakan untuk pelabelan graceful-busur pada graf caterpillar reguler.

Teorema 2. Graf lintasan hanya jika

dapat dilabelkan secara graceful-busur jika dan

merupakan bilangan ganjil.

Bukti : Dengan menggunakan Observasi 2 diketahui jika graf lintasan mempunyai pelabelan graceful-busur, maka Berikutnya akan dibuktikan untuk


ganjil, maka graf lintasan

dapat dilabelkan

secara graceful-busur. Misalkan .

merupakan graf lintasan, dengan

dan

merupakan himpunan simpul di merupakan himpunan busur di

, dan

.

Pelabelan graceful-busur pada graf lintasan didapatkan dengan memberikan label

ke busur

diberikan label

secara berurutan. Lalu ke busur

secara berurutan. Sedemikian sehingga didapatkan sebuah fungsi yang melabelkan graf lintasan secara graceful-busur, yaitu

sebagai

berikut.



16

Fungsi

tersebut menginduksi label simpul

sebagai berikut.

Selanjutnya akan dibuktikan bahwa fungsi

dan

Pertama, akan dibuktikan

bijektif. bijektif

Jelas terlihat untuk setiap busur :

Jadi, bila diurutkan label untuk busur-busur di

, maka diperoleh :

Karena untuk setiap busur dilabelkan dengan bilangan yang berbeda dan , maka

Kedua, akan dibuktikan

Untuk setiap simpul di

Untuk

bijektif.

bijektif dengan

berlaku

.



17

. . .

Untuk

.

Untuk

. . . Universitas Indonesia


18

Sehingga terbukti bahwa

dan

Akibatnya,

dan

Jadi,

atau bisa dikatakan bahwa

dengan

. Karena untuk setiap simpul dilabelkan dengan bilangan yang berbeda dan

, maka bijektif.

Jadi, dari penjelasan di atas dapat disimpulkan bahwa dan

merupakan fungsi bijektif.



19

Pada Gambar 3.1 diberikan pelabelan graceful-busur pada graf lintasan dengan

2


2

0

1

3

1

3

1

4

(a)

4

,

4

5

0

4

2 1

2

(b)

1

6

5

3

6

2 0

2

1

3

(c)

5

5

6

1

7

6

3

7

2 8

1

0

4

8 2

3

4

(d)

Gambar 3. 1 Pelabelan graceful-busur pada graf lintasan (a)

, (b)

, (c)

, dan (d)

3.2 Pelabelan Graceful-Busur pada Graf Bintang

Selanjutnya, akan dibahas mengenai pelabelan graceful-busur pada kelas graf bintang. Seperti yang telah dijelaskan pada Bab 2, sebuah graf bintang memiliki sebanyak

busur dan

simpul. Untuk melihat apakah terdapat

pelabelan graceful-busur pada kelas graf bintang akan digunakan kondisi Lo. Dengan cara yang serupa dengan yang dilakukan pada graf lintasan, didapatkan :

Karena

, jadi



20

Observasi 3 : Graf bintang

, dengan

merupakan bilangan genap (order

genap), tidak mempunyai pelabelan graceful-busur. Jika

merupakan bilangan genap, maka

sedangkan dengan

, dimana

. Dengan demikian, graf bintang

merupakan bilangan genap (order genap) tidak dapat memenuhi

kondisi Lo, sehingga tidak dapat dilabelkan secara graceful-busur.

Observasi 4 : Graf bintang

, dengan


ganjil), memenuhi kondisi Lo. Jika


Dengan demikian, graf bintang

, dengan

. merupakan bilangan ganjil (order

ganjil), memenuhi kondisi Lo.

Selanjutnya akan dibahas mengenai konstruksi pelabelan graceful-busur pada graf bintang dengan order ganjil. Alifah pada tahun 2005 telah membuktikan konstruksi pelabelan graceful-busur pada graf bintang dengan order ganjil, namun pada teorema berikut diberikan pembuktian dengan penjelasan yang lebih lengkap.

Teorema 3. Graf bintang

, dengan

busur dan

dilabelkan secara graceful-busur jika dan hanya jika

simpul, dapat

merupakan bilangan ganjil

(order ganjil).

Bukti : Dengan menggunakan Observasi 4 diketahui jika graf bintang mempunyai pelabelan graceful-busur, maka Berikutnya akan dibuktikan untuk


ganjil, maka graf bintang

dapat

dilabelkan secara graceful-busur. Universitas Indonesia


21

Misalkan adalah simpul pusat pada graf

dan

merupakan himpunan simpul daunnya. Pelabelan graceful-busur pada graf bintang didapat dengan memberikan label 1, 2, 3, …,

ke busur

secara berurutan. Sedemikian sehingga didapatkan sebuah fungsi yang melabelkan graf bintang secara graceful-busur, yaitu

sebagai

berikut.

Fungsi

tersebut menginduksi label simpul … (3.2.1)

Dari persamaan (3.2.1), didapatkan bahwa Sekarang akan dibuktikan bahwa

. dimana

Karena semua busur

.

, terhubung dengan simpul pusat

dan diketahui bahwa

, maka

Akan dibuktikan :

Karena

ganjil, maka

(sebanyak

Jadi,

untuk

kali)

bilangan ganjil.

Akibatnya fungsi


Jadi,

bilangan ganjil (order ganjil) mempunyai pelabelan graceful-

, dengan

busur.

Pada Gambar 3.2, 3.3, dan 3.4 diberikan pelabelan graceful-busur pada graf bintang

, dengan

merupakan bilangan ganjil. Universitas Indonesia


22

S2 (mod 3)

S4 (mod 5)

1 1

1 1 4

0

4

0

2 2

2

3

2

3

(a)

(b)

Gambar 3. 2 Pelabelan graceful-busur graf bintang (a)

S6

1

S8 (mod 9)

2

(mod 7)

2

1

1

0

6

6 5

2

1

7

0

4

7

4 6

5

(a)

(b)


2 2

1

10

0

5

9

n-1 n-2

n-

3

0 2

7 7

3

.

.

.

4

8

...

n-1

5

6 8

2

1 4

.

2

n-

9

3 4

10

Sn-1 1 (mod n)

3

3

1

dan (b)

n-

S10 (mod 11)

4

5

6

5

3

3

8

3

4

.

2 8

3

dan (b)

6

(a)


n-3

n-4

(b)

dan (b)

.



23

3.3 Pelabelan Graceful-Busur pada Graf Bintang Ganda

Pada Subbab 3.2 telah dibahas pelabelan graceful-busur pada graf bintang. Pada subbab ini akan dibahas mengenai pelabelan graceful-busur pada graf bintang ganda. Graf bintang ganda buah graf bintang

dan

merupakan sebuah graf yang terdiri dari dua yang simpul pusatnya bertetangga satu sama lain.

Graf bintang ganda memiliki sebanyak

simpul dan sebanyak

busur. Untuk melihat apakah terdapat pelabelan graceful-busur pada graf bintang ganda, pertama akan diperiksa persyaratannya dengan mengunakan kondisi Lo. Dengan mensubstitusi banyaknya simpul dan banyaknya busur ke kondisi Lo, akan didapatkan persamaan sebagai berikut :

Karena

, jadi

Observasi 5 : Graf bintang ganda

dengan

merupakan

bilangan genap (order genap) tidak mempunyai pelabelan graceful-busur. Jika


ganjil. Dari kondisi Lo diperoleh dimana

merupakan bilangan sedangkan

Sehingga untuk

bilangan genap, tidak dapat

memenuhi kondisi Lo. Diketahui merupakan bilangan genap atau

. Maka

bernilai genap, jika

keduanya

keduanya merupakan bilangan ganjil.

Dari Observasi 5 di atas dapat pula kita simpulkan bahwa, graf bintang ganda reguler tidak mempunyai pelabelan graceful-busur. Universitas Indonesia


24

Observasi 6 : Graf bintang ganda

dengan

merupakan

bilangan ganjil (order ganjil) dapat memenuhi kondisi Lo. Jika


merupakan bilangan

genap. Dari kondisi Lo diperoleh untuk

bilangan ganjil, dapat memenuhi kondisi Lo. Diketahui

dan

. Sehingga

. Maka

bilangan ganjil atau

bernilai ganjil, jika

bilangan ganjil dan

bilangan genap

bilangan genap.

Dari Observasi 5 dan Observasi 6, didapatkan sebuah conjecture mengenai pelabelan graceful-busur pada graf bintang ganda

Conjecture 2. Graf bintang ganda jika dan hanya jika

ganjil dan

.

dapat dilabelkan secara graceful-busur genap atau

genap dan

ganjil (order

ganjil).

Pada Gambar 3.5, 3.6, 3.7 diberikan contoh pelabelan graceful-busur pada graf bintang ganda. 5

8

6 6

8

5

1

0 4 4

7 7 1

3 3

2 2

Gambar 3. 5 Pelabelan graceful-busur pada graf bintang ganda

(

).



25

5

6

7

6

5

7 1

0

1

8

4

3

4

2 8

2

3


6 7

8

9

3

1

10

2

0

10 9

2 4

0 8

4

5

7

).

3 5

6

(

14 14

11

12

11

13 13 12


(

).

Karena penekanan pada skripsi ini adalah graf caterpillar reguler, maka pelabelan graceful-busur pada graf bintang ganda tidak dibahas lebih lanjut.

3.4 Pelabelan Graceful-Busur pada Graf Caterpillar Reguler

Pada tiga subbab sebelumnya telah dijelaskan tentang pelabelan gracefulbusur pada graf lintasan, graf bintang dan graf bintang ganda. Meskipun pelabelan graceful-busur tidak ada untuk graf bintang ganda reguler, tetapi pelabelan graceful-busur akan ada untuk graf caterpillar reguler, seperti yang akan dijelaskan pada subbab ini. Pelabelan graceful-busur pada graf ceterpillar reguler, Universitas Indonesia


26

didapatkan dengan menggabungkan ide pelabelan graceful-busur pada graf bintang dan graf lintasan. Untuk melabelkan busur yang menghubungkan simpul pusat dengan simpul daun, digunakan ide dari pelabelan graceful-busur pada graf bintang pada Teorema 3, yaitu penjumlahan setiap busur ganjil dan busur genap akan sama dengan

. Sedangkan untuk melabelkan busur yang

menghubungkan dua simpul pusat digunakan rumus dari pelabelan graceful-busur pada graf lintasan pada Teorema 2. Graf caterpillar reguler dan

merupakan graf caterpillar dengan

. Misalkan banyaknya simpul pada graf caterpillar

reguler adalah

dan banyaknya busur pada graf caterpillar adalah . Untuk melihat apakah terdapat pelabelan graceful-

busur pada graf ceterpillar reguler, pertama akan diperiksa persyaratannya dengan menggunakan kondisi Lo. Dengan mensubstitusikan banyaknya simpul dan banyaknya busur ke kondisi Lo, akan didapatkan persamaan sebagai berikut :

Karena

, jadi

Observasi 7 : Graf caterpillar reguler

dengan banyaknya simpul

merupakan bilangan genap (order genap) tidak mempunyai pelabelan graceful-busur. Jika


ganjil. Dari kondisi Lo diperoleh dimana

merupakan bilangan sedangkan

Sehingga untuk

bilangan genap, tidak

dapat memenuhi kondisi Lo. Diketahui

Maka

bernilai genap untuk setiap

merupakan bilangan genap atau untuk setiap

jika

jika merupakan bilangan ganjil. Universitas Indonesia


27

Observasi 8 : Graf caterpillar reguler

dengan banyaknya simpul

merupakan bilangan ganjil (order ganjil ) dapat memenuhi kondisi Lo. Jika


merupakan bilangan

genap. Dari kondisi Lo diperoleh untuk

bilangan ganjil, dapat memenuhi kondisi Lo. Diketahui

dan

. Sehingga

. Maka

bernilai ganjil untuk

bilangan genap

bilangan ganjil. Jadi, pelabelan graceful-busur untuk graf caterpillar reguler

dengan banyaknya simpul ganjil memenuhi kondisi Lo.

Pelabelan graceful-busur pada graf caterpillar reguler dan

dengan

, didapat dengan memberikan label

secara berurutan ke busur

Lalu diberikan label


Selanjutnya diberikan label


Terakhir, diberikan label




28

Dengan menggunakan pelabelan tersebut, maka akan didapatkan pelabelan graceful-busur. Dari penjelasan di atas didapatkan sebuah teorema mengenai pelabelan graceful-busur pada kelas graf caterpillar reguler.

Teorema 4. Graf caterpillar reguler , dan

, dengan

simpul,

busur dapat dilabelkan secara graceful-busur jika dan

hanya jika mempunyai sejumlah ganjil simpul pusat ( ) dan sejumlah genap simpul daun pada tiap pusatnya ( ) (order ganjil).

Bukti : Dengan menggunakan Observasi 8, diketahui jika graf caterpillar reguler mempunyai pelabelan graceful-busur, maka dan

merupakan bilangan genap

merupakan bilangan ganjil. Berikutnya akan dibuktikan untuk

ganjil, maka graf caterpillar reguler

genap dan

dapat dilabelkan secara graceful-

busur. Dengan mensubstitusi

ke pelabelan graceful-

busur pada graf caterpillar yang telah dijelaskan di atas didapatkan fungsi

yang

melabelkan busur-busur pada graf caterpillar reguler, yaitu sebagai berikut :

Fungsi

tersebut menginduksi label simpul

dan Universitas Indonesia


29

Selanjutnya, akan ditunjukan bahwa

dan


Pertama, akan dibuktikan :

bijektif

Jelas terlihat untuk setiap busur :

Jadi, bila diurutkan label untuk busur-busur di

, maka diperoleh

Karena untuk setiap busur dilabelkan dengan bilangan yang berbeda dan , maka

bijektif.

Kedua, akan dibuktikan

bijektif,

dengan Untuk simpul daun, jelas bahwa

, karena hanya

terdapat satu busur yang hadir pada simpul daun. Sehingga,



30

Karena

maka

Dan karena

maka

Jadi, untuk simpul daun didapatkan

Untuk semua simpul pusat berlaku



31

Jadi,

Untuk

.

. . .

Untuk

.



32

Untuk

.

. . .

Sehingga terbukti bahwa

dan

Akibatnya,



33

dan

Jadi,

atau bisa dikatakan bahwa

dengan Karena untuk setiap simpul dilabelkan dengan

bilangan yang berbeda dan

, maka bijektif.

Jadi, dari penjelasan di atas dapat disimpulkan bahwa dan


Pada Gambar 3.8, 3.9, 3.10 dan 3.11 diberikan contoh pelabelan gracefulbusur pada graf caterpillar reguler dengan menggunakan rumus yang telah didapatkan.

13

12

13 23 14 14

11

12 23

24 15 15

10

25 16 16

8

10

11 1

9

24

26 17 17

7

9 2

18 18

3

1 19 19

5

7

8 25

0

6 6 26

2 20 20

4

3 21 21


5 4 22 22

.



34

17

16

15

16

17

15 32

32

13

14

13

33

19

18

14

1

11 33

20

9

10

9

8

23

7 34

1

2

24

5

6

5

4 4 3

3

28

31

26 25

6

2

27 25

22

7

8

24

22 21

10

0

23

20

19

11

12 34

21

18

12

29

26

27

28

30 29

30

31


23 2 24

20 9 22 3

23

46

46

25 4

18

19 47

14 16

17

27 6

11 28

26 5

15

16

15

18 47

48

1

28

27 26

19

20

21

22

24

25

21 8

17

33 29

30

31 13 30

32

18 31

12 29

11 13

14

12

13

0

8 10

11

48 39

34

20 33

25 34

35

19 32

36

37 36

38

37

35

5 7

8

9

1

2

9

10

12

.

6

7

4

5

4

6

2

3

3

45

40

39

41

40

38

42

43 42

43

41

44

45

44


21 22 1 21

20 20

17 19 3 18 1

19

18

16

13 15 3 14 1

17 16

22 43 26 23 23 24

24

44 27

25

28 26 27

25

28

29

13 12 11

11 3 10 1 10 44

0

1

34

30

31 30 31

29

9

14

15 43

12

32

32

9

5 73

61 5

8 7

1

4 4

6

3 3

2

2

35

33

42 36

34 35 33

8

.

36

37

38

39 38 39

37

40


40

41 42 41

.



35

3.5 Bentuk Lain Pelabelan Graceful-Busur pada Graf Caterpillar Reguler Pelabelan yang telah dibahas pada Subbab 3.4, bukan merupakan pelabelan tunggal. Graf caterpillar reguler juga dapat dilabelkan secara gracefulbusur dengan beberapa cara lain. Pada subbab ini akan dibahas mengenai bentuk lain dari pelabelan graceful-busur pada graf caterpillar reguler. Pembahasan dibatasi hanya untuk graf caterpillar reguler


dengan

.

dan

Pelabelan graceful-busur dengan menggunakan rumus ini hanya dapat dilakukan pada beberapa kelas graf ceterpillar reguler, yaitu Pelabelan graceful-busur label

dan

dan

.

didapat dengan memberikan ke busur (dimana

simpul daun di tiap pusatnya, meberikan label

merupakan banyaknya

merupakan banyaknya simpul pusat). Lalu ke busur

.

Jadi didapatkan sebuah fungsi yang melabelkan graf tersebut secara gracefulbusur, yaitu

…(3.5.1.1)

dan …(3.5.1.2)

Persamaan (3.5.1.1) menginduksi label simpul daun

Persamaan (3.5.1.1) dan (3.5.1.2) menginduksi label simpul pusat Universitas Indonesia


36

Pada Gambar 3.12 dan 3.13 diberikan contoh pelabelan graceful-busur pada graf

dan

1

2

.

7

2

1

8 8

7 3

6

18

13

9

9

6

13

4

0 10

5 4

5

14 14 15

3

16

11

10

20 20

19

12

12

19

11

15

18 17

16

17


2

9

1

3 2

7

5

15

10

6 4

10

6

14

23 17

16

9

8

28

4

8

3

1

16

17 21 20

12

5

18 13

18

12

24

23

29

19

20

19

31 30

22

0

13

30

24

11 11

22

15 14

.

21

31

29 7

28

34

25 25

26

27

32 27

32

26

33

34

33



dan

Sama halnya dengan sub-subbab sebelumnya, pelabelan graceful-busur pada sub-subbab ini hanya dapat dilakukan pada beberapa kelas graf ceterpillar reguler, yaitu

dan

. Universitas Indonesia


37

Pelabelan graceful-busur

dan

didapat dengan melabelkan ke busur (dimana

simpul daun di tiap pusatnya,

merupakan banyaknya

merupakan banyaknya simpul pusat). Lalu

memberikan label

ke busur

.

Jadi didapatkan sebuah fungsi yang melabelkan graf bintang secara gracefulbusur, yaitu

…(3.5.2.1)

dan …(3.5.2.2)

Persamaan (3.5.2.1) menginduksi label simpul daun

Persamaan (3.5.2.1) dan (3.5.2.2) menginduksi label simpul pusat

Pada Gambar 3.14, dan 3.15 diberikan contoh pelabelan graceful-busur pada graf

dan

.



38

21

22

16 16

22

21

11

17

5

6

10

6 15

0

24

23

18

24

2 5

15 20

14 19

18

2

1

7

10 23

1

7

12

11

17

20

12

13

19

4

8

13 14

9

3

8

3

9

4


25 24

26 25

23

14

24

13 27

26

15 16

11

22

28

29

29 30

11

22

10 21

18 32

31

5

1

17

31 30

5

4

2

0

32

4 3

1

16

23

28

2

15

12

27

3

13 14

12

.

19

17

20

18

6 21

20

6

9

7

8

7

19

10 9

8


.

Pada Bab ini telah diberikan konstruksi pelabelan graceful-busur dari graf lintasan, graf bintang, dan graf bintang ganda. Dari ketiga konstruksi pelabelan tersebut dikonstruksi pelabelan graceful-busur pada graf caterpillar reguler dengan sejumlah ganjil simpul pusat dan sejumlah genap simpul daun untuk setiap pusatnya. Konstruksi pelabelan graceful-busur pada graf caterpillar reguler tidak tunggal, terdapat beberapa cara lain untuk mengkons-truksi pelabelan gracefulbusur pada graf caterpillar reguler. Karena itu pada Bab ini ditunjukan konstruksi alternatif untuk graf

dan

.



BAB 4 KESIMPULAN

Pada skripsi ini telah dibahas konstruksi pelabelan graceful-busur yang dirangkum pada Tabel 4.1 berikut :

Graf Graf lintasan Graf bintang

Syarat

(Alifah, 2005)

bilangan ganjil

(Alifah, 2005)

bilangan ganjil dan

Graf bintang ganda

berbeda paritas (conjecture) bilangan

Graf caterpillar reguler genap, dan

bilangan ganjil

Tabel 4. 1 Pelabelan graceful-busur pada beberapa kelas graf

Pelabelan graceful-busur untuk graf caterpillar reguler tidak tunggal. Graf caterpillar reguler juga dapat dilabelkan secara graceful-busur dengan beberapa cara lain. Pada skripsi ini juga dibahas mengenai bentuk lain dari pelabelan graceful-busur pada graf caterpillar reguler. Pembahasan dibatasi hanya untuk graf caterpillar reguler

dengan

.

39



40

DAFTAR PUSTAKA

Alifah. (2005). Pelabelan Edge-Graceful pada graf lintasan, graf sikel, graf bintang, dan graf superstar. Skripsi. Departemen Matematika Universitas Jember. Choudum, S. A., & Kishore, S. P. (1996). All 5-star are Skolem graceful. Indian J. Pure and Appl. Math,27 , 1101-1105. Gallian, J. A. (2010). Dynamic survey of Graph Labeling. Electronic Journal of Combinatorics 17 #DS6 . Hartsfield, N., & Ringel, G. (1990). Pearls in graph theory: A Comprehensive Introduction. Academic Press. Lee, L., Lee, S., & Murthy, G. (1988). On Edge-Graceful Labelings of Complete Graphs. Congressus Numeratium 62 , 225-233. Lee, S. M., et al. (2006). On Edge-graceful and Edge-Magic Maximal Outerplanar Graphs. J. Combin. Math. Combin. Comput., 59 , 119-129. Lee, S. M., et al. (2002). On The Edge-Graceful Grids. Congressus Numerantium 154 , 61-77. Lee, S. M., Seah, E., & Wang, P. (1990). On Edge-Gracefulness of The Kth Power Graph. Bulletin of The Institute of Mathematics Academia Sinica 18 , 1-11. Rosen, K. H. (1991). Discrete Mathematics and Its Application 4th edition. Mc Graw Hill. Sugeng, K. A., et al. (2005). (a,d)-edge-antimagic total labeling of caterpillars. Lecture Notes Comput. Sci. , 3330, 169-180. Venkatesan, S., & Sattanathan, D. R. (2010). Is All The Wheel Graphs Are EdgeGraceful? International Journal of Algorithms, Computing and Mathematics 3 , 37-43.

40



UNIVERSITAS INDONESIA PELABELAN GRACEFUL-BUSUR PADA GRAF CATERPILLAR REGULER SKRIPSI RENDY AHMAD TRIPUTRA

Recommend Documents