BILANGAN PELANGI TERHUBUNG PADA GRAF YANG BERKAITAN DENGAN SIKEL SKRIPSI. Oleh: AINUL RHOFIQ TRIDISSUWEDHY NIM

BILANGAN PELANGI TERHUBUNG PADA GRAF YANG BERKAITAN DENGAN SIKEL

SKRIPSI

Oleh: AINUL RHOFIQ TRIDISSUWEDHY NIM. 08610015

JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI MAULANA MALIK IBRAHIM MALANG 2013


SKRIPSI

Diajukan kepada: Fakultas Sains dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim Malang untuk Memenuhi Salah Satu Persyaratan dalam Memperoleh Gelar Sarjana Sains (S.Si)


JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI MAULANA MALIK IBRAHIM MALANG 2013


SKRIPSI


Telah Diperiksa dan Disetujui untuk Diuji: Tanggal: 27 Mei 2013

Pembimbing I

Pembimbing II

Abdussakir, M.Pd

Dr. H. Ahmad Barizi, M.A

NIP. 19751006 200312 1 001

NIP. 19731212 199803 1 001

Mengetahui, Ketua Jurusan Matematika

Abdussakir, M.Pd NIP. 19751006 200312 1 001


SKRIPSI Oleh: AINUL RHOFIQ TRIDISSUWEDHY NIM. 08610015 Telah Dipertahankan di Depan Dewan Penguji Skripsi dan Dinyatakan Diterima Sebagai Salah Satu Persyaratan untuk Memperoleh Gelar Sarjana Sains (S.Si) Tanggal: 13 Juni 2013

Penguji Utama:

Wahyu Henky Irawan, M.Pd NIP. 19710420 200003 1 003

Ketua Penguji:

Hairur Rahman, M.Si NIP. 19800429 200604 1 003

Sekretaris Penguji:

...................


Anggota Penguji:

...................

...................

Dr. H. Ahmad Barizi, M.A NIP. 19731212 199803 1 001

...................

Mengesahkan, Ketua Jurusan Matematika

Abdussakir, M.Pd NIP.19751006 200312 1 001

PERNYATAAN KEASLIAN TULISAN

Saya yang bertanda tangan di bawah ini: Nama

: Ainul Rhofiq Tridissuwedhy

NIM

: 0861005

Jurusan

: Matematika

Fakultas

: Sains danTeknologi

Menyatakan dengan sebenarnya bahwa skripsi yang saya tulis ini benar-benar merupakan hasil karya saya sendiri, bukan merupakan pengambilalihan data, tulisan atau pikiran orang lain yang saya akui sebagai hasil tulisan atau pikiran saya sendiri, kecuali dengan mencantumkan sumber cuplikan pada daftar pustaka. Apabila di kemudian hari terbukti atau dapat dibuktikan bahwa skripsi ini hasil jiplakan, maka saya bersedia menerima sanksi atas perbuatan tersebut.

Malang, 27 Mei 2013 Yang membuat pernyataan,

Ainul Rhofiq Tridissuwedhy NIM. 08610015

MOTTO Ilmu & Bakti Kuberikan, Adil dan Makmur Kuperjuangkan Untukmu Satu Tanah Airku, Untukmu Satu Keyakinanku

Mungguh sajatine ananing dzat kang sanyata iku muhung ana anteping tekat kita, tandhane ora ana apa-apa, ananging kudu dadi sabarang sedya kita kang satuhu

Halaman Persembahan

Skripsi ini penulis persembahkan kepada Ibu tersayang (Mariyati) dan Bapak terhebat (Sanusi) yang selalu memberikan doa dan restunya dalam segala hal, serta kasih sayang yang tak pernah habis. Kepada kakak-kakak terbaik (Nor Jumroti, Turfi’ah, Agus Setyo U, dan Jono) yang tak pernah berhenti dalam memberikan dukungannya.

KATA PENGANTAR

Assalamu’alaikum Wr. Wb. Alhamdulillahirobbil ‘alamin, segala puji bagi Allah SWT atas limpahan rahmat, taufik, hidayah, dan inayah-Nya sehingga penulis dapat menyelesaikan penulisan skripsi ini dengan baik. Shalawat serta salam semoga tetap tercurah limpahkan kepada sang revolusioner Nabi Muhammad SAW yang membimbing umat manusia dari zaman kegelapan jahiliyah menuju zaman terang benderang Islamiyah yang penuh dengan rahmat dan kasih sayang Allah SWT. Semoga mendapatkan syafaatnya di hari akhir nanti. Amin. Penulis menyadari bahwa banyak pihak yang telah berpartisipasi dan membantu dalam menyelesaikan penulisan skripsi ini. Oleh karena itu iringan do’a dan ucapan terima kasih yang sebesar-besarnya penulis sampaikan terutama kepada: 1.

Prof. Dr. H. Mudjia Rahardjo, M.Si, selaku Rektor Universitas Islam Negeri Maulana Malik Ibrahim Malang.

2.

Dr. drh. Hj. Bayyinatul Muchtaromah, M.Si selaku Dekan Fakultas Sains dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim Malang.

3.

Abdussakir, M.Pd, selaku Ketua Jurusan Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim Malang, sekaligus pembimbing.

4.

Dr. H. Ahmad Barizi, M.A, selaku dosen pembimbing keagamaan yang telah memberikan saran dan bantuan selama penulisan skripsi ini.

viii

5.

Dr. Sri Harini, M.Si selaku Dosen Wali.

6.

Seluruh dosen dan staf administrasi Jurusan Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim Malang.

7.

Bapak Sanusi dan Emak Mariyati yang selalu berdo’a untuk kesuksesan anaknya, dan juga kehidupan yang telah diberikan. Serta kakak-kakak tercinta atas dukungannya selama ini.

8.

Hadiratul Mufida dan Tahta Alfina yang telah menjadi saudara terbaik selama ini.

9.

Sahabat-sahabat dalam keluarga PMII Rayon Pencerahan Galileo dan PMII Komisariat Sunan Ampel Malang yang senantiasa membantu dalam suka dan duka.

10. M. Yasin Arief, Mukhlas, Satrio, A. Huda F, M. Fauzan yang selalu menemani dalam penulisan skripsi selama ini. 11. Sahabat-sahabat Matematika angkatan 2008, Nuril Futikhatul A, Adila Mujtahidah, A. Rifqi Z, Dedik Iswahyudi, A. Rizki, Rosi A, Sofiatul I, Elva Rafita S, Dewi Kurniasih, Trisusanti, Fuad Adi, Aris A, M. Halik, dan semuanya yang belum disebut, terimakasih untuk semuanya. 12. Anis Fathona, Erwanto, M. Lutfi, Chamidatus Z, untuk bantuan, semangat dan dukungannya. Agus Syaifurrohim, M. Wildan, Izza Nasrulloh, Arief Nur Handika, Mufid Nurrahman, Barokat Anas, Sandi Yudha, Refki Rosyadi, terimakasih untuk ilmu yang diberikan.

ix

13. Sahabat-sahabat dalam mencari jati diri dan berproses, Bayu Andri, Sigit Bayu, Darul Faruq, Abdur Rohim, Saiur Hasan, Choirudin, A. Wildan, Ainul Yakin, dan semua teman-teman yang belum disebut. Akhirnya, semoga skripsi ini dapat bermanfaat bagi kita semua. Amin. Wassalamu’alaikum Wr. Wb. Malang, Juli 2013

Penulis

x

DAFTAR ISI HALAMAN JUDUL HALAMAN PENGAJUAN HALAMAN PERSETUJUAN HALAMAN PENGESAHAN HALAMAN PERNYATAAN KEASLIAN TULISAN HALAMAN MOTTO HALAMAN PERSEMBAHAN KATA PENGANTAR ................................................................................... viii DAFTAR ISI .................................................................................................. xi DAFTAR GAMBAR ..................................................................................... xiii DAFTAR TABEL ......................................................................................... xv ABSTRAK ..................................................................................................... xvi ABSTRACT ................................................................................................... xvii ‫ هلخص‬................................................................................................................. xviii

BAB I PENDAHULUAN 1.1 Latar Belakang ..................................................................................... 1 1.2 Rumusan Masalah ................................................................................ 5 1.3 Tujuan ................................................................................................... 6 1.4 Batasan Masalah ................................................................................... 6 1.5 Manfaat Penelitian ................................................................................ 6 1.6 Metode Penelitian ................................................................................. 7 1.7 Sistematika Penulisan ........................................................................... 9 BAB II KAJIAN PUSTAKA 2.1 Graf ....................................................................................................... 10 2.2 Terhubung Langsung dan Terkait Langsung ........................................ 11 2.3 Jalan, Lintasan, Jejak, dan Sirkuit ........................................................ 12 2.4 Derajat Suatu Titik ............................................................................... 14 2.5 Operasi pada Graf ................................................................................. 16 2.5.1 Gabungan Graf (Union Graph) .................................................... 16 2.5.2 Penjumlahan Graf (Joint Graph) ................................................... 16 2.6 Macam-macam Graf ............................................................................. 17 2.6.1 Graf Komplit ................................................................................. 17 2.6.2 Graf Sikel ...................................................................................... 18 2.6.3 Graf Bipartisi ................................................................................ 18 2.6.4 Graf Roda ...................................................................................... 19 2.6.5 Graf Helm ..................................................................................... 20 2.6.6 Graf Helm Tertutup ...................................................................... 20 2.6.7 Graf Gear ...................................................................................... 21 2.6.1 Graf Bunga .................................................................................... 21 2.7 Pewarnaan pada Graf ............................................................................ 21

xi

2.7.1 Pewarnaan Titik (vertex colouring) .............................................. 22 2.7.2 Pewarnaan Sisi (edge colouring) ................................................. 23 2.8 Pelangi Terhubung (Rainbow Connection) .......................................... 23 2.9 Relevansi Pelangi Terhubung (Rainbow Connection) pada Graf dalam Kajian Agama Islam ................................................................. 25 BAB III PEMBAHASAN 3.1 Graf Sikel ........................................................................................ 30 3.2 Graf Roda ....................................................................................... 42 3.3 Graf Gear ......................................................................................... 51 3.4 Graf Helm ....................................................................................... 70 3.5 Graf Helm Tertutup ...................................................................... 82 3.6 Graf Bunga .................................................................................... 100 BAB IV PENUTUP 4.1 Kesimpulan ........................................................................................... 115 4.2 Saran ..................................................................................................... 116 DAFTAR PUSTAKA .................................................................................... 118

xii

DAFTAR GAMBAR

Gambar 2.1 Graf

....................................................................................... 11

Gambar 2.2 Graf G ......................................................................................... 11 Gambar 2.3 Graf

...................................................................................... 12

Gambar 2.4 Lintasan Graf

......................................................................... 13

Gambar 2.5 Sirkuit dan Jejak (Trail) Graf

.................................................. 13

Gambar 2.6 Graf dengan Derajat Titik ........................................................... 15 Gambar 2.7 Graf

.................................................................. 16

Gambar 2.8 Penjumlahan Dua Graf .............................................................. 17 Gambar 2.9 Graf Komplit .............................................................................. 17 Gambar 2.10 Graf Sikel .................................................................................... 18 Gambar 2.11 Graf Bipartisi .............................................................................. 19 Gambar 2.12 Graf Roda ................................................................................... 19 Gambar 2.13 Graf Helm ................................................................................... 20 Gambar 2.14 Graf Helm Tertutup .................................................................... 20 Gambar 2.15 Graf Gear .................................................................................... 21 Gambar 2.16 Graf Bunga .................................................................................. 21 Gambar 2.17 Perwarnaan Titik ......................................................................... 23 Gambar 2.18 Pewarnaan Sisi ............................................................................ 23 Gambar 2.19 Pelangi Terhubung (Rainbow Connection) ................................ 25 Gambar 2.20 Isra’ ............................................................................................. 26 Gambar 2.21 Mi’raj .......................................................................................... 28 Gambar 2.22 Peristiwa Isra’ Mi’raj .................................................................. 28 Gambar 3.1 Graf Sikel

............................................................................... 31

Gambar 3.2 Graf Sikel

............................................................................... 31


................................................................................ 32


................................................................................ 33


............................................................................... 34

Gambar 3.6 Graf Roda

............................................................................. 42


............................................................................. 43 xiii


.............................................................................. 43


.............................................................................. 45


............................................................................. 46

Gambar 3.11 Graf Gear

............................................................................... 51


............................................................................... 52


................................................................................ 54


................................................................................ 56


............................................................................... 58

Gambar 3.16 Graf Helm

............................................................................. 71


............................................................................. 72


.............................................................................. 74


.............................................................................. 75


............................................................................. 77

Gambar 3.21 Graf Helm Tertutup

............................................................. 82


............................................................. 83


.............................................................. 85


.............................................................. 86


............................................................. 88

Gambar 3.26 Graf Bunga

........................................................................... 100


........................................................................... 101


............................................................................ 102


............................................................................ 104


........................................................................... 105

xiv

DAFTAR TABEL Tabel 3.1 Pola Bilangan

dan

pada

sampai

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

Tabel 3.2 Pola Bilangan

dan

pada

sampai

.................... 47


dan

pada

sampai

..................... 61


dan

pada

sampai

..................... 79


dan

pada

sampai

................. 91


dan

pada

sampai

................... 107

xv

ABSTRAK Tridissuwedhy, Ainul Rhofiq. 2013. Bilangan Pelangi Terhubung pada Graf yang Berkaitan dengan Sikel. Skripsi. Program S1 Jurusan Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Maulana Malik Ibrahim Malang. Pembimbing : (1) Abdussakir, M.Pd (2) Dr. H. Ahmad Barizi, M.A Kata Kunci : Rainbow edge-connection, Rainbow vertex-connection, Graf Sikel, Graf Roda, Graf Gear, Graf helm, Graf Helm Tertutup, Graf Bunga Dalam teori graf konsep pewarnaan terus mengalami perkembangan, salah satunya adalah tentang rainbow connection. Rainbow connection dibagi menjadi 2 jenis, yang pertama adalah pelangi sisi terhubung (rainbow edge-connected), sedangkan yang kedua adalah pelangi titik terhubung (rainbow vertex-connected) . Rainbow edge-connection pada graf G yang terhubung yaitu bilangan terkecil dari warna yang dibutuhkan untuk membuat graf menjadi pelangi sisi terhubung, sedangkan Rainbow vertex–connection pada graf G yang terhubung merupakan bilangan terkecil dari warna yang dibutuhkan untuk membuat graf G menjadi pelangi titik terhubung. Pada penelitian ini akan dibahas tentang bilangan bilangan dan pada sikel,graf roda,graf gear,graf helm,graf helm tertutup, dan graf bunga Berdasarkan penelitian diperoleh bahwa rumus umum untuk pada graf sikel adalah jika dan ⌈ ⌉ untuk . pada graf roda adalah jika , jika , dan jika . pada graf gear adalah untuk . pada graf helm adalah untuk . pada graf helm tertutup adalah jika , jika , dan jika . Dan pada graf bunga adalah dan untuk . Sedangkan pada graf sikel adalah jika , jika , jika , ⌈ ⌉ jika , dan ⌈ ⌉ jika , dan untuk

.

pada graf roda adalah jika jika . pada graf gear adalah dan jika . pada graf helm adalah jika , dan jika . pada graf helm tertutup adalah jika , jika , jika , dan jika . Dan pada graf bunga adalah untuk . Pada skripsi ini, penulis hanya memfokuskan pada pokok bahasan pada graf yang berkaitan dengan sikel. Maka dari itu dapat dikaji dengan jenis graf yang lain.

xvi

ABSTRACT Tridissuwedhy, Ainul Rhofiq. 2013. The Number of Rainbow Connection on Cycle Related Graphs. Thesis. S1 Department of Mathematics Faculty of Science and Technology State Islamic University of Maulana Malik Ibrahim Malang. Advisors : (1) Abdussakir, M.Pd (2) Dr. H. Ahmad Barizi, M.A In the graph teory, concept of colouring immediately work out. It’s one of rainbow connection. Rainbow connection is divided into two parts, the first isi rainbow edge connection and the second is rainbow vertex connection The rainbow edge-connection of a connected graph is the smallest number of colors that are needed in order to make graph rainbow edge connected, and then the rainbow vertex-connection of a connected graph is the smallest number of colors that are needed in order to make rainbow vertex-connected. This research was analysis about number of and from cycle graph, wheel graph, gear graph, helm graph, closed helm graph, and flower graph. The result show that conclusion from this research are from cycle graph are if and ⌈ ⌉ if . from wheel graph are if , if , and if . from gear graph is if . from helm graph is if . from closed helm graph are if , if , and if . And from flower graph are if and if . And then from cycle graph are if , if , if , ⌈ ⌉ if , and wheel graph are if from gear graph are from helm graph are from closed helm graph are , if from flower graph is This thesis just focuses on graph be analyzed by another graph.

if if

⌈ ⌉ if , and and , and if

.

from if . if . if . if . and

, , and if if . that related to cycle. So from that, it can

Keywords : Rainbow edge-connection, Rainbow vertex-connection, Cycle Graph, Wheel Graph, Gear Graph, Helm Graph, Closed Helm Graph, Flower Graph

xvii

‫هلخّص‬ ‫‪ .‬أرقام هتصل على رسن بياني تتصل سيكيل هن قوس‬

‫تُشٌ دَغىَذٌ ‪,‬ػٍُ انشفُق ‪.‬‬ ‫قزح‪.‬طشوحح‪ S1.‬تحج انجا يؼً‪ .‬شؼثح انشَاضُّح كّهُح انؼهىو وانتكُىنىجٍ‪.‬جايُؼح‬ ‫يىالَا يانك إتشاهُى اإلعاليُّح انحكىيُّح ياالَج‪.‬‬ ‫يششف ‪ .۱ :‬ػثذانشا كشانًاجغتُشفٍ انتشتُّح‬ ‫‪ .۲‬دكتىس انحجّ احًذ تشَض انًاجغتُشفٍ انف ّ‬ ‫ٍ‬ ‫الكلوات الرئيسية‪ :‬قىط قضح‪ ,‬قىط قضح اتصال انحافح‪--‬فُشتكظ‪-‬اتصال‪ ،‬غشاف‪ ،‬ػجالخ عُكُم غشاف‪،‬‬ ‫غشاف‪ ،‬خىرج انؼتاد غشاف‪ ،‬يغطً انخىرج‪ ،‬ػذ غشاف انضهىس‬ ‫فٍ َظشَح انشعى فٍ َظشَح انشعًانثُاٍَ يفهىو انتهىٍَ ًَش تاعتًشاس انتًُُح‪ ،‬أحذ حىل اتصال‬ ‫قىط قضح‪ .‬اتصال قىط قضح تُقغى إنً َىػٍُ‪ ،‬األول هى انجاَة قىط قضح يتصهح ‪ ،‬تًُُا انثاٍَ قىط‬ ‫قضح َقاط يتصهح‪.‬‬ ‫يٍ انحافح اتصال ػهً تىصُم‬ ‫هى أصغشػذد يٍ األنىاٌ انالصيح نجغ ‪ G‬قىط قضح‬ ‫سعًثُاَُهى أصغش ػذد يٍ األنىاٌ ‪ G‬قضح يتصم انشعى انثُاٍَ‪ ،‬فٍ حٍُ أٌ قىط قضح فُشتكظ‬ ‫اتصال ػهً تىصُم سعى تُاَُقضح يتصم انشعى انثُاٍَ‪ ،‬فٍ حٍُ أٌ قىط قضح فُشتكظ‬ ‫اتصال ػهً تىصُم سعى تُاَُهزا انثحج عىف َُاقش حىل فٍ هزا انثحج عىف تُاقش حىل ‪ G‬انالصيح‬ ‫نجؼم يتصم قىط قضح َقطح انشعى انثُاَُاألسقاو واألسقاو ػهً انشُكم‪ ،‬سعى تُاٍَ ػجهح انقُادج‪ ،‬وانؼتاد‬ ‫سعى تُاٍَ‪ ،،‬سعى تُاٍَ انخىر‪ ،‬وخىرج انشعى انثُاٍَ يغهقح‪،‬وانشعى انثُاٍَ انفائذج‪.‬‬ ‫إرا‬ ‫هى‬ ‫اعتُاداً إنيانثحىث انتٍ اكتغثتها أٌ صُغح شائؼح عُكُم غشاف‬ ‫إرا‬ ‫هى‬ ‫‪ .‬فٍ ػذ انؼجهح‬ ‫إنً‬ ‫و ⌉ ⌈‬ ‫‪ .‬فٍ انؼذ وانؼتاد‬ ‫إرا‬ ‫‪ ،‬و‬ ‫إرا‬ ‫‪،‬‬ ‫‪ .‬ػهً‬ ‫إرا‬ ‫‪ .‬فٍ ػذ انخىرج‬ ‫إرا‬ ‫هى‬ ‫‪،‬‬ ‫‪ ،‬إرا‬ ‫كاٌ‬ ‫إرا‬ ‫غشاف خىرج يغهقح‬ ‫و‬ ‫إرا‬ ‫هٍ‬ ‫‪ .‬وفٍ انؼذ نهفائذج‬ ‫إرا‬ ‫و‬ ‫إرا‬ ‫‪،‬‬ ‫إرا‬ ‫‪ .‬تًُُا عُكُم غشاف‬ ‫إرا‬ ‫‪،‬و‬ ‫إرا‬ ‫⌉ ⌈‬ ‫‪،‬‬ ‫إرا‬ ‫‪،‬‬ ‫و‬ ‫إرا‬ ‫⌉ ⌈‬ ‫‪ .‬فٍ انؼذ وانؼتاد‬ ‫إرا‬ ‫إرا‬ ‫‪ .‬فٍ ػذ انخىرج‬ ‫‪،‬‬ ‫إرا كاٌ‬ ‫يغهقح‬ ‫إرا‬ ‫‪ ،‬و‬ ‫‪.‬‬ ‫فٍ هزِ األطشوحح‪َ ،‬شكض انًؤنف فقط ػهً انًىاضُغ راخ انصهح إنً غشاف فٍ عُكُم‪.‬حتً‬ ‫أَهًُكٍ دساعح يغ هزا انُىع يٍ انشعى انثُاٍَ‪.‬‬ ‫فٍ ػذ انؼجهح‬ ‫و‬ ‫إرا‬ ‫إرا‬ ‫‪،‬و‬ ‫‪،‬‬ ‫إرا‬ ‫‪ .‬وفٍ حغاب انفائذج تانُغثح‬

‫‪xviii‬‬

‫‪ ،‬و‬ ‫إرا‬ ‫إرا كاٌ‬ ‫‪ .‬ػهً غشاف خىرج‬ ‫إرا‬ ‫إرا‬

BAB I PENDAHULUAN

1.1 Latar Belakang Galileo Galilie pernah berkata bahwa, Tuhan menciptakan alam raya ini dengan angka (Muftie, 2004:1). Jadi dapat dikatakan bahwa angka mempunyai arti yang sangat penting di dunia ini. Matematika adalah suatu cabang ilmu yang di dalamnya banyak bergelut dengan angka-angka. Matematika juga merupakan salah satu cabang ilmu yang mendasari berbagai macam ilmu yang lain dan selalu menghadapi berbagai macam fenomena yang semakin kompleks. Tetapi masih banyak yang menganggap matematika itu merupakan cabang ilmu yang sulit untuk dipelajari dan harus dihindari. Mempelajari matematika yang sesuai dengan paradigma ulul albab, tidak cukup hanya berbekal kemampuan intektual semata, tetapi perlu didukung secara bersamaan dengan kemampuan emosional dan spiritual. Pola pikir deduktif dan logis dalam matematika juga bergantung pada kemampuan intuitif dan imajinatif serta mengembangkan pendekatan rasionalis, empiris, dan logis (Abdussakir, 2007:24). Sebagaimana dalam firman Allah SWT dalam surat Ali Imran pada ayat 199 yang berbunyi:

     … … Sesungguhnya Allah Amat cepat perhitungan-Nya.” (QS. Ali Imran [3]:199) Sejalan dengan pernyataan Galileo, pada dasarnya konsep matematika sudah ada di dalam alam semesta. Alam semesta menyimpan simbol-simbol pengetahuan yang apabila dikaji secara benar akan menghasilkan konsep-konsep

1

2

ilmu pengetahuan. Jadi kesimpulannya, semua ilmu pengetahuan adalah hasil penyimbolan atas apa yang ada di alam semesta ini. Allah SWT telah menciptakan alam semesta ini dengan ukuran-ukuran cermat dan persamaan yang rapi (Abdussakir, 2007:79-80) Firman Allah dalam surat Al-Jin ayat 28 berbunyi:

              supaya Dia mengetahui, bahwa Sesungguhnya Rasul-rasul itu telah menyampaikan risalah-risalah Tuhannya, sedang (sebenarnya) ilmu-Nya meliputi apa yang ada pada mereka, dan Dia menghitung segala sesuatu satu persatu.(AlJin[72]:28) Dalam surat Maryam ayat 93-94 dijelaskan juga :



              

tidak ada seorangpun di langit dan di bumi, kecuali akan datang kepada Tuhan yang Maha Pemurah selaku seorang hamba. Sesungguhnya Allah telah menentukan jumlah mereka dan menghitung mereka dengan hitungan yang teliti.(Maryam[19]:93-94) Dalam pandangan al-Qur'an, tidak ada peristiwa yang terjadi secara kebetulan. Semua terjadi dengan hitungan, baik dengan hukum-hukum alam yang telah dikenal manusia maupun yang belum. Bagi Muslim yang beriman, tidak ada bedanya apakah al-Qur'an diciptakan dengan hitungan atau tidak, mereka tetap percaya bahwa kitab yang mulia ini berasal dari Tuhan Yang Maha Esa. Pencipta alam semesta, yang mendidik dan memelihara manusia. Namun bagi sebagian ilmuwan, terutama yang Muslim, yang percaya bahwa adanya kodetifikasi alam semesta, baik kitab suci, manusia maupun objek di langit, adalah suatu kepuasan

3

tersendiri jika dapat menemukan hubungan-hubungan tersebut. Al-Qur'an adalah salah satu mahakarya yang diturunkan dari langit, untuk pedoman umat manusia, berlaku hingga alam semesta runtuh. Ia menggambarkan masa lalu, sekarang dan masa depan dengan cara yang menakjubkan. Prof. Palmer seorang ahli kelautan di Amerika Serikat mengatakan "Ilmuwan sebenarnya hanya menegaskan apa yang telah tertulis didalam al-Qur'an beberapa tahun yang lalu" (Muftie, 2004:1). Dalam ayat lain juga disebutkan:

                   

Yang kepunyaan-Nya-lah kerajaan langit dan bumi, dan dia tidak mempunyai anak, dan tidak ada sekutu baginya dalam kekuasaan-Nya, dan dia Telah menciptakan segala sesuatu, dan dia menetapkan ukuran-ukurannya dengan serapi-rapinya” (Q.S. Al-Furqaan:[25]: 2). Ayat di atas menjelaskan bahwa segala sesuatu yang ada di alam ini ada ukurannya, ada hitungan-hitungannya, ada rumusnya, atau ada persamaannya. Ahli matematika atau fisika tidak membuat suatu rumus sedikitpun. Mereka hanya menemukan rumus atau persamaan, sehingga rumus-rumus yang ada sekarang bukan diciptakan manusia sendiri, tetapi sudah disediakan. Manusia hanya menemukan dan menyimbolkan dalam bahasa matematika (Abdussakir, 1997:80). Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tidak kosong dari obyek-obyek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di V yang

4

disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G) (Chartrand dan Lesniak, 1986: 4). Pewarnaan pada graf dari

adalah pemetaan warna-warna ke titik atau sisi

sedemikian hingga titik atau sisi yang terhubung langsung mempunyai

warna-warna yang berbeda. Dikatakan bahwa pewarnaan dari

yang menggunakan

adalah berwarna

jika terdapat

warna. Pewarnaan dengan jumlah warna

minimum yang diperlukan untuk mewarnai graf , disebut bilangan kromatik dari . Ada tiga macam pewarnaan graf, yaitu pewarnaan titik, pewarnaan sisi, dan pewarnaan wilayah (region). Dalam teori graf, konsep pewarnaan terus mengalami perkembangan, salah satunya adalah tentang pelangi terhubung (rainbow connection). Pelangi terhubung dibagi menjadi 2 jenis, yang pertama adalah pelangi sisi terhubung (rainbow edge-connected) yang didefinisikan sebagai pewarnaan sisi pada graf jika setiap titik pada graf

dihubungkan oleh lintasan yang memiliki sisi-sisi

dengan warna yang berbeda, sedangkan yang kedua adalah pelangi titik terhubung (rainbow vertex-connected) yang didefinisikan sebagai pewarnaan titik pada graf jika setiap titik pada graf

dihubungkan oleh lintasan memiliki titik-titik

interior dengan warna yang berbeda. Bilangan pelangi sisi terhubung pada graf terhubung disimbolkan oleh

yaitu bilangan warna terkecil pada sisi yang

dibutuhkan untuk membuat

menjadi pelangi sisi yang terhubung. Sedangkan

bilangan pelangi titik terhubung pada graf terhubung disimbolkan oleh yaitu bilangan warna terkecil pada titik yang dibutuhkan untuk membuat menjadi pelangi titik terhubung (Krivelevich dan Yuster, 2010:1).

5

Dalam penelitian sebelumnya yang ditulis oleh Fuad Adi S. (2012) dalam skripsinya yang berjudul Bilangan Rainbow connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf Bilangan Rainbow connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf, telah dibahas tentang bilangan rainbow connection

dan

pada graf komplit, graf

bipartisi komplit, graf roda, graf kipas dan graf kipas ganda. Sehingga perlu dilakukan penelitian lebih lanjut mengenai objek graf lainnya. Disini penulis akan mengkaji jenis graf lain, yaitu graf sikel, graf roda, graf gear, graf Helm, Graf helm tertutup, dan Graf bunga. Graf ini mempunyai hubungan satu sama lain, yaitu sama-sama mempunyai sikel, dan merupakan pengembangan dari graf sikel. Oleh karena itu, penulis akan mengkaji tentang bilangan pelangi terhubung dengan mengambil judul skripsi “Bilangan Pelangi Terhubung pada Graf yang Berkaitan dengan Sikel”. 1.2 Rumusan Masalah Berdasarkan latar belakang di atas maka rumusan masalah penelitian ini yaitu: 1. connection) connection)

Bagaimana

pola

pelangi

sisi

terhubung

(rainbow

edge-

dan bilangan pelangi titik terhubung (rainbow vertex) pada graf yang berkaitan dengan sikel?

2. Bagaimana bukti dari pola pelangi sisi terhubung (rainbow edgeconnection) connection)

dan bilangan pelangi titik terhubung (rainbow vertex) pada graf yang berkaitan dengan sikel?

6

1.3 Tujuan Berdasarkan rumusan masalah maka tujuan penelitian ini yaitu: 1.

Menjelaskan

connection) connection)

pola

pelangi

sisi

terhubung

(rainbow

edge-

dan bilangan pelangi titik terhubung (rainbow vertex) pada graf yang berkaitan dengan sikel.

2. Menjelaskan bukti dari pola pelangi sisi terhubung (rainbow edgeconnection) connection)

dan bilangan pelangi titik terhubung (rainbow vertex) pada graf yang berkaitan dengan sikel.

1.4 Batasan Masalah Pada penulisan skripsi ini, penulis hanya membatasi penelitian pada pola dan

pada jenis graf sikel, graf roda, graf gear, graf helm, graf helm

tertutup, dan graf bunga. 1.5 Manfaat Penelitian Adapun manfaat penelitian ini adalah: 1. Jurusan Matematika Hasil pembahasan ini dapat digunakan sebagai tambahan bahan dalam pengembangan ilmu matematika khususnya di kalangan mahasiswa Jurusan Matematika. 2. Peneliti Melalui penelitian ini dapat menambah penguasaan materi, sebagai pengalaman dalam melakukan penelitian dan menyusun karya ilmiah dalam bentuk skripsi, serta media untuk mengaplikasikan ilmu matematika yang telah diterima dalam bidang keilmuannya.

7

3. Pengembangan ilmu pengetahuan Menambah khasanah dan mempertegas keilmuan matematika tentang bilangan pelangi terhubung (rainbow connection) pada teori graf, dalam peranannya terhadap perkembangan teknologi dan disiplin ilmu lain. 1.6 Metode Penelitian Metode yang digunakan dalam penelitian ini adalah metode penelitian kepustakaan (library research) atau kajian pustaka, yaitu melakukan penelitian untuk memperoleh data-data dan informasi serta objek masalah yang digunakan dalam pembahasan masalah tersebut. Studi kepustakaan merupakan penampilan argumentasi penalaran keilmuan untuk memaparkan hasil olah pikir mengenai suatu topik kajian kepustakaan yang dibahas dalam penelitian ini. Dengan menggunakan metode ini diharapkan kemampuan analisis dan pemahaman tentang masalah yang diangkat dapat terasah. Dalam penelitian ini penulis menggunakan beberapa langkah strategi. Hal ini dimaksudkan untuk mempermudah penulis dalam memperoleh hasil yang akurat. Adapun langkah-langkah yang digunakan oleh penulis dalam membahas penelitian ini adalah sebagai berikut : 1. Merumuskan masalah yang akan dibahas 2. Mempelajari sumber–sumber dan informasi dengan cara membaca dan memahami literatur yang berkaitan dengan graf roda, graf gear, graf helm, graf helm tertutup, dan graf bunga, serta pewarnaan graf dan pelangi terhubung (rainbow connection) pada graf.

8

3. Menganalisis permasalahan yang telah diperoleh dengan mendeskripsikan permasalahan. Selanjutnya mendapatkan pola dan teorema yang dibuktikan. Langkah-langkah analisis: a. Menggambar graf-graf tersebut satu-persatu dengan order mulai dari 1 sampai 7 hingga didapatkan pola dari bilangan pelangi sisi terhubung (rainbow edge-connection) (rainbow vertex-connection) tentang

dan

dan bilangan pelangi titik terhubung ) sehingga dapat diperoleh pola

) terhadap graf-graf tersebut

b. Membuktikan teorema tentang bilangan pelangi sisi terhubung (rainbow edge-connection) vertex-connection)

dan bilangan pelangi titik terhubung (rainbow ) yang telah diperoleh dari pola di atas

c. Menganalisis bilangan pelangi sisi terhubung (rainbow edgeconnection) vertex-connection)

dan bilangan pelangi titik terhubung (rainbow ) pada graf roda, graf gear, graf helm, graf

helm tertutup, dan graf bunga dengan menghubungkan teorema yang telah didapatkan pada langkah sebelumnya, sehingga diperoleh teorema secara umum. d. Membuktikan teorema umum tersebut. 4. Merumuskan kesimpulan dari hasil analisis teorema buktikan. 5. Menyusun laporan dari penelitian dalam bentuk tugas akhir.

yang telah di

9

1.7 Sistematika Penulisan Sistematika penulisan di sini terdiri dari empat bab dan masing-masing bab dibagi menjadi beberapa subbab dengan sistematika sebagai berikut: Bab I Pendahuluan Berisi latar belakang, rumusan masalah, tujuan, batasan masalah, manfaat penelitian, metode penelitian, dan sistematika penulisan. Bab II Kajian Pustaka Bab kedua menguraikan kajian tentang teori yang berkaitan dengan pembahasan, antara lain pengertian graf, macam-macam jenis graf, dan bilangan pelangi terhubung (rainbow connection). Kajian Agama Islam tentang pelangi terhubung (rainbow connection) dibahas juga dalam bab ini.. Bab III Pembahasan penulis mengkaji tentang pembahasan yang terdiri dari bagaimana menentukan teorema tentang bilangan pelangi terhubung (rainbow connection) pada graf yang berkaitan dengan sikel kemudian membuktikannya. Kemudian menentukan teorema umum atas graf yang berkaitan dengan sikel. BAB IV Penutup Bab ini berisi tentang kesimpulan dari hasil penelitian dan saran sebagai acuan bagi peneliti yang lain.

BAB II KAJIAN PUSTAKA 2.1

Graf Menurut catatan sejarah, awal munculnya konsep graf adalah pada tahun

1936 yaitu di Kota Konigsberg (salah satu kota di Jerman). Di kota Konigsberg tersebut terdapat sungai Pregal yang bercabang dan memisahkan beberapa blok/lokasi di kota tersebut, sehingga di sana dibangun tujuh jembatan sebagai penghubungnya (Saondi, 2003:1). Awal permasalahannya adalah apakah mungkin melalui ketujuh jembatan tersebut masing-masing satu kali dan kembali ke tempat semula. Hingga akhirnya seorang matematikawan Swiss, Leonardo Euler merupakan orang pertama yang dapat memecahkan permasalahan tersebut dengan pembuktian yang sederhana. Inilah yang menjadi tonggak sejarah munculnya teori graf (Saondi, 2003:1). Teori graf merupakan salah satu bidang dalam disiplin ilmu matematika yang sampai sekarang masih terus dikaji karena memang tidak sedikit permasalahan yang dapat dipecahkan dengan menggunakan teori graf. Definisi Graf G adalah pasangan himpunan (V, E) dengan V adalah himpunan tidak kosong dan berhingga dari obyek-obyek yang disebut sebagai titik dan E adalah himpunan (mungkin kosong) pasangan tak berurutan dari titik-titik berbeda di G yang disebut sebagai sisi. Himpunan titik di G dinotasikan dengan V(G) dan himpunan sisi dinotasikan dengan E(G). Sedangkan banyaknya unsur di V disebut order dari G dan dilambangkan dengan p(G)

10

11

dan banyaknya unsur di E disebut ukuran dari G dan dilambangkan dengan q(G). Jika graf yang dibicarakan hanya graf G, maka order dan ukuran dari G tersebut cukup ditulis dengan p dan q (Chartrand dan Lesniak, 1986:4). Sebagai (

+

*

contoh

(

misal

+. Maka

)

*

+

dan

dapat digambarkan sebagai berikut : v2

G1

e1

v4

e2

v1

e3 v3

Gambar 2.1 graf

2.2

Terhubung Langsung dan Terkait Langsung

Definisi Sisi e = (u, v) dikatakan menghubungkan titik u dan v. Jika e = (u, v) adalah sisi di graf G, maka u dan v disebut terhubung langsung (adjacent), u dan e serta v dan e disebut terkait langsung (incident). Untuk selanjutnya, sisi e = (u,v) akan ditulis e = uv (Chartrand dan Lesniak, 1986:4). Perhatikan gambar berikut : v1 e4 e1 v2

e5

v4

e2 e3

v3

Gambar 2.2 graf G

12

Dari gambar 2.2 pada graf G, sisi e1,e5 dan e4 adalah terkait langsung (incident) dengan titik v1. Sedangkan titik v1 dan v4 adalah terhubung langsung (adjacent) tetapi v4 dan v2 tidak. 2.3

Jalan, Lintasan, Jejak, dan Sirkuit Misalkan

graf. Misalkan juga

berbeda). Jalan u-v pada graf

dan

adalah titik di

(yang tidak harus

adalah barisan berhingga yang berselang seling

antara titik dan sisi, yang dimulai dari titik dan diakhiri dengan titik dengan: dengan adalah sisi di

.

sebagai titik awal, dan

adalah titik internal, dan maka

sebagai

titik akhir, titik

menyatakan panjang dari

disebut jalan terbuka. Jika

maka

. Jika

disebut jalan

tertutup (Abdussakir, dkk, 2009:49). Perhatikan gambar graf berikut:

v1 v4

v2

v3 G2

Gambar 2.3 Graf

Pada gambar graf

sebelah kiri, terlihat bahwa gambar tersebut hanya

memuat satu sisi yang menghubungkan dua titik. Lintasan merupakan lintasan dengan barisan sisi (

)(

)(

).

13

Jalan

yang semua sisinya berbeda disebut jejak (trail). Jalan terbuka

yang semua titiknya berbeda disebut lintasan. Dengan demikian setiap lintasan adalah trail, tetapi tidak semua trail adalah lintasan. Pada graf

a

c

W1 = a, c, e, b, d, f W2 = a, e

e

f

b

berikut :

d

W3 W4 W5 W6

= a, e, b, d = a, c, e, b, d, f, d, e, a = a, e, b, e, c = f, c, a, e, b, d, e, c, d, f

Gambar 2.4 Lintasan Graf

Jalan di

;

dan

adalah lintasan

karena semua titiknya berbeda. Sedangkan

dan

bukan merupakan lintasan karena ada titik yang sama (Abdussakir, 2009:51-52). Dan

adalah jalan tertutup

dan merupakan trail karena semua sisinya berbeda. Jalan tertutup

tak trivial yang semua sisinya berbeda disebut sirkuit.

Dengan kata lain, sirkuit adalah jejak (trail) tertutup yang tak trivial. Perhatikan graf

berikut :

a

c W1  a, e, b, d , e, c, a

e

b

f

W2  a, e, b, d , e, d , c, a

d Gambar 2.5 Sirkuit dan Jejak (trail) Graf

14

Jalan

adalah jalan tertutup, dan merupakan trail

karena semua sisinya berbeda. Jadi

adalah sirkuit dan

adalah jalan tertutup dan bukan trail karena Dengan demikian

dilalui lebih dari satu kali.

bukan sirkuit.

Jalan tertutup tak trivial yang semua titiknya berbeda disebut sikel. Dengan demikian setiap sikel pasti merupakan sirkuit, tetapi tidak semua sirkuit merupakan sikel. Misalkan

dan

titik berbeda pada graf

dikatakan terhubung jika terdapat lintasan

ke

, titik

dan

di .

Chartrand dan Oellerman (1993:21) mendefinisikan suatu graf terhubung (connected) jika untuk setiap titik

dan

di

terdapat lintasan yang

menghubungkan kedua titik tersebut. Sedangkan apabila terdapat dua titik pada graf

yang tidak dihubungkan oleh suatu lintasan, maka graf

dinamakan graf

tak terhubung (disconnected). 2.4

Derajat Suatu Titik

Definisi Derajat suatu titik v pada sebuah graf G, ditulis dengan deg(v), adalah jumlah sisi yang terkait langsung (incident) pada v. Dengan kata lain, jumlah sisi yang memuat v sebagai titik ujung. Titik v dikatakan genap atau ganjil tergantung dari jumlah deg(v) genap atau ganjil (Chartrand dan Lesniak, 1986: 8).

15

Perhatikan gambar berikut : v3

v4

2

1

2 v2 3

v1

Gambar 2.6 Graf dengan derajat titik

Teorema 1 p

Jika G graf V(G) = { v1, v2, ..., vn} maka

 deg i 1

G

(vi )  2q (Chartrand dan

Lesniak, 1986: 7) Bukti: Setiap sisi adalah terkait langsung dengan 2 titik jika setiap derajat titik dijumlahkan, maka setiap sisi dihitung dua kali. Akibat 1. Pada sebarang graf, banyaknya titik ganjil adalah genap. Bukti: Misalkan graf G dengan ukuran q. Maka ambil W yang memuat himpunan titik ganjil pada G serta U yang memuat himpunan titik genap di G. Dari teorema 1 maka diperoleh:

 deg

vv ( G )

G

v   deg G v   deg G v  2q vW

dengan demikian karena

vU



vU

deg G v genap, maka

genap. Sehingga |W| adalah genap.



vW

degG v juga --

16

2.5

Operasi Pada Graf

2.5.1

Gabungan Graf (Union Graph) Definisi Misal

dan

graf. Union graph atau graf gabungan dari

ditulis ( )

adalah graf dengan (

)

(

). Jika graf

maka ditulis

( )

(

terdiri atas

)

kali graf

dan (

,

) dan ,

,

(Purwanto, 1998:25).

Definisi 6 Penjumlahan dua graf

dan ( )

mempunyai himpunan titik ( )

(

)

(

)

yang dinotasikan ( (

*

)

)

(

) dan himpunan sisi (

)+ (Chartrand dan

Lesniak, 1986: 11). Berikut contoh operasi gabungan pada graf:

Gambar 2.7 Graf

2.5.2

Penjumlahan Graf (Joint Graph) Definisi Misal

dan

ditulis (

)

graf. Joint graph atau penjumlahan graf dari ( )

, adalah graf dengan graf dengan dan

( )

(Purwanto, 1998:26).

(

)

(

)

*

(

)

dan (

, )

(

)+

17

Berikut akan ditunjukkan penjumlahan graf

, dengan

adalah

graf lintasan (graf yang berbentuk garis yang terdiri dari 3 titik) seperti pada gambar di bawah (graf

), dan

yaitu graf komplit (graf dengan dua titik yang

berbeda yang saling terhubung langsung) seperti gambar di bawah (graf

)

(Chartrand dan Oellerman, 1993:29)

A

A+ B

B

Gambar 2.8 Penjumlahan Dua Graf

2.6

Macam-Macam Graf Graf memiliki jenis yang bermacam macam, tergantung dari sudut mana

memandangnya. Berdasarkan titik, sisi, dan derajatnya, terdapat beberapa jenis graf sebagai berikut: 2.6.1

Graf Komplit Definisi Graf komplit adalah graf yang setiap dua titik yang berbeda saling terhubung langsung. Graf komplit dengan

titik dinotasikan dengan

(Wilson dan Watkins, 1989:36). Berikut adalah gambar graf komplit mulai

K1

K2

K3

sampai

K4

Gambar 2.9 Graf Komplit

:

K5

18

2.6.2

Graf Sikel Definisi Chartrand dan Lesniak (1986:28) mendefinisikan graf sikel graf terhubung beraturan 2 yang mempunyai

titik (

Berikut adalah gambar graf sikel mulai dari v1

sampai

v1

v1

v2

v4

C3

) dan :

v2

v3

sisi.

v1

v5

v3

sebagai

vn

v2

v n 1

v3

v2

v4

C4

v3

v4

C5

Cn


2.6.3

Graf Bipartisi Definisi Graf

dikatakan bipartisi jika himpunan titik pada

menjadi dua himpunan tak kosong

dan

sehingga masing-masing sisi

pada graf

tersebut menghubungkan satu titik di

. Jika

adalah graf bipartisi beraturan- dengan

. Graf

dikatakan partisi-

menjadi sebanyak

dapat dipartisi

dengan satu titik di , maka

jika himpunan titiknya dapat dipartisi

himpunan tak kosong

sehingga masing-

masing sisi pada graf

menghubungkan titik pada

untuk

, maka graf partisi- disebut tripartisi (Abdussakir,

. Jika

dkk, 2009:21-22).

dengan titik pada

,

19

Graf bipartisi komplit (complete bipartite graph) adalah graf bipartisi dengan himpunan partisi

dan

sehingga masing-masing titik di

dihubungkan dengan masing-masing titik di dan

oleh tepat satu sisi. Jika

, maka graf bipartisi tersebut dinyatakan dengan

(Purwanto, 1998:22). Berikut adalah contoh gambar graf bipartisi komplit :

K 2,3

K 3, 3

K 2, 4

Gambar 2.11 Graf Bipartisi

2.6.4

Graf Roda Definisi Graf roda adalah graf yang dibentuk dari operasi joint graf antara graf sikel ( dengan

) dan graf komplit dengan satu titik ( untuk

). Graf roda dinotasikan

.

Berikut ini adalah gambar dari graf roda :

W3

W4 Gambar 2.12 Graf Roda

W5

20

2.6.5

Graf Helm Definisi Graf Helm Hn adalah graf yang didapatkan dari sebuah graf roda dengan menambahkan sisi anting-anting pada setiap titik di sikel (Gallian, 2007:7). Berikut ini adalah gambar dari Graf Helm :

H3

H4

H5


2.6.6

Graf Helm Tertutup Definisi Graf helm tertutup

adalah graf yang diperoleh dari sebuah graf helm

dengan menghubungkan setiap titik pada anting-anting untuk membentuk sikel (Gallian, 2007:7). Berikut adalah contoh gambar graf helm tertutup:

cH 3

cH 4 Gambar 2.14 Graf Helm Tertutup

cH 5

21

2.6.7

Graf Gear Definisi Graf gear adalah graf yang diperoleh dari graf roda dengan tambahan satu titik di antara tiap-tiap pasangan titik pada sikel luar (Gallian, 2007:7).

Berikut adalah contoh gambar graf gear :


2.6.8

Graf Bunga Definisi Graf Bunga adalah graf yang diperoleh dari graf helm dengan menghubungkan tiap-tiap titik anting-anting ke titik pusat dari graf Helm (Gallian, 2007:7). Berikut adalah contoh dari graf bunga :

F3

F4 Gambar 2.16 Graf Bunga

2.7

Pewarnaan pada Graf Pewarnaan pada graf dibedakan menjadi tiga, pewarnaan titik, pewarnaan

sisi dan pewarnaan peta.

22

2.7.1

Pewarnaan Titik (Vertex Colouring) Definisi Pewarnaan titik dari graf G adalah sebuah pemetaan warna-warna ke titiktitik dari G sedemikian hingga titik yang terhubung langsung mempunyai warna-warna yang berbeda. Graf G berwarna n jika terdapat sebuah pewarnaan dari G yang menggunakan n warna (Hasanah, 2007:20). Dalam pewarnaan titik erat kaitannya dengan penentuan bilangan

kromatik, yaitu masalah menentukan banyak warna minimum yang diperlukan untuk mewarnai titik-titik pada graf sehingga dua titik yang terhubung langsung mempunyai warna yang berbeda. Bilangan kromatik (chromatic number) dari graf G, dinyatakan dengan  (G), adalah bilangan k terkecil sehingga G dapat diwarnai dengan k warna. Biasanya warna-warna yang digunakan untuk mewarnai suatu graf dinyatakan dengan 1, 2, 3, …, k. Jelas bahwa  (G)  V G  (Purwanto, 1998:7). Beberapa graf tertentu dapat langsung ditentukan bilangan kromatiknya. Graf kosong N n memiliki  (G)  1. Karena semua titik tidak terhubung, jadi untuk mewarnai semua titik cukup dibutuhkan satu warna saja. Graf lengkap K n memiliki  (G)  n sebab semua titik saling terhubung sehingga diperlukan n warna (Hasanah, 2007: 20). Contoh Perhatikan gambar 2.17, untuk graf G1, karena V G1  = 3, maka  (G1)  3. Untuk G2, karena V G2  = 4, maka  (G1)  4. Karena semua titik

23 pada G1 dan G2 saling terhubung langsung, akibatnya  (G1)  3 dan  (G1)  4. Jadi,  (G1) = 3 dan  (G2) = 4. Untuk graf G3,  (G3)  3, karena 3 warna untuk mewarnainya seperti pada gambar. Karena graf G3 memuat graf Komplit K3, maka  (G3)  3, akibatnya  (G3) = 3. 1 1

1

2

3

3

2

2

3

4

3

2

Gambar 2.17 Pewarnaan titik

2.7.2

Pewarnaan Sisi (Edge Coloring) Definisi Suatu pewarnaan sisi-k untuk graf g adalah suatu penggunaan sebagian atau semua k warna untuk mewarnai semua sisi di G sehingga setiap pasang sisi yang mempunyai titik persekutuan diberi warna yang berbeda. Jika G mempunyai pewarnaan sisi-k, maka dikatakan sisi-sisi di G diwarnai dengan k warna (Purwanto, 1998:80). Contoh : 3 1

2

1

1

2

2

1

3 3

3

4

2

3

2

1

4

Gambar 2.18 Pewarnaan Sisi

2.8

Pelangi Terhubung (Rainbow Connection) Definisi Pewarnaan sisi pada graf

disebut pelangi sisi terhubung (rainbow edge-

connected) jika setiap titik pada graf

dihubungkan oleh lintasan yang

24

memiliki sisi-sisi dengan warna yang berbeda. Pelangi terhubung (Rainbow connection) pada graf

yang terhubung (connected graph)

( ) yaitu bilangan terkecil dari warna yang

disimbolkan oleh

dibutuhkan untuk membuat graf G

menjadi pelangi sisi terhubung

(rainbow edge-connected) (Krivelevich dan Yuster, 2010:1). Lintasan pelangi (rainbow path) adalah lintasan antara dua titik sehingga tidak ada dua sisi pada lintasan tersebut yang memiliki warna yang sama. Jika lintasan pelangi tersebut ada di setiap antara dua titik maka pewarnaan tersebut dinamakan pewarnaan pelangi (rainbow colouring). Sedangkan bilangan minimum pada warna yang diinginkan dinamakan bilangan pelangi yang terhubung (rainbow connection number rc(G)) (Chandran, 2011:3). Definisi Pewarnaan titik pada graf

adalah Pelangi titik terhubung (rainbow

vertex-connected) jika setiap titik pada graf

dihubungkan oleh lintasan

memiliki titik-titik interior dengan warna yang berbeda. Rainbow vertexconnection pada graf oleh

yang terhubung (connected graph) disimbolkan

( ) yaitu bilangan terkecil dari warna yang dibutuhkan untuk

membuat graf G

menjadi pelangi titik terhubung (rainbow vertex-

connected) (Krivelevich dan Yuster, 2010:2). Misalkan graf graf sikel dengan

memiliki

dengan ( ), maka

maka ( )

(Krivelevich dan Yuster, 2010:1-2).

titik, maka ( )

( )

. Kemudian jika

, -. Sedangkan jika dihubungkan ( ) dan

( )

( )

25

Contoh : 𝟏 1

1

𝟏

𝟐

2

1

3

3

𝟏

𝟐

3

𝟑

4

5

5

𝟐

𝟑

5

𝟑

Gambar 2.19 Pelangi Terhubung (Rainbow Connection)

Gambar 2.19 merupakan contoh dari graf pelangi sisi terhubung dan pelangi titik terhubung dengan 5 warna sisi dan 3 warna titik. Pada gambar di atas mempunyai bilangan 2.9

( )

dan

( )

.

Relevansi Pelangi Terhubung (Rainbow Connection) pada Graf dalam Kajian Agama Islam Inti dari teori graf adalah titik dan sisi, dimana titik-titik itu bisa

diasumsikan sebagai suatu cara untuk mencari sebuah solusi dala menyelesaikan masalah. Jika dua titik pada suatu graf diasumsikan sebagai suatu benda dan dihubungkan dengan suatu sisi, maka hal ini memiliki artian bahwa dua benda tersebut mempunyai suatu hubungan tertentu. Jika dua titik dalam suatu graf diasumsikan sebagai suatu kejadian dan dihubungkan dengan suatu sisi, maka dapat diambil suatu pengertian bahwa ada dua kejadian yang mempunyai hubungan. Dalam Islam dikenal peristiwa Isra’ Mi’raj, Isra’ merupakan perjalanan suci yang dilakukan oleh Nabi Muhammad SAW dari Masjidil Haram menuju Masjidil Aqsha, sedangkan Mi’raj adalah perjalanan suci Nabi Muhammad SAW dari Masjidil Aqsha menuju Sidrotul Muntaha (langit ke-7). Berdasarkan kisah

26

tersebut dapat kita masukkan dalam teori graf, karena dalam perjalanan Nabi dari Mekkah sampai Sidrotul Muntaha ditemukan adanya titik (vertex) dan lintasan yang dilalui Nabi SAW dalam perjalanannya merupakan sisi atau garis (edge). Sehingga dapat kita katakan kisah isra’ mi’raj masuk dalam teori graf. Kejadian perjalanan Nabi saw dari Masjidil Haram menuju Masjidil Aqsha dijelaskan oleh Allah dalam surat Al-Israa’ ayat 1 yang berbunyi :

                       Maha suci Allah, yang telah memperjalankan hamba-Nya pada suatu malam dari Al Masjidil Haram ke Al Masjidil Aqsha yang telah Kami berkahi sekelilingnya agar Kami perlihatkan kepadanya sebagian dari tanda-tanda (kebesaran) kami. Sesungguhnya Dia adalah Maha mendengar lagi Maha mengetahui (Q.S. AlIsraa’:[17]:1). Pada surat di atas, merupakan isyarat Nabi SAW untuk isra’, kata isrâ secara harfiah selalu diterjemahkan dengan “perjalanan di malam hari”. Padahal, kata isrâ’ itu sendiri, kalau dirujuk ke kata dasar Arabnya bisa bermakna “sebuah pencarian”. Kata sâriyah yang satu dasar kata dengan isrâ’ berarti pencarian. Jadi isrâ’ di

sini bisa berarti

“proses pencarian

yang

melepaskan diri seseorang dari kegelapan hidup”. Peristiwa Isra’ digambarkan sebagai berikut : Keterangan: a. Masjidil Haram Mekkah

a

c

b b. Masjidil Aqsha Palestina c. Peristiwa Isra’ Gambar 2.20 Isra’

akan

27

Dari gambar 2.20 terlihat ada dua titik yang dihubungkan oleh satu sisi, kedua titik itu adalah Masjidil Haram dan Masjidil Aqsha, sedangkan sisi yang menghubungkan adalah peristiwa atau proses perjalanan Nabi saw yaitu Isra’. Sedangkan kejadian perjalanan Nabi SAW dari Masjidil Aqsha menuju sidrotul Muntaha atau Mi’raj dijelaskan oleh Allah dalam surat Al-Najm ayat 1318 yang berbunyi :

                                dan Sesungguhnya Muhammad telah melihat Jibril itu (dalam rupanya yang asli) pada waktu yang lain, (yaitu) di Sidratil Muntaha. Di dekatnya ada syurga tempat tinggal, (Muhammad melihat Jibril) ketika Sidratil Muntaha diliputi oleh sesuatu yang meliputinya. Penglihatannya (Muhammad) tidak berpaling dari yang dilihatnya itu dan tidak (pula) melampauinya. Sesungguhnya Dia telah melihat sebahagian tanda-tanda (kekuasaan) Tuhannya yang paling besar (Q.S. AlNajm:[53]:13-18). Ayat-ayat ini menjelaskan benar bahwa beliau telah sampai ke Sidratul Muntaha, yang lebih tinggi lagi dari langit. Bertemu di sana Jibril AS dalam keadaan yang asli, penglihatannya yang pertama ialah di Gua Hira’. Adapun di waktu-waktu yang lain, beliau tidak melihat Jibril AS menurut bentuk aslinya walaupun dia datang membawa wahyu.

28

Penggambaran peristiwa Mi’raj tersebut adalah sebagai berikut : Keterangan:

d

a. Sidratul Muntaha

f

b. Masjidil Aqsha c. Peristiwa Mi’raj

e Gambar 2.21 Peristiwa Mi’raj

Dari gambar 2.21 ada dua titik yang dihubungkan oleh satu sisi, kedua titik itu adalah Masjidil Aqsha dan Sidrotul Muntaha, sedangkan sisi yang menghubungkan adalah peristiwa atau proses perjalanan Nabi SAW yaitu Mi’raj. Sedangkan peristiwa Isra’ Mi’raj dapat digambarkan sebagai berikut : Keterangan: a. Masjidil Haram

c f

e

b. Masjidil Aqsha c. Sidratul Muntaha d. Isra’

a

d

b

e. Mi’raj f.

Perjalanan Nabi SAW dari Sidratul Muntaha Ke Masjidil Haram

Gambar 2.22 peristiwa Isra’ Mi’raj

Dari gambar 2.22 dihasilkan suatu graf sikel yang mempunya 3 titik dan 3 sisi. Ketiga titik itu adalah, titik pertama merupakan tempat awal Nabi SAW yaitu Masjidil Haram, titik kedua adalah Masjidil Aqsha, sedangkan titik ketiga adalah Sidrotul Muntaha. Sedangkan untuk sisi-sisinya adalah, sisi pertama yaitu

29 Isra’ yang dimaknai sebagai perjalanan Nabi SAW dari Masjidil Haram menuju Masjidil Aqsha, sedangkan sisi kedua dimakanai sebagai Mi’raj yaitu perjalanan Nabi SAW dari Masjidil Aqsha menuju Sidrotul Muntaha, dan sisi yang terakhir adalah perjalanan Nabi SAW dari Sidrotul Munatah kembali ke Masjidil Haram. Dengan demikian pelangi sisi terhubung (rainbow edge-connection) dan pelangi titik terhubung (rainbow vertex-connection) dapat diaplikasikan dalam ajaran Islam, seperti dalam peristiwa Isra’ Mi’raj tersebut, dimana titik yang dilabelkan sebagai tempat kejadian dan sisi yang dilabelkan sebagai proses kejadian atau perjalanan Nabi SAW.

BAB III PEMBAHASAN Pada bab ini, akan dibahas mengenai bilangan pelangi sisi terhubung (rainbow edge-connection) dan pelangi titik terhubung (rainbow vertexconnection) pada graf yang berkaitan dengan graf sikel. Yaitu antara lain graf sikel, graf roda, graf gear, graf helm, graf helm tertutup, dan graf bunga. Pewarnaan sisi pada graf dua titik pada graf

disebut pelangi sisi yang terhubung jika setiap

dihubungkan oleh lintasan yang memiliki sisi-sisi dengan

warna yang berbeda. Bilangan pelangi sisi terhubung pada graf disimbolkan oleh

yang terhubung

yaitu bilangan terkecil dari warna yang dibutuhkan untuk

membuat graf G menjadi pelangi sisi terhubung. Pewarnaan titik pada graf dua titik pada graf

adalah pelangi titik yang terhubung jika setiap

dihubungkan oleh lintasan memiliki titik-titik interior dengan

warna yang berbeda. Bilangan pelangi titik terhubung pada graf disimbolkan oleh

yang terhubung

yaitu bilangan terkecil dari warna yang dibutuhkan

untuk membuat graf G menjadi pelangi titik terhubung. 3.1

Graf Sikel Graf sikel

2. Misal graf sikel

adalah graf terhubung n titik yang setiap titiknya berderajat mempunyai himpunan titik

, maka

graf tersebut mempunyai himpunan sisi untuk setiap

,

Bilangan pelangi sisi terhubung ( terhubung (

, dimana . ) dan bilangan pelangi titik

) pada graf sikel dapat ditentukan dengan menggambar pola

30

31

graf sikel

, graf

dan

, graf

, graf

, dan graf

pada graf sikel

. Kemudian menggambar pola

. Dari pola tersebut selanjutnya dapat

disimpulkan bilangan pelangi sisi terhubung dan pelangi titik terhubung pada graf sikel

. 1

1

C :

1

1

2

3

Gambar 3.1 Graf sikel

Pada graf 3 sisi yaitu sisi

terdapat 3 titik yaitu , sisi

,

, dan

. Graf ini juga mempunyai

, dan sisi

. Langkah pertama untuk

mencari bilangan pelangi sisi terhubung adalah. Ambil lintasan lewat dari , ,

maka lintasan itu menjadi ke

tanpa melewati

,

ke

, bila

, . Karena dapat melewati langsung

, maka sisi

diwarna 1, sehingga lintasan

dapat diabaikan. Dengan cara yang sama dapat diterapkan pada sisi dan sisi

. Sehingga terbukti bahwa

.

Sedangkan untuk bilangan pelangi titik terhubung, pada graf titik terhubung langsung, sehingga tidak memiliki warna titik. Jadi 11

𝑪𝟒 :

1

1

2

41

2

2 1

1


3

semua .

32

Pada graf adalah

,

dapat melalui Ketika melewati warna 1 pada sisi

terdapat 4 titik dan juga 4 sisi. Misalkan sisi-sisi pada graf dengan

,4, ambil lintasan

ke

sehingga lintasannya menjadi

, lintasan ini

dengan jarak 2 sisi.

lintasan ini juga memiliki jarak 2 sisi, yaitu , maka sisi

. Beri

haruslah diwarna 2. Ketika lewat

dengan cara yang sama akan didapatkan hasil yang sama. Sehingga untuk memperoleh bilangan pelangi sisi terhubung dibutuhkan minimal 2 warna berbeda. Jadi terbukti bahwa

.

Sedangkan agar terbentuk pelangi titik yang terhubung, di mana setiap antara dua titik pada graf

terdapat lintasan dengan warna titik interior yang

berbeda, cukup dibutuhkan satu warna titik. Misalnya ambil titik 1 dan

diberi warna 1, sehingga setiap lintasan

dimana

, sedangkan setiap lintasan

dimana

. Sehingga terbukti

diberi warna

akan melewati titik akan melewati titik

. 1

3

𝑪𝟓 :

1

1 2

5

2

2

4

1

1 3


Pada graf adalah

,


maka lintasan ini menjadi

,4,5, ambil lintasan

ke

, bila lewat

, sedangkan bila melewati

dan

33

maka lintasan ini menjadi warna 1 pada sisi

. Ambil lintasan , dan warna 2 pada sisi

pelangi sisi terhubung pada lintasan , ketika sisi

, beri ini akan membuat

. Sedangakan pada lintasan diwarna 1 dan

diwarna 2 maka

untuk membuat pelangi sisi terhubung haruslah sisi

diberi warna 3,

karena sisi

sudah berwarna 1 dan sisi

berwarna 2. Sehingga

diperlukan minimal 3 warna yang berbeda untuk membuat pelangi sisi terhubung pada graf

. Jadi terbukti bahwa

.



berbeda, cukup dibutuhkan satu warna titik. Misalnya ambil titik 1 dan

diberi warna 1, sehingga setiap lintasan

dimana


dimana

. Sehingga terbukti

diberi warna

akan melewati titik akan melewati titik

. 1

1

3 6

𝑪𝟔 :

1

2

2

1

1

2 5

2

2

1

2

3

3

4


Pada graf adalah

,


,4,5,6, ambil lintasan

ke

, melalu

sisi manapun pada lintasan ini akan melewati 3 sisi. Misalnya pada lintasan

34

, lintasan ini akan melewati sisi-sisi yaitu, sisi , dan sisi

, sisi

. Sedangkan pada lintasan

akan melewati sisi-sisi yaitu, sisi

, lintasan ini

, sisi

, dan sisi

. Maka

untuk pelangi sisi terhubung minimal dibutuhkan 3 warna yang berbeda. Misalkan beri warna 1 pada sisi

, warna 2 pada sisi

, maka lintasan

, dan warna 3 pada sisi

merupakan lintasan pelangi. Dengan

menggunakan cara yang sama lintasan pelangi. Jadi terbukti bahwa

merupakan lintasan

.



berbeda, dibutuhkan dua warna titik. Misalkan pewarnaan titik

dari

menggunakan 2 warna, dua titik yang berdekatan (misal

dan

warna yang berbeda, ini akan membuat lintasan

yang melalui titik

dan

ke

) mempunyai

menjadi lintasan pelangi. Sehingga untuk memperoleh bilangan pelangi

titik terhubung dibutuhkan minimal 2 warna berbeda. Jadi terbukti bahwa . 4 7

1

1

1

2

2

3

𝑪𝟕 : 3 6

2 1

3

2 5

3

1

2 1


4

3

35

Pada graf adalah

terdapat 7 titik dan juga 7 sisi. Misalkan sisi-sisi pada graf

,

dengan

titik

,7. Ambil lintasan

ke

maka lintasannya menjadi

. Karena dapat

melewati lintasan pendek yaitu lintasan , warna 2 pada sisi membuat lintasan

bila lewat

, beri warna 1 pada sisi

), dan warna 3 pada sisi

ini akan

menjadi pelangi sisi terhubung. Namun ketika

lintasan

diberi warna dengan menggunakan cara yang sama

misalnya sisi

diberi warna 1, sisi

diberi warna 3, maka sisi

tidak mungkin diberi warna 1 atau 2, karena ini

mengakibatkan pada lintasan Maka haruslah sisi

diberi warna 2, dan sisi

) tidak terdapat lintasan pelangi.

diberi warna 4 agar terbentuk pelangi sisi terhubung.

Sehingga untuk memperoleh bilangan pelangi sisi terhubung dibutuhkan minimal 4 warna berbeda. Jadi terbukti bahwa

.



berbeda, dibutuhkan 3 warna titik. Misalnya pewarnaan titik

dari

menggunakan 2 warna, ini mengakibatkan ada dua titik yang berdekatan mempunyai warna yang sama. sehingga dua lintasan yaitu dan

pada

bukanlah lintasan

pelangi, dengan kata lain tidak ada lintasan pelangi diantara

dan

. Oleh

karena itu dibutuhkan minimal 3 warna titik yang berbeda. Jadi terbukti .

36

Tabel 3.1 Pola Bilangan No 1 2 3 4 5

dan

pada

sampai

Jenis Graf 1 2 2 3 4

0 1 1 2 3

⌈ ⌉ ⌈ ⌉ ⌈ ⌉ Dari pola yang ditunjukan oleh bilangan pelangi sisi terhubung (rainbow edge-connection) dan bilangan pelangi titik terhubung (rainbow vertexconnection) di atas dapat diperoleh teorema sebagai berikut: Teorema 1 Graf sikel

dengan jumlah titik

, maka bilangan pelangi sisi

terhubung (rainbow edge-connection) adalah: {

⌈ ⌉

Bilangan pelangi titik terhubung (rainbow vertex-connection) adalah:

.

⌈ ⌉ {

⌈ ⌉

(Li dan Liu, 2011:3).

37

Bukti Graf Sikel

adalah graf terhubung

titik yang setiap titiknya berderajat

2. Misalkan

lalu untuk setiap

kita berikan

dengan

.

1. Bilangan pelangi sisi terhubung (rainbow edge-connection) a.

jika Ambil lintasan

ke

, bila lewat

maka lintasan itu menjadi

, . Karena dapat melewati langsung dari , maka sisi

ke

,

tanpa melewati

diwarna 1, sehingga lintasan

,

,

dapat

diabaikan. Dengan cara yang sama dapat diterapkan pada sisi dan sisi

. Sehingga terbukti bahwa

.

⌈ ⌉ jika

b.

Anggap terdapat dua kasus, yaitu

genap dan

Untuk

genap, misalkan

dimana

sikel

yaitu

dari

ganjil. . Maka diameter graf

. Misalnya didefinisikan pewarnaan sisi dengan

untuk

dan

, ini menunjukkan bahwa

jika dan juga

. Untuk

ganjil, misalkan

pertama pewarnaan sisi dan

jika .

dimana dari

adalah

. Misalkan definisi untuk

. Ini menunjukkan

38

Selanjutnya ambil diberikan dan

asumsi

kebalikannya,

misalnya

merupakan pewarnaan pelangi sisi terhubung dari

merupakan titik yang bertolak belakang dari

pada

, , lalu

. Lintasan

merupakan lintasan pelangi, sedangkan lintasan

pada

yang lain bukan lintasan pelangi karena mempunyai panjang . Misalnya pada sisi Ambil titik

.

, dan

. Lintasan

ke

yang melewati titik

merupakan lintasan pelangi, misalnya lintasan ini diberi nama P. Lintasan

ke

yang melewati titik

juga merupakan lintasan pelangi, misalnya lintasan ini diberi nama Q. Lalu beberapa sisi dari

diberi warna

warna yang sama. Misalkan lintasan

dan sisi pada ke

yang melewati titik

adalah lintasan pelangi, maka

berwarna

Dengan menggunkan cara yang sama lintasan melewati titik maka

ke

.

yang

merupakan lintasan pelangi, . Jadi

langsung tidak ada lintasan pelangi pada

. Secara tidak ke

, sehingga haruslah

. Dari ulasan diatas sehingga terbukti bahwa

⌈ ⌉.

2. Bilangan pelangi titik terhubung (rainbow vertex-connection) Asumsikan bahwa

.

a. Diasumsikan

juga diberi

atau

39

Ambil dari titik

dan

sehingga ada lintasan pelangi

ke titik , dengan minimal bilangan warna sisi sebanyak .

Ini artinya lintasan dari titik

ke titik

melewati

. Sehingga dapat dikatakan ada

titik misalkan titik

yang tidak terhubung

langsung. Ini jelas tidak sesuai dengan graf

, karena ketiga titik saling

berhubungan. Sehingga pengasumsian salah. Jadi dapat disimpulkan bahwa b.

untuk Untuk membuktikan

, maka akan dibuktikan bahwa

dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil

, misalkan ada fungsi pewarnaan

maka lintasan

dan

akan melewati titik interior

sedangkan setiap lintasan dimana

, sehingga setiap dimana

,


. Dengan demikian setiap dua titik terdapat lintasan

dengan warna titik interior yang berbeda. Jadi terbukti

.

⌈ ⌉

c. ⌈ ⌉

untuk

Ambil contoh pada

atau , misalkan pewarnaan titik

dari

menggunakan 2 warna, dua titik yang berdekatan mempunyai warna yang sama. Namun dua lintasan yaitu

40

dan

pada

bukanlah lintasan

pelangi, dengan kata lain tidak ada lintasan pelangi diantara Jadi

dan

.

bukanlah pewarnaan pelangi titik. Oleh karena itu haruslah .

misalkan dengan asumsi berbeda, bahwa mempunyai

⌈ ⌉

untuk

pewarnaan pelangi titik c. lalu ketiga titik mempunyai warna

sama

pada

satu

bagian

titik,

diantara

titik-titik

yang

tersebut

mempunyai jarak tidak lebih dari ⌈ ⌉ dengan kata lain ⌈ ⌉ . Misalkan menuju

adalah lintasan dari

dengan panjang

. Karena

,

bukanlah lintasan pelangi. Jadi adalah lintasan pelangi dari ⌈ ⌉

Sehingga

⌈ ⌉ jika

untuk titik dalam.

. atau

Misalkan dari

. Karena

bukanlah lintasan pelangi. Oleh karena itu

untuk

d.

⌈ ⌉

mempunyai paling sedikit ⌈ ⌉

,

⌈ ⌉

menuju

. Didefinisikan pewarnaan titik adalah

untuk

⌈ ⌉ dan

⌈ ⌉ jika

41

⌈ ⌉

. Untuk sembarang dua titik dengan panjang

, lintasan pada

adalah lintasan pelangi. Sehingga akan ⌈ ⌉ untuk

didapatkan

dari

atau ⌈ ⌉ untuk

Sekarang akan dibuktikan bahwa

⌈ ⌉

Misalkan diasumsikan terbalik, bahwa Lalu ada ⌈ ⌉ ada

tiga

pewarnaan titik pelangi

pada

titik

pada

adalah lintasan dari Sekarang diberi contoh pada titik

, misal

dengan panjang dan

. Karena

mempunyai warna yang sama, lintasan pelangi diantara haruslah

adalah minimal ⌈ ⌉

⌈ ⌉

untuk

atau

bahwa

bukanlah lintasan pelangi. Oleh karena itu

untuk

atau atau

. dan dan

. Karena

, nomor titik dalam pada

⌈ ⌉ untuk

yang

⌈ ⌉. Selanjutnya diasumsikan bahwa

memenuhi

⌈ ⌉

.

. Sesungguhnya,

mempunyai warna yang sama. Dan satu titik diantara

pada

atau

.

ini menunjukkan

. Sehingga diperoleh .

⌈ ⌉

⌈ ⌉

42

3.2

Graf Roda Graf roda adalah graf yang berbentuk dari operasi penjumlahan antara graf

sikel (

) dan graf komplit dengan satu titik (

dan

. Graf roda dinotasikan dengan

. Bilangan pelangi sisi terhubung

pada graf roda dan

dan bilangan pelangi titik terhubung

dapat ditentukan dengan menentukan terlebih dahulu pada graf

, graf

, graf

terakhir menggambar pola warna pada graf

, graf

, graf

dan

agar terbentuk graf pelangi sisi

terhubung. 1

1

1

1

𝑾 :

1

1 1

3

2

Gambar 3.6 Graf roda

Graf

terdiri dari 4 titik dan 6 sisi. Setiap titik

langsung dengan titik . Ambil lintasan ini menjadi

ke

. Sedangkan bila lewat

pada graf

, bila lewat titik , maka lintasan , maka lintasan ini menjadi

. Namun karena lintasan dapat langsung terhubung dari melalui

atau

atau

, maka sisi

terhubung

ke

diberi warna 1. sehingga lintasan

tanpa , ,

dapat diabaikan. Dengan cara yang sama dapat diterapkan pada sisi , sisi

, dan sisi

, Sehingga terbukti bahwa

Sedangkan untuk bilangan pelangi titik terhubung, pada graf titik terhubung langsung, sehingga tidak memiliki warna titik. Jadi

. semua .

43

1

1

2

1 1 𝑾𝟒 :

1 2

2 2

2 1

1

4

3


Graf titik

terdiri dari 5 titik dan 8 sisi. Ambil lintasan

, maka lintasan ini menjadi

lintasan ini menjadi menjadi lintasan

ke

bila lewat


. Lintasan ini juga bisa melewati titik

, maka , sehingga

. Dari ketiga lintasan yang tercipta dari lintasan

ke

ini sama-sama mempunyai panjang 2 sisi, sehingga dengan memberikan 2 warna warna yang berbeda pada masing-masing sisi pada lintasan akan terbentuk pelangi sisi terhubung. Jadi terbukti bahwa

.

Sedangkan untuk pelangi titik terhubung. Ambil lintasan semua titik

berhubungan langsung dengan titik

akan membuat pelangi

. 1

1

1 1

5

𝑾𝟓 :

2

2 1

2 4

2

1

1

, karena


. sehingga dengan memberi warna 1 pada titik titik terhubung. Jadi terbukti bahwa

ke

1


2 3

44

Graf titik



lintasan ini menjadi

ke

bila lewat


. Lintasan inipun dapat melewati titik

sehingga lintasan menjadi

. Pada lintasan

maupun

, maka dan

, ,

sama-sama mempunyai panjang 2 sisi, sehingga misalnya salah satu yaitu lintasan diberi warna masing-masing 1 untuk sisi . Lalu pada lintasan dan sisi

diwarna 2

merupakan lintasan pelangi.

diberi warna 1, maka tidak ada lintasan pelangi pada lintasan

yang melewati titik

pelangi dengan melewati titik (

masing-masing sisi, sisi

, maka lintasan

Ketika sisi ( ke

dan warna 2 untuk sisi

. Namun lintasan

ke

yaitu ketika sisi (

diberi warna 1, ini sudah membuat

dapat dibuat lintasan diberi warna 2 dan sisi

ke

pelangi dengan mengabaikan lintasan

menjadi lintasan . Sehingga dari uraian diatas

minimal dibutuhkan 2 warna berbeda untuk membuat pelangi sisi terhubung. Jadi terbukti bahwa

.



.

, karena



ke


45

1

1

2 6

𝑾𝟔 :

2

2

1

1

1 2

3

1

5

2

1 2 1

2 4


Graf


melewat titik dan

dan


ke

, bila

. Bila lewat titik


. Namun karena dengan

melewati titik

yang menjadi lintasan

merupakan lintasan terpendek,

maka sisi

diberi warna 1 dan sisi

diwarna 2. Dengan menggunakan

cara yang sama pada lintasan yang berhubungan dengan titik lintasan pelangi, dimana setiap lintasan yang melewati titik

akan terbentuk

merupakan lintasan

terdekat dibandingkan menggunakan lintasan sikelnya. Sedangkan untuk membuat lintasan pelangi pada sisi sikelnya dengan memberi warna 1 pada sisi dengan ganjil, dan warna 2 pada sisi

dengan

genap, maka

akan tercipta pelangi sisi terhubung secara keseluruhan. Jadi terbukti bahwa . Sedangkan untuk pelangi titik terhubung. Ambil lintasan semua titik


.

, karena



ke


46

1

1

1 7

3

2

𝑾𝟕 :

2

1 2 1

3 6

3

1

2

5

2

1 3

2 1 4


Graf


melewat titik dan

dan



ke

, bila

. Bila lewat titik . Namun karena dengan

melewati titik

yang menjadi lintasan

merupakan lintasan terpendek,

maka sisi


diwarna 2. Lalu misalnya untuk

lintasan sikel diberi warna 1 pada sisi sisi

dengan

dengan ganjil, dan warna 2 pada

genap. Sedangkan lintasan yang melewati titik

diberi warna 1 dengan ganjil dan sisi dengan genap, maka pada lintasan

ke

, lintasan

, sisi

diberi warna 2 ke

dan lintasan

ke

tidak terdapat lintasan pelangi. Sehingga haruslah lintasan sikel diberi warna 1 pada sisi

dengan ganjil, dan warna 2 pada sisi

genap. Lalu sisi sisi


diberi warna 3. Ini akan membuat lintasan

menjadi lintasan pelangi. Pada sisi warna 3 maka lintasan diberi warna 3 dan sisi

ke

dengan

diwarna 2, selanjutnya ke

dan lintasan


ke diberi

merupakan lintasan pelangi. Lalu sisi diberi warna 1 membuat lintasan

ke

menjadi

47

lintasan pelangi. Sehingga dibutuhkan minimal 3 warna yang berbeda untuk membuat pelangi sisi terhubung. Jadi terbukti bahwa

.




, karena



ke


. dan

pada

sampai


0 1 1 1 1

Dari pola yang ditunjukan oleh bilangan pelangi sisi terhubung (rainbow edge-connection) dan bilangan pelangi titik terhubung (rainbow vertexconnection) di atas dapat diperoleh teorema sebagai berikut: Teorema 2 Graf

adalah graf roda

dengan


terhubung (rainbow edge-connection) pada graf {

(Li dan Sun, 2012:8).

adalah:

48

Bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf adalah: { Bukti: Graf roda

dengan

adalah graf yang terbentuk dari operasi

penjumlahan antara graf sikel (

) dan graf komplit dengan satu titik (

Misalkan

, maka

serta untuk semua

, dan

. ,

terhubung langsung dengan .

1. Bilangan pelangi sisi terhubung (rainbow edge-connection) a. Jika

,

Ambil lintasan

ke

, bila lewat titik , maka lintasan ini menjadi



Namun karena lintasan dapat langsung terhubung dari melalui , ,

atau

, maka sisi

atau

tanpa


dapat diabaikan. Dengan cara yang sama dapat

diterapkan pada sisi terbukti bahwa b. Jika

ke

.

, sisi

, dan sisi

,

Sehingga

. maka

Akan dibuktikan

dan

Graf

bukan merupakan graf komplit, karena

dengan

sedangkan jumlah titiknya . Kemudian untuk membuktikan

.

|

|

, sehingga maka akan

49

dibuktikan bahwa dengan 2 warna dapat membentuk

menjadi

pelangi sisi yang terhubung, sehingga setiap dua titik terdapat lintasan dengan warna sisi yang berbeda. Fungsi pewarnaan sisi yang didefinisikan oleh jika genap,

jika ganjil,

jika ganjil,

Setiap lintasan

atau

Kemudian lintasan

jika genap.

hanya terdapat satu warna sisi.

, jika

genap dan

dan

ganjil pasti

berbentuk lintasan pelangi 2 warna. Sedangkan untuk lintasan dengan

dan sama-sama genap atau dan

sama-sama ganjil. Jika

maka membentuk lintasan pelangi yang sisi-sinya jika lintasan

, dengan

diperoleh

maka

. Untuk

dengan lintasan

pelangi melewati titik

, karena

, dengan lintasan

maka dapat dibentuk lintasan pelangi melewati titik untuk

. Tetapi

, sedangkan

, maka dapat dibentuk lintasan

, terbukti setiap dua titik terdapat lintasan

dengan warna sisi yang berbeda, sehingga diperoleh terbukti untuk c. Jika

,

maka

. Jadi

.

maka

Ambil lintasan menjadi menjadi menjadi lintasan

ke

, bila melewat titik . Bila lewat titik

dan dan

, maka lintasan ini , maka lintasan ini

. Namun karena dengan melewati titik

yang

merupakan lintasan terpendek, maka sisi



50

lintasan sikel diberi warna 1 pada sisi warna 2 pada sisi melewati titik

dengan

, sisi

dengan ganjil, dan

genap. Sedangkan lintasan yang

diberi warna 1 dengan ganjil dan sisi

diberi warna 2 dengan genap, maka pada lintasan lintasan

ke

dan lintasan

ke

ke

,

tidak terdapat lintasan pelangi.

Sehingga haruslah lintasan sikel diberi warna 1 pada sisi dengan ganjil, dan warna 2 pada sisi sisi

dengan


diwarna 2, selanjutnya sisi

diberi warna 3. Ini akan membuat lintasan ke sisi

menjadi lintasan pelangi. Pada sisi diberi warna 3 maka lintasan

pelangi. Lalu sisi membuat lintasan

genap. Lalu

ke

dan lintasan

diberi warna 2 dan ke

merupakan lintasan


diberi warna 1

ke

menjadi lintasan pelangi. Sehingga

dibutuhkan minimal 3 warna yang berbeda untuk membuat pelangi sisi terhubung. Jadi terbukti bahwa

.

2. Bilangan pelangi titik terhubung (rainbow vertex-connection) Jika

maka

Akan dibuktikan Diketahui

dan

.

, sehingga

Untuk membuktikan

.

, maka akan dibuktikan bahwa dengan 1

warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil , misalkan ada fungsi pewarnaan

maka:

51

, sehingga setiap lintasan dimana



tidak ada titik interior

karena terhubung langsung, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti . Karena 3.3

dan

, maka

.

Garaf Gear Graf gear

merupakan graf roda dengan tambahan satu titik di antara

tiap-tiap pasangan titik pada sikel luar. Graf gear

memiliki

titik pada sikel

luarnya dan satu titik pada pusatnya sehingga banyaknya titik pada . Graf gear

memuat graf roda

yang memiliki

adalah

sisi ditambah

sisi

yang terbentuk dari penambahan satu titik di antara tiap-tiap pasangan titik pada sikel luar sehingga banyaknya sisi pada

adalah

.

Bilangan pelangi sisi terhubung (rainbow edge-connection) dan bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf roda ditentukan dengan menentukan terlebih dahulu graf

, graf

, graf

, dan graf

graf

agar terbentuk graf pelangi sisi terhubung.

dan

dapat

pada graf

,

dan terakhir menggambar pola warna pada

1

1

3:

3

1 1 3

2

3

2 1

2

2 3

2 3 2

1

1

2

Gambar 3.11 Graf gear

1 2

52

Graf gear

terdiri dari 7 titik dan 9 sisi, itu diperoleh dari tambahan titik

pada sisi-sisi luar graf

. Ambil lintasan

ke

, melalu lintasan manapun

lintasan ini mempunyai panjang 3 sisi, sehingga dibutuhkan minimal dibutuhkan 3 warna yang berbeda. Misal beri warna lintasan dan

dengan, sisi

ke

yang melewati titik

diberi warna 1, sisi (


diberi warna 3, maka dengan menggunakan cara yang sama dalam memberi warna pada lintasan

ke

yang melewati titik

dan

, sisi sikel

akan mendapat pelangi sisi terhubung. Lalu untuk membuat pelangi sisi terhubung semuanya, sisi



diberi warna 2, sehingga terbukti dengan 3 warna dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa

.



berbeda, dibutuhkan dua warna titik. Ambil lintasan

ke

, lewat lintasan

manapun, lintasan ini akan melewati 2 titik. misal lewat titik

dan

dengan memberi warna 1 pada titik

akan membuat

dan warna 2 pada titik

pelangi titik terhubung. Jadi terbukti bahwa 3 3 4:

4

1

1

4

2

2

3 4

2

1

2

1 2

2

1

1 1

4

.

2 3

3

2

2

4

3

3


, maka

53

Graf gear


ke

, lewat

lintasan manapun,panjang lintasan ini adalah 4 sisi, sehingga dibutuhkan minimal 4 warna yang berbeda. Misal ambil lintasan , maka lintasan itu menjadi warna 2 pada sisi

ke

yang melewati

. Beri warna 1 pada sisi

, warna 4 pada sisi

, sehingga lintasan

ke

dan

misalkan sisi

,

, dan warna 3 pada sisi

yang melewati

dan

menjadi

lintasan pelangi. Dengan menggunakan cara yang sama pada lintasan yang melewati

dan

ke

, maka sisi sikel menjadi lintasn pelangi. Lalu



diberi

warna 2,dan sisi

diberi warna 3, maka akan terbentuk pelangi sisi

terhubung pada graf gear

. Jadi terbukti bahwa

.



berbeda, dibutuhkan 3 warna titik. Ambil lintasan

ke

manapun, lintasan ini akan melewati 3 titik. misal lewat titik dengan memberi warna 1 pada titik pada titik


, lewat lintasan dan

, maka

dan warna 3

akan membuat pelangi titik terhubung. Jadi terbukti bahwa .

54

1

5 3 2

5

5

𝑮𝟓 :

1 2 1 4

5

4 2 5 4

1

1

1 2

1 3

2 2 4

3 3

2 3

2

3

2

2

2

4 3

3


Graf gear


lintasan ini mempunyai panjang minimal 4 sisi yaitu ketika lewat titik dan titik

yang membuat lintasan menjadi

melewati titik

titik

, dan titik

. Lalu melewati titik lintasan menjadi

titik

titik

, dan titik

,

titik

,

. Selanjutnya

yang membuat lintasan menjadi titik

, dan titik

. Lalu melewati titik

membuat lintasan menjadi

ke

yang membuat

titik , dan titik

yang

. Dan yang terakhir adalah melewati yang membuat lintasan menjadi

.

Sehingga dibutuhkan minimal 4 atau lebih warna yang berbeda. Asumsikan dengan 4 warna dapat membuat pelangi sisi terhubung. Misal lintasan diberi warna 1-4 pada setiap sisi-sisinya, yaitu sisi warna 1, sisi

) diberi warna 2, sisi

diberi warna 4. Karena sisi 4, maka sisi



diberi warna

diberi warna 2. Sehingga

dan lintasan

pelangi sisi terhubung. Selanjutnya karena sisi

dan sisi

) diberi warna 3, dan sisi


membuat lintasan

diberi

menjadi lintasan ) diberi warna 2, sisi


diberi warna 2. Sehingga lintasan

)

) diberi warna 1 menjadi

55

lintasan pelangi terhubung. Karena sisi diberi warna 2, maka haruslah sisi

) diberi warna 1 dan sisi ) diberi warna 4 dan sisi

warna 3 agar terbentuk lintasan pelangi pada lintasan karena sisi


warna 4, maka haruslah sisi

. Selanjutnya

) diberi warna 3, dan

ke

. Selanjutnya karena sisi


ke

pelangi. Lalu untuk membuat lintasan pelangi pada lintasan diberi warna 4 dan sisi diberi warna 3 dan sisi

diberi

) diberi warna 1, maka haruslah sisi

haruslah diberi warna 4. Sehingga lintasan

karena sisi

) diberi

haruslah diberi warna 1. Sehinga terdapat

lintasan pelangi pada lintasan warna 2, sisi

diberi

menjadi lintasan ke

haruslah sisi

diberi warna 2, karena sisi diberi warna 1. Lalu pada lintasan


diberi warna 4, maka haruslah sisi

ke

,

) diberi warna 2, dan sisi ) diberi warna 3. Sehingga lintasan

menjadi lintasan pelangi. Namun ini membuat lintasan merupakan lintasan pelangi. Sehingga haruslah

ke

ke bukan

) diberi warna 5 agar

menjadi lintasan pelangi. Jadi terbukti bahwa dengan menggunakan 5 warna berbeda membuat graf gear

menjadi pelangi sisi terhubung. Oleh karena itu

. Sedangkan agar terbentuk pelangi titik yang terhubung, di mana setiap antara dua titik pada graf


berbeda, dibutuhkan 3 warna titik. Ambil lintasan melewati 3 titik. misal lewat titik

dan

ke

, lintasan ini akan

, maka dengan memberi warna 1

56

pada titik



pelangi titik terhubung. Jadi terbukti bahwa

6

6

𝑮𝟔 :

6

1 4 6 5 2 2 6 4 3 5 3 3 2 4

.

1

1 2

4

akan membuat

3 2 2 1

1

1

2

2 32

5 1

2 5

2

1 5 2 3

3 3

4


Graf gear


lintasan ini mempunyai panjang minimal 4 sisi yaitu ketika lewat titik dan titik titik

yang membuat lintasan menjadi , dan titik

melewati titik

, dan titik

titik

pada setiap sisi-sisinya, yaitu sisi

dan sisi lintasan sisi




. Lalu

, dan titik

yang

. Asumsikan dengan 4 warna dapat

membuat pelangi sisi terhubung. Misal lintasan

2, sisi

titik ,


. Dan yang terakhir melewati titik membuat lintasan menjadi

diberi warna 1-4 ) diberi warna

diberi warna 4. Karena sisi


)

) diberi warna 1

diberi warna 2. Sehingga membuat lintasan menjadi lintasan pelangi. Karena diberi warna 2, dan sisi


,



ke

dan ) diberi warna 1,

) diberi warna 3, maka sisi

diberi warna 3 sehingga lintasan

) ke

57

menjadi lintasan pelangi. Selanjutnya karena sisi ) diberi warna 3, dan sisi





menjadi lintasan pelangi. Lalu karena sisi warna 2, sisi sisi


diberi warna 1 dan sisi ke

lintasan pelangi. Selanjutnya karena sisi ) diberi warna 3, dan sisi

haruslah sisi


ke

menjadi


warna 4, sisi

lintasan

) diberi

diberi warna 2, maka ) diberi warna 2. Sehingga

menjadi lintasan pelangi. Karena sisi


diberi


diberi warna 4, maka haruslah sisi ) diberi warna 4. Sehingga lintasan

ke

diberi warna 3,


diberi warna 1, namun ini membuat lintasan

ke

bukan merupakan lintasan

pelangi. Sehingga 4 warna tidak dapat membuat lintasan pelangi. Selanjutnya misalnya dengan 6 warna akan dibuktikan dapat membuat lintasan pelangi. Beri warna 1 s/d 6 pada sisi sisi

) s/d sisi


2, maka haruslah sisi

). Karena sisi

) diberi warna 5, dan sisi diberi warna 2, sisi


maka haruslah sisi

) diberi warna diberi warna 1, sisi


menjadi lintasan pelangi. Selanjutnya karena sisi ) diberi warna 3, sisi

) diberi warna 1,



ke

) diberi warna 2, sisi ) diberi warna 6, diberi warna 2, sisi

diberi warna 5. Sehingga membuat

58

lintasan

ke

warna 1, sisi



diberi warna 6, maka haruslah sisi warna 3, sisi lintasan



ke

) diberi ) diberi


menjadi lintasan pelangi. Dan ini juga membuat semua lintasan

menjadi lintasan pelangi. Sehingga terbukti dengan 6 warna yang berbeda dapat membuat lintasan pelangi. Oleh karena itu

.



berbeda, dibutuhkan 3 warna titik. Ambil lintasan melewati 3 titik. misal lewat titik pada titik


dan

ke

, lintasan ini akan



pelangi titik terhubung. Jadi terbukti bahwa 7

akan membuat

. 1

2 1 7 1 1 1 2 2 7 3 3 2 1 6 3 7 2 𝑮𝟕 : 6 2 2 2 2 7 6 2 3 1 6 1 3 4 5 2 5 2 4 5 2 3 3 3 6 3 4 4 5 1 5 4

Gambar 3.15 Graf gear Graf gear


lintasan ini mempunyai panjang minimal 4 sisi yaitu ketika lewat titik dan titik


ke

,

titik ,


59

titik

, dan titik

melewati titik


, dan titik

. Lalu


. Dan yang terakhir melewati titik membuat lintasan menjadi

titik

, dan titik

. Asumsikan dengan 4 warna dapat

membuat pelangi sisi terhubung. Misal lintasan pada setiap sisi-sisinya, yaitu sisi 2, sisi

yang




diberi warna 1-4 ) diberi warna



)

) diberi warna 1

dan sisi

diberi warna 2. Sehingga membuat lintasan

dan

lintasan

menjadi lintasan pelangi. Karena sisi

) diberi warna

1, sisi





menjadi lintasan pelangi. Selanjutnya karena sisi ) diberi warna 4, dan sisi

) ke



diberi warna 2 agar lintasan

ke

lintasan pelangi. Namun ini membuat sisi

ke

menjadi bukan merupakan lintasan

pelangi. Sehingga 4 warna tidak dapat membuat lintasan pelangi. Selanjutnya misalkan dengan 7 warna akan dibuktikan dapat membuat lintasan pelangi. Beri warna 1 s/d 7 pada sisi sisi

) s/d sisi



). Karena sisi

) diberi warna 1,



) diberi warna diberi warna 1, sisi


menjadi lintasan pelangi. Selanjutnya karena sisi

ke


60

) diberi warna 3, sisi maka haruslah sisi


diberi warna 7, dan sisi lintasan

ke

warna 3, sisi


diberi warna 7. Sehingga membuat


)


warna 3, sisi


membuat lintasan

ke


) diberi



sisi

) diberi warna 7,

diberi




) diberi warna 5, maka haruslah sisi diberi warna 1, sisi



warna 5. Sehingga membuat lintasan

ke

diberi

menjadi lintasan pelangi. Dari

uraian diatas membuktikan bahwa dengan memberikan 7 warna yang berbeda terbukti bahwa apat membuat lintasan pelangi. Oleh karena itu

.



berbeda, dibutuhkan 3 warna titik. Ambil lintasan melewati 3 titik. misal lewat titik pada titik


dan

ke



pelangi titik terhubung. Jadi terbukti bahwa

, lintasan ini akan

akan membuat

61


dan

pada

sampai


2 3 3 3 3


adalah graf gear

dengan


terhubung (rainbow edge-connection) pada graf

adalah:

untuk Bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf adalah: { Bukti : Graf gear

merupakan graf roda

dengan tambahan satu titik di

antara tiap-tiap pasangan titik pada sikel luar. Misalkan dan terhubung langsung dengan .

serta semua

62

1. Bilangan pelangi sisi terhubung (rainbow edge-connection) pada graf a. Jika

maka

Ambil lintasan

ke

, melalu lintasan manapun lintasan ini

mempunyai panjang 3 sisi, sehingga dibutuhkan minimal dibutuhkan 3 warna yang berbeda. Misal beri warna lintasan titik

dan

dengan, sisi

warna 2, dan sisi

ke

yang melewati

diberi warna 1, sisi (

diberi

diberi warna 3, maka dengan menggunakan

cara yang sama dalam memberi warna pada lintasan melewati titik

dan

ke

yang

, sisi sikel akan mendapat pelangi sisi

terhubung. Lalu untuk membuat pelangi sisi terhubung semuanya, sisi diberi warna 1, sisi


diberi

warna 2, sehingga terbukti dengan 3 warna dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa b. Jika

.

maka

Ambil lintasan

ke

, lewat lintasan manapun,panjang lintasan ini

adalah 4 sisi, sehingga dibutuhkan minimal 4 warna yang berbeda. Misal ambil lintasan

ke

yang melewati

lintasan itu menjadi warna 2 pada sisi pada sisi dan

dan

. Beri warna 1 pada sisi , warna 4 pada sisi

, sehingga lintasan

ke

, maka ,

, dan warna 3 yang melewati

menjadi lintasan pelangi. Dengan menggunakan cara yang sama

pada lintasan

ke

yang melewati

menjadi lintasn pelangi. Lalu misalkan sisi

dan

, maka sisi sikel diberi warna 1, sisi

63


diberi warna 2,dan sisi

diberi

warna 3, maka akan terbentuk pelangi sisi terhubung pada graf gear Jadi terbukti bahwa c. Jika

.

.

maka

Ambil lintasan

ke

, lintasan ini mempunyai panjang minimal 4

sisi yaitu ketika lewat titik

titik

lintasan menjadi , dan titik

, dan titik

yang membuat

. Selanjutnya melewati titik yang membuat lintasan menjadi

melewati titik

titik , dan titik . Lalu melewati titik

membuat lintasan menjadi melewati titik

titik . Lalu


, dan titik

yang

. Dan yang terakhir adalah

titik , dan titik


. Sehingga dibutuhkan minimal 4 atau lebih warna yang berbeda. Asumsikan dengan 4 warna dapat membuat pelangi sisi terhubung. Misal lintasan sisi-sisinya, yaitu sisi

diberi warna 1-4 pada setiap diberi warna 1, sisi

2, sisi


sisi

diberi warna 1 dan sisi diberi warna 3 dan sisi

membuat lintasan

) diberi warna

diberi warna 4. Karena diberi warna 4, maka sisi diberi warna 2. Sehingga dan lintasan

menjadi lintasan pelangi sisi terhubung. Selanjutnya karena sisi diberi warna 2, sisi 4, maka sisi

) diberi warna 3 dan sisi ) diberi warna 1 dan sisi

)

diberi warna diberi warna 2.

64

Sehingga lintasan Karena sisi

menjadi lintasan pelangi terhubung. ) diberi warna 1 dan sisi

maka haruslah sisi

diberi warna 2,

) diberi warna 4 dan sisi

diberi warna

3 agar terbentuk lintasan pelangi pada lintasan Selanjutnya karena sisi 3, dan

.


) diberi warna


haruslah

diberi warna 1. Sehinga terdapat lintasan pelangi pada lintasan . Selanjutnya karena sisi warna 3, dan


ke

menjadi lintasan

pelangi. Lalu untuk membuat lintasan pelangi pada lintasan

karena sisi

ke


diberi warna 2,


diberi warna 1.

Lalu pada lintasan

ke

, karena sisi

) diberi warna 2, dan sisi sisi

) diberi


haruslah diberi warna 4. Sehingga lintasan

haruslah sisi

ke


diberi warna 4, maka haruslah

) diberi warna 3. Sehingga lintasan

pelangi. Namun ini membuat lintasan lintasan pelangi. Sehingga haruslah

ke ke

menjadi lintasan bukan merupakan

) diberi warna 5 agar menjadi

lintasan pelangi. Jadi terbukti bahwa dengan menggunakan 5 warna berbeda membuat graf gear karena itu

.

menjadi pelangi sisi terhubung. Oleh

65

d. Jika

maka

Ambil lintasan

ke



titik

lintasan menjadi


titik

, dan titik

yang membuat


titik

titik

, dan titik

titik

, dan

. Lalu melewati


. Dan yang terakhir melewati titik yang membuat lintasan menjadi

titik , dan titik

. Asumsikan dengan 4

warna dapat membuat pelangi sisi terhubung. Misal lintasan diberi warna 1-4 pada setiap sisi-sisinya, yaitu sisi diberi warna 1, sisi warna 3, dan sisi warna 3, dan sisi


) diberi


) diberi


1 dan sisi

diberi warna 2. Sehingga membuat lintasan dan lintasan

Karena

) diberi warna

menjadi lintasan pelangi.


) diberi warna 3, maka sisi diberi warna 3 sehingga lintasan Selanjutnya karena sisi 3, dan sisi

diberi warna 2, dan sisi ) diberi warna 4 dan sisi ke



) diberi warna


warna 2 dan sisi

diberi


ke

menjadi lintasan pelangi. Lalu karena sisi diberi warna 2, sisi sisi


) diberi warna

66

3, dan sisi


warna 1 dan sisi

diberi


ke

menjadi lintasan pelangi. Selanjutnya karena sisi diberi warna 1, sisi warna 3, dan sisi





menjadi lintasan pelangi. Karena sisi ) diberi warna 2, dan sisi sisi

) diberi

ke

diberi warna 3,

) diberi warna 4, maka haruslah


ke

bukan merupakan lintasan pelangi. Sehingga 4 warna tidak dapat membuat lintasan pelangi. Selanjutnya misalnya dengan 6 warna akan dibuktikan dapat membuat lintasan pelangi. Beri warna 1 s/d 6 pada sisi ) s/d sisi

). Karena sisi



2, maka haruslah sisi 1, sisi

karena sisi

ke

diberi warna diberi warna 4.

menjadi lintasan pelangi. Selanjutnya





diberi




)


diberi warna 3, sisi warna 6, dan sisi

)

) diberi warna



Sehingga lintasan

ke



)

) diberi warna 4,

67

dan sisi


4, sisi


diberi warna



ke

menjadi lintasan

pelangi. Dan ini juga membuat semua lintasan menjadi lintasan pelangi. Sehingga terbukti dengan 6 warna yang berbeda dapat membuat lintasan pelangi. Oleh karena itu e. Jika

.

maka

Ambil lintasan

ke



titik

lintasan menjadi


titik titik

, dan titik


, dan titik

yang membuat titik

, dan

. Lalu melewati


. Dan yang terakhir melewati titik yang membuat lintasan menjadi

titik , dan titik

. Asumsikan dengan 4

warna dapat membuat pelangi sisi terhubung. Misal lintasan diberi warna 1-4 pada setiap sisi-sisinya, yaitu sisi diberi warna 1, sisi warna 3, dan sisi warna 3, dan sisi 1 dan sisi


) diberi


) diberi


diberi warna 2. Sehingga membuat lintasan dan lintasan

Karena sisi

) diberi warna



menjadi lintasan pelangi. diberi warna 2, dan sisi ) diberi warna 4 dan sisi

68

diberi warna 3 sehingga lintasan Selanjutnya karena sisi 4, dan sisi

ke



) diberi warna


warna 2 agar lintasan

ke

diberi

menjadi lintasan

pelangi. Namun ini membuat sisi

ke

bukan merupakan lintasan

pelangi. Sehingga 4 warna tidak dapat membuat lintasan pelangi. Selanjutnya misalkan dengan 7 warna akan dibuktikan dapat membuat lintasan pelangi. Beri warna 1 s/d 7 pada sisi Karena sisi


) diberi warna 5, dan sisi sisi

ke


diberi warna 1, sisi diberi warna 4. Sehingga lintasan


warna 2, sisi



pelangi. Selanjutnya karena sisi

3, sisi




ke



Sehingga membuat lintasan Selanjutnya karena sisi

menjadi lintasan




) diberi




).

) diberi warna 2, maka haruslah



) s/d sisi

ke

)

) diberi warna diberi warna diberi warna 7.



) diberi warna

69

4, sisi


haruslah sisi

) diberi warna 5, maka


diberi warna 6, dan sisi membuat lintasan

ke

diberi warna 1, sisi diberi warna 5. Sehingga

menjadi lintasan pelangi. Dari uraian diatas

membuktikan bahwa dengan memberikan 7 warna yang berbeda terbukti bahwa dapat membuat lintasan pelangi. Oleh karena itu . Atau misalkan fungsi pewarnaan sisi oleh

, didefinisikan

secara berputar. Kemudian , dan

jika

jika terbukti dengan

jika

. kemudian

dan

jika

. Sehingga

warna yang berbeda dapat membuat pelangi sisi

terhubung. Jadi terbukti bahwa

.

2. Bilangan pelangi titik terhubung (rainbow vertex- connection) pada graf

a. Jika

maka

Ambil lintasan

ke

, lewat lintasan manapun, lintasan ini akan

melewati 2 titik. misal lewat titik warna 1 pada titik


titik terhubung. Jadi terbukti bahwa b. Jika

dan

, maka dengan memberi akan membuat pelangi .

maka

Untuk membuktikan

, maka akan dibuktikan bahwa

dengan 3 warna titik, dapat membentuk pelangi titik yang terhubung,

70

artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil

, misalkan ada fungsi pewarnaan maka:

dengan

,

ganjil, dan

dengan . Sehingga

genap,

dapat membuat

pelangi titik terhubung, oleh karena itu terbukti bahwa

.

3.4 Graf Helm Graf helm

adalah graf yang diperoleh dari graf roda dengan

menambahkan sisi anting pada setiap titik pada sikel luarnya. Graf helm memuat graf roda

dengan

titik ditambah

titik lagi yang diperoleh dari

penambahan sisi anting-anting pada setiap titik pada sikel luar, sehingga banyaknya titik pada memiliki

adalah

sisi ditambah

. Graf helm

memuat graf roda

yang

sisi yang terbentuk dari penambahan satu sisi anting-

anting pada setiap titik pada sikel luar sehingga banyaknya sisi pada

adalah

. Bilangan pelangi sisi terhubung (rainbow edge-connection) dan bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf Helm ditentukan dengan menentukan terlebih dahulu ,

,

dan

dan

pada graf

dan terakhir menggambar pola warna pada graf

terbentuk graf pelangi sisi terhubung.

dapat

agar

71

1

1 2 1

1 𝑯 :

1

1

4

1

1

1

1

2 1

3

1 2

3

3

2

Gambar 3.16 Graf helm

Graf helm

mempunyai 9 sisi dan 7 titik. Graf helm

adalah graf yang

diperoleh dari graf roda dengan menambahkan sisi anting pada setiap titik pada sikel luarnya. Ambil lintasan menjadi

ke

, bila lewat titik



Namun karena lintasan dapat langsung terhubung dari atau

, maka sisi

, maka lintasan ini

ke

.

tanpa melalui


, ,

atau


, dan sisi

1, maka sisi lintasan


diberi warna

haruslah diberi warna 1 agar terbentuk lintasan pelangi pada ke



diberi warna 1, maka untuk membuat pelangi sisi terhubung pada lintasan ke

maka sisi

haruslah diberi warna 3. Lalu untuk membuat pelangi

sisi terhubung pada lintasan

ke

, karena sisi

diberi warna 1, maka haruslah sisi cara lain, sisi-sisi dari graf helm graf roda

diberi warna 3, dan sisi diberi warna 3. Atau dengan

dapat dikelompokkan sebagai berikut (i) sisi

, dan (ii) sisi jari-jari. Awalnya beri warna sisi graf roda

dengan warna pada graf roda

sesuai

yaitu 1. Yang kedua untuk sisi jari-jari agar

terbentuk graf pelangi sisi terhubung pada graf

, di mana setiap antara dua titik

72

terdapat lintasan dengan warna berbeda maka dibutuhkan minimal 3 warna sisi yang berbeda, sehingga

.



berbeda, dibutuhkan dua warna titik. Ambil lintasan dan titik

maka lintasan menjadi

dengan hanya melewati titik menjadi

ke

. Karena dapat dilewati langsung

tanpa melewati titik

, maka titik

, bila lewat titik

yang membuat lintasan

diberi warna 1. Dengan cara yang sama

digunakan pada lintasan

dan lintasan

. Sedangkan agar

terbentuk pelangi titik yang terhubung, di mana setiap antara dua titik pada graf terdapat lintasan dengan warna titik interior yang berbeda maka titik warna 2. Jadi terbukti bahwa

diberi

. 1

2

6 1

1

1

2

1

1

𝑯𝟒 :

2

3

2

3 2 2

2 4

5

2

1

1

3

4 3

4


Graf helm


adalah graf

yang diperoleh dari graf roda dengan menambahkan sisi anting pada setiap titik pada sikel luarnya. Sisi-sisi dari graf helm berikut (i) sisi graf roda

dapat dikelompokkan sebagai

, dan (ii) sisi jari-jari. Awalnya warnai sisi graf roda

sesuai dengan pewarnaan pada graf roda

. Karena sisi

diberi warna

73

1, dan sisi


sehingga terdapat lintasan pelangi pada lintasan Selanjutnya ambil lintasan

ke

, karena sisi


sisi

dan lintasan

ke

.


diberi warna 1, maka untuk membuat

pelangi sisi terhubung pada lintasan warna 4. Selanjutnya pada lintasan

ke

diberi warna 3

ke ke


, maka haruslah sisi , karena sisi

diberi diberi warna 4,


diberi warna 5 agar terbentuk pelangi sisi terhubung pada lintasan

ke

. Jadi untuk sisi anting baru,agar terbentuk pelangi sisi terhubung haruslah diberi warna sesuai dengan jumlah sisi tambahannya, sehingga ketika sisi diberi warna 6 maka akan terbentuk pelangi sisi terhubung pada graf helm Jadi terbukti bahwa

.

.



berbeda, dibutuhkan tiga warna titik berbeda. Ambil lintasan melewati titik , lintasan ini melewati 2 titik yaitu titik diberi warna 1,dan titik pada lintasan

ke

tanpa

, sehingga titik

diberi warna 2. Dengan cara yang sama digunakan

. Kemudian agar dua titik terdapat lintasan dengan warna

titik interior yang berbeda, maka titik .

dan

ke

diberi warna 3 . Jadi terbukti bahwa

74

7 1 56

1

1

5

2

𝑯𝟓 :

1

1

1

1

2 5

1

3

2

2

2

2

1

1

4

3

2 2

1

3

4

4

3


Graf helm


adalah graf



sesuai dengan pewarnaan pada graf roda 1, dan sisi


. Karena sisi


sehingga terdapat lintasan pelangi pada lintasan Selanjutnya ambil lintasan

ke

ke

, karena sisi


diberi warna 3 dan lintasan

warna 4. Selanjutnya pada lintasan

ke ke


.





diberi warna 5 agar terbentuk pelangi sisi terhubung pada lintasan . Selanjutnya ambil lintasan

ke


pelangi sisi terhubung pada lintasan

sisi

diberi warna

ke

diberi warna 2, dan sisi sisi

, karena sisi

ke



diberi warna 6 agar terbentuk pelangi sisi terhubung. Selanjutnya ambil lintasan

ke

, karena sisi


diberi warna 1,

75

dan sisi sisi


diberi warna 7

agar terbentuk pelangi sisi terhubung. Jadi untuk sisi anting baru,agar terbentuk pelangi sisi terhubung haruslah diberi warna sesuai dengan jumlah sisi tambahannya. Jadi terbukti bahwa

.




ke

dan

ke

tanpa

, sehingga titik


. Kemudian agar dua titik terdapat lintasan dengan warna

titik interior yang berbeda, maka titik


. 1

8 7

6

62

𝑯𝟔 :

1 6 5

1

2

1

1 2

2

3

1 4

3

1

2

2

2

2

2 2

3

2

1

1

1

5

1

3

4

5 4


Graf helm


adalah graf




76

sesuai dengan pewarnaan pada graf roda diberi warna 1, dan sisi

. Selanjutnya Karena sisi


warna 3 sehingga terdapat lintasan pelangi pada lintasan ke

. Selanjutnya ambil lintasan

sisi

ke

dan lintasan

, karena sisi


diberi warna 2,



ke

warna 4. Selanjutnya pada lintasan sisi

ke

diberi

ke





diberi warna 5 agar terbentuk pelangi sisi terhubung pada lintasan . Selanjutnya ambil lintasan

ke


, karena sisi

ke




ke

dan sisi

, karena sisi



diberi warna 1, diberi warna 7 agar

terbentuk pelangi sisi terhubung. Selanjutnya ambil lintasan diberi warna 7, sisi 1, maka haruslah sisi


ke

, karena sisi diberi warna

diberi warna 8 agar terbentuk pelangi sisi

terhubung. Jadi untuk sisi anting baru,agar terbentuk pelangi sisi terhubung haruslah diberi warna sesuai dengan jumlah sisi tambahannya. Jadi terbukti bahwa . Sedangkan agar terbentuk pelangi titik yang terhubung, di mana setiap antara dua titik pada graf


berbeda, dibutuhkan tiga warna titik berbeda. Ambil lintasan

ke

tanpa

77

melewati titik , lintasan ini melewati 2 titik yaitu titik diberi warna 1,dan titik pada lintasan

ke

dan

, sehingga titik


, lintasan

ke

, lintasan

ke

dan lintasan

ke

. Kemudian agar dua titik terdapat lintasan dengan warna titik interior yang berbeda, maka titik


.

1

10 1 7

1

9 7

3

6

8

3

2 1

1 2

4

7

1

3

5

1

2 5

2

2

3

1

6

2

3

2

2

4

2

1

3

2

𝑯𝟕 :

1

1

3

6 4

5


Graf helm


adalah graf



sesuai dengan pewarnaan pada graf roda diberi warna 1, dan sisi maka haruslah sisi lintasan

ke

ambil lintasan warna 4, sisi


. Selanjutnya Karena sisi


diberi warna 3

diberi warna 4 sehingga terdapat lintasan pelangi pada , pada lintasan ke

ke

, dan lintasan

, karena sisi

ke



membuat pelangi sisi terhubung pada lintasan

. Selanjutnya diberi

diberi warna 1, maka untuk ke

, maka haruslah sisi

78

diberi warna 5. Selanjutnya pada lintasan diberi warna 5, sisi haruslah sisi lintasan

ke

ke

, karena sisi


diberi warna 2, maka

diberi warna 6 agar terbentuk pelangi sisi terhubung pada . Selanjutnya ambil lintasan

warna 6, sisi

ke

, karena sisi


haruslah sisi

diberi


diberi warna 7 agar terbentuk pelangi sisi terhubung.

Selanjutnya ambil lintasan

ke

, karena sisi





ke

dan sisi

, karena sisi


diberi warna 2,


diberi warna 9 agar

terbentuk pelangi sisi terhubung. Selanjutnya ambil lintasan diberi warna 9, sisi

ke

, karena sisi


diberi warna 10 agar terbentuk pelangi sisi terhubung. Jadi untuk sisi anting baru,agar terbentuk pelangi sisi terhubung haruslah diberi warna sesuai dengan jumlah sisi tambahannya. Jadi terbukti bahwa

.




ke

dan

ke

tanpa

, sehingga titik


, lintasan

ke

, lintasan

ke

dan lintasan

ke

79

. Kemudian agar dua titik terdapat lintasan dengan warna titik interior yang berbeda, maka titik



dan

.

pada

sampai


2 3 3 3 3

untuk


adalah graf gear

dengan



adalah:

untuk Bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf adalah: { Bukti: Graf helm

diperoleh dari graf roda

dengan menambahan sisi anting

baru pada titik sikel luar graf roda, sehingga sisi-sisi anting baru itu

80

menyerupai pohon. Dengan demikian graf helm titik dan (

mempunyai (

) sisi.

1. Bilangan pelangi sisi terhugung (rainbow edge-connection) pada graf a.

untuk untuk

, graf ini dibagi menjadi 2 graf,

yaitu graf roda dan sisi anting baru. Langkah pertama,warnai graf roda sesuai teorema 2. Sedangkan sisi anting baru, untuk memberikan warna pelangi sisi terhubung haruslah diberi warna yang berbeda sesuai dengan jumlah sisi tambahannya. Misalnya pada graf helm lintasan

ke

, bila lewat titik , maka lintasan ini menjadi

Sedangkan bila lewat


karena lintasan dapat langsung terhubung dari atau

, maka sisi

atau

. Ambil

ke

. . Namun

tanpa melalui


, ,

dapat diabaikan. Dengan cara yang sama dapat diterapkan

pada sisi

, sisi

, dan sisi


haruslah diberi warna 1 agar

terbentuk lintasan pelangi pada lintasan sisi


ke


. Selanjutnya karena diberi warna 1, maka

untuk membuat pelangi sisi terhubung pada lintasan

ke

maka sisi

haruslah diberi warna 3. Lalu untuk membuat pelangi sisi terhubung pada lintasan

ke

, karena sisi

diberi warna 3,

dan sisi


diberi

warna 3.

Atau dengan cara lain, sisi-sisi dari graf helm

dapat

81

dikelompokkan sebagai berikut (i) sisi graf roda jari. Awalnya beri warna sisi graf roda graf roda

, dan (ii) sisi jari-

sesuai dengan warna pada

yaitu 1. Yang kedua untuk sisi jari-jari agar terbentuk graf

pelangi sisi terhubung pada graf

, di mana setiap antara dua titik

terdapat lintasan dengan warna berbeda maka dibutuhkan minimal 3 warna sisi yang berbeda. Jadi terbukti

.

2. Bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf a.

jika Ambil lintasan

ke

menjadi

, bila lewat titik

dan titik

maka lintasan

. Karena dapat dilewati langsung dengan hanya

melewati titik

tanpa melewati titik

, maka titik


diberi warna 1. Dengan cara yang sama


dan lintasan

. Sedangkan

agar terbentuk pelangi titik yang terhubung, di mana setiap antara dua titik pada graf berbeda maka titik b.

terdapat lintasan dengan warna titik interior yang diberi warna 2. Jadi terbukti bahwa

.

jika Misalkan fungsi pewarnaan pelangi titik terhubung didefinisikan

,

,

untuk ganjil dan

untuk

genap, sehingga dengan tiga warna yang berbeda dapat membuat pelangi titik terhubung. Jadi terbukti bahwa

.

82

3.5 Graf Helm Tertutup Graf helm tertutup

merupakan graf yang diperoleh dari graf helm

dengan menghubungkan setiap titik pada anting-anting untuk membentuk sikel baru. Banyaknya titik pada

sama dengan banyaknya titik pada

, sedangkan banyaknya sisi pada banyaknya sisi pada

adalah

akan bertambah

yaitu

sisi sehingga

.

Bilangan pelangi sisi terhubung (rainbow edge-connection) dan bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf Helm tertutup dapat ditentukan dengan menentukan terlebih dahulu graf

,

, dan

dan

pada


agar terbentuk graf pelangi sisi terhubung. 1

1

2 𝒄𝑯 :

1 1

1

1 1

1 1

2

3

1

1

1

1 2

2

1

3

1 2

Gambar 3.21 Graf helm tertutup

Graf helm

mempunyai 12 sisi dan 7 titik. Graf helm tertutup

merupakan graf yang diperoleh dari graf helm dengan menghubungkan setiap titik pada anting-anting untuk membentuk sikel baru. Graf ini memiliki 2 sikel yaitu dan ke titik titik

. Ambil lintasan

. Yang mana titik ke


menghubungkan antara titik

, bila melewati titk

berarti juga melewati


83

tanpa melalui titik , yaitu hanya melalui titik . Misalnya sisi sehingga lintasan



ke

warna 2,

merupakan pelangi sisi terhubung. Dengan cara yang

sama diterapkan pada sisi-sisi yang lain maka akan terbentuk pelangi sisi terhubung dengan menggunakan 2 warna yang berbeda. Jadi terbukti bahwa . Sedangkan agar terbentuk pelangi titik yang terhubung, di mana setiap antara dua titik pada graf


berbeda, cukup dibutuhkan satu warna titik. Misalnya titik sehingga setiap lintasan

ke

1. Sedangkan lintasan walaupun lintasan

akan melewati titik

ke ke

diberi warna 1,

dimana titik

diberi warna

tidak ada titik interior karena terhubung langsung. melewati titik

, namun lintasan

ke

saling

terhubung langsung. dengan demikan dengan 1 warna dapat membuat pelangi titik terhubung. Jadi terbukti bahwa

. 1

1

1

3

1

1 𝑯𝟒 :

2

2

2

1

2

1

1 2

2

2

3 1 2

2

2 4

3 2

4

1

1 1

1

3

3 3

1


Graf helm


merupakan graf yang diperoleh dari graf helm dengan menghubungkan setiap titik pada anting-anting untuk membentuk sikel baru. Graf ini memiliki 2 sikel yaitu

84

dan antara titik

ke titik

melewati titik juga titik

. Yang mana titik . Ambil lintasan

ke


bila melewati titik ,


,

menghubungkan berarti

. Bila melewati titik

dan

. Sehingga bisa dikatakan bahwa

lintasan ini mempunyai panjang 3 sisi. Karena mempunyai panjang 3 sisi, maka misalnya sisi


sehingga lintasan

,

diberi warna 2, dan sisi ( ,

menjadi lintasan pelangi. Dengan cara yang sama

diterapkan pada sisi-sisi yang lain akan membuat pelangi sisi terhubung. Sehingga terbukti dengan menggunakan 3 warna berbeda dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa

.



berbeda, cukup dibutuhkan dua warna titik. Ambil lintasan melewati titik

dan titik

, misalnya titik

ke

diberi warna 2, maka titik

warna 1 sehingga terdapat pelangi titik terhubung pada lintasan Selanjutnya ambil 2, maka titik

ke

yang melewati titik

, misalnya titik

yang diberi ke

.

diberi warna

haruslah diberi warna 2 ini akan membuat lintasan

ke

menjadi lintasan pelangi. Sehingga terbukti dengan 2 warna yang berbeda dapat membuat pelangi titik terhubung. Jadi terbukti bahwa

.

85

1 3 1

3 1

1

3 1

5

1

1 4

2

1 1

4

2

3

2

2

2

2

3 2

1 1

2

1

2 2

1

1

5

𝑯𝟓 :

1

1

2

3

3 3

1

1


Graf helm


merupakan graf yang diperoleh dari graf helm dengan menghubungkan setiap titik pada anting-anting untuk membentuk sikel baru. Graf ini memiliki 2 sikel yaitu dan menghubungkan antara titik titik

dan titik

titik

, maka lintasan menjadi

. ke titik

Yang

mana

. Ambil lintasan

, lintasan ini menjadi ,

,

ke

titik

bila melewati


dan

. Lintasan ini bisa melewati titik lain,

namun membuat lintasan menjadi lebih panjang. Sehingga bisa dikatakan lintasan ini mempunyai panjang minimal 3 sisi. Karena mempunyai panjang minimal 3 sisi, maka misalnya sisi sisi

,


diberi warna 2, dan

diberi warna 3, ini akan membuat pelangi sisi terhubung pada

lintasan

,

. Karena sisi

sisi terhubung pada lintasan dan sisi

,

diberi warna 3, untuk membuat pelangi ,

, haruslah sisi

diberi warna 2. Selanjutnya karena sisi

sisi


diberi warna 1, ,

diberi warna 3,

haruslah diberi warna 1, dan sisi

diberi warna 2 sehingga terdapat lintasan pelangi pada lintasan ,



86


,

diberi warna 3. Lalu karena sisi

warna 3 dan sisi


1 sehingga lintasan

ke

,

diberi

diberi warna

terdapat lintasan pelangi. Selanjutnya untuk

membuat lintasan pelangi pada lintasan diberi warna 2 dan sisi

,

ke

, sisi


diberi warna 3. Lalu untuk sisi sikel luar

bisa diberi warna seperti pada teorema 1. Sehingga dengan 3 warna yang berbeda dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa

.




dan titik

, misalnya titik

ke



ke

yang melewati titik

, misalnya titik

yang diberi ke

.

diberi warna


ke

menjadi lintasan pelangi. Sehingga terbukti dengan 2 warna yang berbeda dapat membuat pelangi titik terhubung. Jadi terbukti bahwa

.

1

1

4 3

1

2 2

1

1

1

1

𝒄𝑯𝟔 :

4 6

1

1 2

4 1

5

5

2

2

4

1 1

3

2

1

3

4

4 4

1

3

1

2

1 1

4 2

2

2

2

6

2

2

1

2


1

87

Graf helm

mempunyai 24 sisi dan 13 titik. Graf ini memiliki 2 sikel

yaitu

dan

bila melewati titik

. Awalnya ambil lintasan

, titik , dan titik

maka menjadi

,

dapat dilewati langsung melalui dua titik, yaitu titik lintasan

,

,

, maka misalnya sisi


,


,

menjadi lintasan

1, dan sisi

menjadi ,

diberi warna 3. Dengan cara yang sama ,

. Sehingga lintasan


melalu titik

dan titik

,

. karena


lintasan pelangi. Selanjutnya ambil lintasan titik

,

ke

, ,

ke

ke

menjadi

, bila melewati titik

dan



diberi warna

diberi warna 2. Dengan menggunakan cara yang sama pada

lintasan yang berhubungan dengan titik setiap lintasan yang melewati titik

akan terbentuk lintasan pelangi, dimana

merupakan lintasan terdekat dibandingkan

menggunakan lintasan sikelnya. Sedangkan untuk membuat lintasan pelangi pada sisi sikel dalam dengan memberi warna 1 pada sisi warna 2 pada sisi

dengan

genap, maka akan tercipta pelangi sisi

terhubung. Selanjutnya ambil lintasan diberi warna 1, dan sisi

dengan ganjil, dan

ke

(

,

. Karena sisi sisi

diberi warna 2, maka haruslah sisi ( ,


ke

(

bukan

lintasan pelangi karena mempunyai 2 sisi yang diberi warna 3, yaitu sisi ( dan sisi

, jadi haruslah sisi ( ,

diberi warna 4. Dengan demikian

dengan memberi warna 4 pada semua sisi ( ,

akan terbentuk pelangi sisi

88

terhubung. Sehingga dengan 4 warna yang berbeda dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa

.




dan titik

, misalnya titik

ke



ke

yang melewati titik

, misalnya titik

yang diberi ke

.

diberi warna


ke

menjadi lintasan pelangi. Sehingga terbukti dengan 2 warna yang berbeda dapat membuat pelangi titik terhubung. Jadi terbukti bahwa 1

4

7

2

6

3 2

4

1

3

2

4

𝒄𝑯𝟕 : 3

1

4

1 7

.

1 6

4 1

2

3

3

2

1

1

3

1

3 1

5

1

5

2

2

2

2

2 3

4 1

3

2 4

2

4

3

2

3

2

1

3

3

4 2 4


Graf helm

mempunyai 28 sisi dan 15 titik. Graf ini memiliki 2 sikel

yaitu

dan

bila melewati titik

, titik , dan titik

. Awalnya ambil lintasan maka menjadi

dapat dilewati langsung melalui dua titik, yaitu titik lintasan

,

,


,

,

dan titik


ke

,

. karena menjadi ,

89


,

pelangi. Selanjutnya lintasan sisi (

, ,

ke

yang melewati titik


,

diberi warna 1. Lalu lintasan

, karena sisi haruslah sisi (

,

, ,

melewati titik (

diberi warna 3 sehingga terdapat lintasan

ke

yang melewati titik

diberi warna 3 dan sisi (

lintasan

,

ke

, karena sisi (

ke

,

,

diberi warna 1, maka ke

yang


,

diberi warna 3. Selanjutnya

. Sedangkan kalau diberi warna 2, lintasan ,

ke



juga bukan

diberi warna 4. Selanjutnya ambil dan titik


. Karena dapat dilewati langsung melalu titik

,

dan titik

diberi warna 1 atau 3 maka tidak ada lintasan pelangi pada

lintasan pelangi. Jadi haruslah sisi ( lintasan

,

diberi warna 2. Selanjutnya pada lintasan dan titik

, karena


diberi warna 2, maka haruslah sisi (

ketika sisi (

dan titik

menjadi lintasan


diberi warna

2. Lalu misalnya untuk lintasan sikel dalam diberi warna 1 pada sisi dengan ganjil, dan warna 2 pada sisi lintasan yang melewati titik , sisi

dengan


diberi warna 2 dengan genap, maka pada lintasan dan lintasan

ke

dengan

ke

, lintasan

ke

dan lintasan

dengan ganjil, dan warna

genap. Lalu sisi

diwarna 2, selanjutnya sisi lintasan

ke

tidak terdapat lintasan pelangi. Sehingga haruslah

lintasan sikel dalam diberi warna 1 pada sisi 2 pada sisi

genap. Sedangkan

ke


diberi warna 3. Ini akan membuat menjadi lintasan pelangi. Pada sisi

90


diberi warna 3 maka lintasan

lintasan pelangi. Lalu sisi membuat lintasan ke

(

ke ,


. Karena sisi

(

merupakan diberi warna 1

menjadi lintasan pelangi. Selanjutnya ambil lintasan

warna 2, maka haruslah sisi ( , ke

ke


diberi


bukan lintasan pelangi karena mempunyai 2 sisi yang

diberi warna 3, yaitu sisi (

dan sisi


diberi warna 4. Dengan demikian dengan memberi warna 4 pada semua sisi ( ,

akan terbentuk pelangi sisi terhubung. Jadi terbukti bahwa

.



berbeda, cukup dibutuhkan tiga warna titik. Ambil lintasan haruslah titik warna 1 dan titik

dan

ke

memilik warna yang berbeda. Misalkan titik

diberi warna 2. Dengan cara yang sama titik

, maka diberi

dan titik

harus memilik warna yang berbeda, jika melihat lintasan pelangi yang menghubungkan titik

dan

. Jika titik

diberi warna 1 dan titik

warna 2, tidak ada lintasan pelangi yang menghubungkan

dan

. Jika titik

diberi warna 2 juga tidak ada lintasan pelangi yang menghubungkan Jika titik

diberi warna 1. Sekarang misalnya titik

sama

diberi warna 1. Demikian Jika titik dan

dan

.


diberi warna 1, tidak ada lintasan pelangi yang menghubungkan titik

diberi

dan

Jika

diberi warna 2. Dengan alasan yang

haruslah mempunyai warna yang berbeda. Tetapi tidak ada

lintasan pelangi yang menghubungkan

dan

jika titik

diberi warna 1 dan

91

titik

diberi warna 2 dan tidak ada lintasan pelangi yang menghubungkan

jika titik


diberi warna 1. Jadi dibutuhkan

minimal 3 warna yang berbeda. Misalkan sebagai berikut titik titik

diberi warna 1 jika adalah ganjil dan titik

genap. Lalu titik jika

, titik

warna 2. Jadi terbukti bahwa

diberi warna 2


diberi

.


diberi warna 3,

diberi warna 2 jika adalah

diberi warna 3 jika adalah ganjil dan titik

adalah genap untuk

dan

dan

pada

sampai


1 2 2 2 3


adalah graf gear

dengan



{

adalah:

92

Bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf adalah:

{ Bukti: Graf ini memiliki 2 sikel yaitu untuk1

yang mana titik

dan menghubungkan antara titik

, ke titik

. 1. Bilangan pelangi sisi terhubung (rainbow edge-connection) pada graf a.

jika Ambil lintasan

ke

, bila melewati titk

berarti juga melewati titik

maka lintasan ini menjadi langsung tanpa melalui titik

. Karena dapat dilewati , yaitu hanya melalui titik

yang

. Misalnya sisi

diberi

membuat lintasan menjadi warna 1, maka sisi

warna 2, sehingga lintasan

ke

merupakan pelangi sisi terhubung. Dengan cara yang sama diterapkan pada sisi-sisi yang lain maka akan terbentuk pelangi sisi terhubung dengan menggunakan 2 warna yang berbeda. Jadi terbukti bahwa . b.

jika Ambil lintasan

ke


bila melewati titik ,

berarti melewati titik


dan juga

93

titik


,

. Sehingga bisa dikatakan

bahwa lintasan ini mempunyai panjang 3 sisi. Karena mempunyai panjang 3 sisi, maka misalnya sisi diberi warna 2, dan sisi (

,


sehingga lintasan

,

menjadi

lintasan pelangi. Dengan cara yang sama diterapkan pada sisi-sisi yang lain akan membuat pelangi sisi terhubung. Sehingga terbukti dengan menggunakan 3 warna berbeda dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa c.

.

jika Ambil lintasan menjadi menjadi

ke ,

bila melewati titik

. Bila melewati titik ,

dan titik dan titik

, lintasan ini , maka lintasan

. Lintasan ini bisa melewati titik lain, namun

membuat lintasan menjadi lebih panjang. Sehingga bisa dikatakan lintasan ini mempunyai panjang minimal 3 sisi. Karena mempunyai panjang minimal 3 sisi, maka misalnya sisi diberi warna 2, dan sisi

,

diberi warna 1, sisi diberi warna 3, ini akan

membuat pelangi sisi terhubung pada lintasan , lintasan

,

diberi warna 3, untuk membuat pelangi sisi terhubung pada ,

, haruslah sisi


diberi warna 2. Selanjutnya karena sisi sisi dan sisi lintasan

. Karena sisi


,

diberi warna 3,

haruslah diberi warna 1,

diberi warna 2 sehingga terdapat lintasan pelangi pada ,


diberi warna 1

94

dan sisi


karena sisi

,

,

diberi warna 3. Lalu


diberi warna 2,

maka haruslah sisi


ke

terdapat lintasan pelangi. Selanjutnya untuk membuat lintasan pelangi pada lintasan

ke

warna 2 dan sisi

, sisi

,


diberi

diberi warna 3. Lalu untuk sisi sikel luar bisa

diberi warna seperti pada teorema 1. Sehingga dengan 3 warna yang berbeda dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa . d.

jika Awalnya ambil lintasan titik

ke

maka menjadi

,

, bila melewati titik ,

. karena dapat dilewati langsung

melalui dua titik, yaitu titik , ,

,

dan titik

menjadi lintasan



,

yang sama digunakan pada lintasan ke

diberi warna 1, sisi diberi warna 3. Dengan cara ,

,

. Sehingga lintasan

menjadi lintasan pelangi. Selanjutnya ambil lintasan

bila melewati titik

dan titik


Karena dapat dilewati langsung melalu titik ,

, titik , dan


ke ,

, .

menjadi lintasan


diberi warna 2. Dengan menggunakan cara yang sama pada lintasan yang berhubungan dengan titik

akan terbentuk lintasan pelangi,

dimana setiap lintasan yang melewati titik

merupakan lintasan

95

terdekat dibandingkan menggunakan lintasan sikelnya. Sedangkan untuk membuat lintasan pelangi pada sisi sikel dalam dengan memberi warna 1 pada sisi dengan

dengan ganjil, dan warna 2 pada sisi genap, maka akan tercipta pelangi sisi terhubung.

Selanjutnya ambil lintasan

ke

(

diberi warna 1, dan sisi sisi ( ,

,

. Karena sisi sisi

diberi warna 2, maka haruslah


(

ke

bukan lintasan pelangi karena mempunyai 2 sisi yang

diberi warna 3, yaitu sisi ( ( ,

dan sisi

, jadi haruslah sisi

diberi warna 4. Dengan demikian dengan memberi warna 4

pada semua sisi ( ,

akan terbentuk pelangi sisi terhubung.

Sehingga dengan 4 warna yang berbeda dapat membuat pelangi sisi terhubung. Jadi terbukti bahwa e.

.

jika Awalnya ambil lintasan titik

maka menjadi

ke ,

, bila melewati titik ,

melalui dua titik, yaitu titik , ,

,

. karena dapat dilewati langsung dan titik



,

dan titik

, karena sisi

,

diberi warna 3 sehingga

,

ke

ke

yang melewati titik

yang melewati



Lalu lintasan

menjadi lintasan diberi warna 1, sisi

terdapat lintasan pelangi. Selanjutnya lintasan titik

, titik , dan

, dan titik

diberi warna 1. , karena sisi

96

,

diberi warna 3 dan sisi (

haruslah sisi (

,


diberi warna 2. Selanjutnya pada lintasan

yang melewati titik warna 1 dan sisi (

,

dan titik

,

, karena sisi (

,

kalau diberi warna 2, lintasan ,

ke

. Sedangkan

juga bukan lintasan pelangi.

diberi warna 4. Selanjutnya ambil lintasan


,

ke

dan titik


. Karena dapat dilewati langsung melalu titik

lintasan

,

,

diberi warna 1 atau 3

maka tidak ada lintasan pelangi pada lintasan

ke

diberi


diberi warna 3. Selanjutnya ketika sisi (

Jadi haruslah sisi (

,

ke


menjadi


diberi warna 2. Lalu misalnya untuk lintasan sikel dalam diberi warna 1 pada sisi dengan sisi

dengan ganjil, dan warna 2 pada sisi genap. Sedangkan lintasan yang melewati titik


dengan genap, maka pada lintasan lintasan

ke

ke

,

diberi warna 2

, lintasan

ke

dan

tidak terdapat lintasan pelangi. Sehingga haruslah

lintasan sikel dalam diberi warna 1 pada sisi dan warna 2 pada sisi warna 1 dan sisi

dengan

dengan ganjil,

genap. Lalu sisi


diberi warna

3. Ini akan membuat lintasan

ke

lintasan pelangi. Pada sisi


warna 3 maka lintasan

ke

dan lintasan

diberi

ke

menjadi diberi

merupakan lintasan pelangi. Lalu sisi

97

diberi warna 3 dan sisi ke (

diberi warna 1 membuat lintasan

menjadi lintasan pelangi. Selanjutnya ambil lintasan ,

. Karena sisi


warna 2, maka haruslah sisi ( , membuat lintasan

ke

ke diberi

diberi warna 3, namun ini

(

bukan lintasan pelangi

karena mempunyai 2 sisi yang diberi warna 3, yaitu sisi ( sisi


dan

diberi warna 4. Dengan

demikian dengan memberi warna 4 pada semua sisi ( , terbentuk pelangi sisi terhubung. Jadi terbukti bahwa

akan .

Dari uraian diatas (a,b,c,d, dan e) terbukti bahwa bilangan pelangi sisi terhubung (rainbow edge-connection) pada graf

adalah:

{

2. Bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf a.

jika Untuk membuktikan

maka akan dibuktikan bahwa

dengan 1 warna titik, dapat membentuk pelangi titik yang terhubung, artinya setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Ambil

, misalkan ada fungsi pewarnaan maka:

melewati titik interior

, sehingga setiap lintasan dimana

akan


tidak ada titik interior karena terhubung langsung, walaupun pada lintasan

terdapat titik interior

, namun lintasan

98

saling terhubung langsung, dengan demikian setiap dua titik terdapat lintasan dengan warna titik interior yang berbeda. Jadi terbukti . Karena

dan

, maka

. b.

jika Berikan 2 warna ,

seperti berikut,

jika

,

ganjil, dan

untuk

jika

genap. Sehingga

adalah pelangi titik terhubung. Oleh karena itu terbukti jika c.

jika Akan

ditunjukkan

bahwa

. Misalkan

.

Asumsikan

adalah pewarnaan titik pelangi pada

Perhatikan lintasan pelangi yang menghubungkan , maka Misalkan dan

bahwa

dan dan

dan

.

. Karena

haruslah memiliki warna yang berbeda. . Dengan cara yang sama maka

harus memiliki warna yang berebeda jika melihat lintasan

pelangi yang menghubungkan

dan

. Jika

, tidak ada lintasan pelangi yang menghubungkan

dan dan

jika

dan juga tidak ada lintasan pelangi yang menghubungkan dan

jika

. Sekarang misalnya

tidak ada lintasan pelangi yang menghubungkan . Demikian jika

dan dan

. Dengan alasan yang sama

, jika dan

haruslah mempunyai warna yang berbeda. Tetapi tidak ada lintasan

99

pelangi yang menghubungkan

dan

jika

dan

dan tidaka ada lintasan pelangi yang menghubungkan dan

dan

. Sehingga haruslah

.

Selanjutnya misalnya didefinisikan pewarnaan titik berikut,

,

jika

adalah genap. ,

bahwa

sebagai

adalah ganjil dan

jika adalah ganjil dan

genap untuk

jika

jika jika adalah

dan

. Ini menunjukkan

.

d.

jika Misalkan, dengan 4 warna pelangi.

,

kita dapat membuat pewarnaan titik jika

adalah genap,

. Sehingga . Misalnya

,

dapat membuat 3 warna

adalah satu-satunya lintasan , maka

warna yang berbeda. Misalkan maka

.

haruslah mempunyai dan

. Karena

Selanjutnya

. Dengan cara yang sama maka , maka

.

. Lalu untuk setiap dengan

dengan panjang 4 pada

,

jika

. Ini menunjukkan bahwa

Asumsikan bahwa pelangi dari

adalah ganjil,

; ;

,

sehingga

, maka

;

, maka ,

demikian tidak ada warna pelangi pada lintasan

; . Dengan , sehingga

100

haruslah

. Sehingga

. Karena

maka terbukti

dan

, dengan

.

3.6 Graf Bunga Graf bunga

adalah graf yang diperoleh dari graf helm dengan

menghubungkan setiap titik anting-anting ke titik pusat graf helm. Banyaknya titik pada

dan

bertambah

adalah sama yaitu

, sedangkan sisi pada

sisi sehingga banyaknya sisi pada

adalah

akan

.

Bilangan pelangi sisi terhubung (rainbow edge-connection) dan bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf bunga ditentukan dengan menentukan terlebih dahulu s/d graf

dan

dapat

pada graf


agar

terbentuk graf pelangi sisi terhubung. 1

1 1 1

1

𝑭𝒍 :

1

1 3

1 1

1

1 1

1

1

1

1

2

1

3

1 2

Gambar 3.26 Graf bunga

Graf bunga bila melewati titik langsung

ke


tanpa lewat titik

lintasan ke

mempunyai 12 sisi dan 7 titik. Ambil lintasan

ke

,

. Karena dapat dilewati

, maka sisi


dapat diabaikan. Dengan cara yang sama dapat diterapkan pada dan

ke


. Selanjutnya ambil lintasan . Sedangkan bila lewat

ke

, bila lewat titik , maka , maka lintasan ini menjadi

101

. Namun karena lintasan dapat langsung terhubung dari melalui

atau

atau

, maka sisi

ke

tanpa


, ,


, dan sisi

. Sehingga diperoleh bahwa



. ke

, karena


, sehingga lintasan lain dapat diabaikan. Maka dengan memberi warna 1 pada titik

akan membuat pelangi titik terhubung. Sehingga diperoleh bahwa . 1

3

2

2 1

𝑭𝒍𝟒 : 2 1

1

3

1

2

1

1 1

2

2

2

2

2 4

3

1

3

1

4

3 3


Graf bunga

mempunyai 16 sisi dan 9 titik. Ambil lintasan dari


, titik

, dan titik


. Karena dapat dilewati langsung tanpa melewati titik , hanya melewati titik

lintasan ini menjadai

diberi warna 2 dan sisi dapat diterapkan pada lintasan pada lintasan

dan lintasan

ke

dan titik

. Maka misalnya sisi

diberi warna 1. Dengan cara yang sama . Sehingga terdapat pelangi sisi terhubung . Selanjutnya ambil lintasan

bila lewat titik , maka lintasan ini menjadi

ke


,

102


. Lintasan ini juga bisa melewati titik

sehingga menjadi lintasan sisi

. Misalnya sisi

,


haruslah diberi warna 2, sehingga terdapat pelangi sisi terhubung pada

lintasan

. Cara ini juga dapat diterapkan pada lintasan , dan lintasan

dan sisi sisi

,lintasan


diberi warna 1,


diberi warna 3,

agar terdapat pelangi sisi terhubung. Sehingga dengan memberikan warna 3 pada setiap sisi

maka akan terdapat pelangi sisi terhubung secara keseluruhan.

Jadi terbukti bahwa

.



ke

, karena




3 2 5

1

3

1

5

𝑭𝒍𝟓 :

1

1

1

2 1

2 3

4

2

2

2 1 3

1

4

3

2

2 1

2 1

2

3 3


Graf bunga



ke


,

103


. Lintasan inipun dapat melewati titik

, sehingga lintasan menjadi

. Pada lintasan

dan

maupun

, sama-sama mempunyai panjang 2 sisi, sehingga misalnya salah satu yaitu lintasan

diberi warna masing-masing 1 untuk sisi

warna 2 untuk sisi

. Lalu pada lintasan

diwarna 2 dan sisi

ke

masing-masing sisi, sisi

, maka lintasan

lintasan pelangi. Ketika sisi ( pelangi pada lintasan

merupakan

diberi warna 1, maka tidak ada lintasan yang melewati titik

. Namun lintasan

dapat dibuat lintasan pelangi dengan melewati titik diberi warna 2 dan sisi (

dan

ke

yaitu ketika sisi (


ke

menjadi lintasan pelangi dengan mengabaikan lintasan Selanjutnya ambil lintasan

ke

lintasan ini menjadi melewati titik dan sisi

, bila lewat titik

, titik

.

, dan titik

. Karena dapat dilewati dengan hanya

lintasannya menjadi

, maka sisi

diberi warna 1,


dapat

diabaikan. Dengan cara yang sama dapat diterapkan pada lintasan

ke

lainnya, sehingga terdapat pelangi sisi terhubung pada lintasan Selanjutnya karena sisi 2, maka haruslah sisi


ke

.

diberi warna

diberi warna 3, agar terdapat pelangi sisi terhubung.

Sehingga dengan memberikan warna 3 pada setiap sisi

maka akan

terdapat pelangi sisi terhubung secara keseluruhan. Jadi terbukti bahwa .

yang

104



ke

, karena




1

3

𝑭𝒍𝟔 : 6

1

2

1

2

2

1

1

2 3

1 1

6

1

1

2 3

5

1

2

2

2

3

3

1

1

1

2 2

3

3

2

1 4

1

5

3 4


Graf bunga bila lewat titik


, titik , dan titik


dapat dilewati dengan hanya melewati titik sisi

ke

. Karena

lintasannya menjadi


,

, maka


dapat diabaikan. Dengan cara yang sama dapat diterapkan pada lintasan

ke

lintasan

ke

yang lainnya, sehingga terdapat pelangi sisi terhubung pada . Selanjutnya ambil lintasan

, maka lintasan ini menjadi lintasan ini menjadi menjadi lintasan warna 1 dan sisi

ke

, bila melewat titik

. Bila lewat titik

dan

. Namun karena dengan melewati titik merupakan lintasan terpendek, maka sisi

dan , maka yang diberi

diwarna 2. Dengan menggunakan cara yang sama pada

105

lintasan yang berhubungan dengan titik setiap lintasan yang melewati titik

akan terbentuk lintasan pelangi, dimana

merupakan lintasan terdekat dibandingkan

menggunakan lintasan sikelnya. Sedangkan untuk membuat lintasan pelangi pada sisi sikelnya dengan memberi warna 1 pada sisi warna 2 pada sisi

dengan

dengan ganjil, dan


terhubung. Selanjutnya karena sisi



diberi warna 3, agar terdapat pelangi

sisi terhubung. Sehingga dengan memberikan warna 3 pada setiap sisi maka akan terdapat pelangi sisi terhubung secara keseluruhan. Jadi terbukti bahwa . Sedangkan untuk pelangi titik terhubung. Ambil lintasan semua titik


ke

, karena




3

2

2

1

1 7

𝑭𝒍𝟕 :

1

7

3 1

2 2

1

1

1

6

5

2

1 5

4

1

3

3

1 2

1

2

1

2

3

2

2

2

3 6

3

2

3 4


3

106

Graf bunga bila lewat titik


, titik , dan titik


dapat dilewati dengan hanya melewati titik sisi

ke

. Karena

lintasannya menjadi


,

, maka



ke

lintasan

ke

yang lainnya, sehingga terdapat pelangi sisi terhubung pada . Selanjutnya ambil lintasan


ke


. Bila lewat titik


dan


dan , maka yang

menjadi lintasan


warna 1 dan sisi

diwarna 2. Lalu misalnya untuk lintasan sikel diberi

warna 1 pada sisi dengan

dengan ganjil, dan warna 2 pada sisi

genap. Sedangkan lintasan yang melewati titik

warna 1 dengan ganjil dan sisi lintasan

ke

diberi

, lintasan

, sisi

diberi

diberi warna 2 dengan genap, maka pada

ke

dan lintasan

ke

tidak terdapat lintasan

pelangi. Sehingga haruslah lintasan sikel diberi warna 1 pada sisi dengan ganjil, dan warna 2 pada sisi diberi warna 1 dan sisi

genap. Lalu sisi


Ini akan membuat lintasan pelangi. Pada sisi

dengan

ke

dan lintasan

ke


lintasan

ke

sisi

diberi warna 1 membuat lintasan

Selanjutnya karena sisi

menjadi lintasan diberi warna 3 maka

merupakan lintasan pelangi. Lalu sisi ke

diberi warna 3.

diberi warna 3 dan menjadi lintasan pelangi.


diberi warna

107


diberi warna 3, agar terdapat pelangi sisi terhubung.

Sehingga dengan memberikan warna 3 pada setiap sisi terdapat pelangi sisi terhubung. Kecuali pada sisi warna 1, karena sisi juga dengan sisi

maka akan yang harus diberi


diberi warna 3. Begitu

yang harus diberi warna 2, dan sisi

yang harus

diberi warna 1. Sehingga terbukti dengan 3 warna yang berbeda diperoleh pelangi sisi terhubung. Jadi terbukti bahwa

.



ke

, karena



akan membuat pelangi titik terhubung. Sehingga diperoleh bahwa .


dan

pada

sampai


1 1 1 1 1

Dari beberapa kasus yang ditunjukan oleh bilangan pelangi sisi terhubung (rainbow edge-connection) dan bilangan pelangi titik terhubung (rainbow vertexconnection) di atas maka dapat diperoleh teorema:

108

Teorema 6 Graf

adalah graf roda

dengan



adalah:

{ bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf adalah: untuk Bukti : Graf bunga

didapat dari graf helm

dengan menggabung tiap-tiap

titik puncak menuju titik pusat dari graf helm. 1. Bilangan pelangi sisi terhubung (rainbow edge-connection) pada graf a.

jika Ambil lintasan

ke


. Karena dapat dilewati langsung maka sisi

maka lintasan menjadi ke

tanpa lewat titik


dapat

diabaikan. Dengan cara yang sama dapat diterapkan pada ke

. Selanjutnya ambil lintasan

lintasan ini menjadi ini menjadi dari

ke

ke

ke

, bila lewat titik


,

dan , maka

, maka lintasan

. Namun karena lintasan dapat langsung terhubung tanpa melalui

sehingga lintasan

, ,

atau atau

, maka sisi

diberi warna 1.

dapat diabaikan. Dengan cara

109

yang sama dapat diterapkan pada sisi

, sisi

. Sehingga diperoleh bahwa b.

, dan sisi

.

jika Ambil lintasan dari

ke


lintasan ini menjadi tanpa melewati titik menjadai

, titik , dan titik

. Karena dapat dilewati langsung dan titik

, hanya melewati titik

. Maka misalnya sisi

lintasan ini


diberi warna 1. Dengan cara yang sama dapat diterapkan pada lintasan

.

lintasan

dan lintasan

ke

Sehingga terdapat pelangi sisi terhubung pada . Selanjutnya ambil lintasan


bila lewat


bisa melewati titik sisi

. Sedangkan . Lintasan ini juga

, sehingga menjadi lintasan


. Misalnya

haruslah diberi warna 2,

sehingga terdapat pelangi sisi terhubung pada lintasan juga dapat diterapkan pada lintasan lintasan


sisi sisi

,lintasan

. Cara ini , dan

diberi warna 1, dan


diberi

warna 3, agar terdapat pelangi sisi terhubung. Sehingga dengan memberikan warna 3 pada setiap sisi

maka akan terdapat

pelangi sisi terhubung secara keseluruhan. Jadi terbukti bahwa .

110

c.

jika Ambil lintasan

ke




Lintasan inipun dapat melewati titik menjadi

dan

. Pada lintasan

.

, sehingga lintasan

maupun

, sama-

sama mempunyai panjang 2 sisi, sehingga misalnya salah satu yaitu lintasan

diberi warna masing-masing 1 untuk sisi

warna 2 untuk sisi

. Lalu pada lintasan

sisi, sisi

dan

masing-masing

diwarna 2 dan sisi

, maka lintasan

merupakan lintasan pelangi. Ketika sisi ( warna 1, maka tidak ada lintasan pelangi pada lintasan melewati titik

. Namun lintasan

dengan melewati titik (

ke

yaitu ketika sisi (

, bila lewat titik

ini menjadi melewati titik

yang

diberi warna 2 dan sisi ke

menjadi

lintasan pelangi dengan mengabaikan lintasan ke

ke

dapat dibuat lintasan pelangi


ambil lintasan

diberi

. Selanjutnya

, titik , dan titik

lintasan

. Karena dapat dilewati dengan hanya lintasannya menjadi

warna 1, dan sisi

, maka sisi

diberi



ke

yang lainnya, sehingga terdapat

pelangi sisi terhubung pada lintasan diberi warna 1, dan sisi sisi

ke

. Selanjutnya karena sisi diberi warna 2, maka

111

haruslah sisi

diberi warna 3, agar terdapat pelangi sisi

terhubung. Sehingga dengan memberikan warna 3 pada setiap sisi maka akan terdapat pelangi sisi terhubung secara keseluruhan. Jadi terbukti bahwa d.

.

jika Ambil lintasan

ke

, bila lewat titik

ini menjadi

, titik , dan titik

lintasan


melewati titik

lintasannya menjadi

warna 1, dan sisi

, maka sisi

diberi



ke



ke

. Selanjutnya ambil

lintasan


dan

, maka lintasan ini

menjadi

. Bila lewat titik

dan

, maka lintasan ini

menjadi


ke

menjadi lintasan

yang



diwarna 2. Dengan menggunakan

cara yang sama pada lintasan yang berhubungan dengan titik

akan

terbentuk lintasan pelangi, dimana setiap lintasan yang melewati titik merupakan lintasan terdekat dibandingkan menggunakan lintasan sikelnya. Sedangkan untuk membuat lintasan pelangi pada sisi sikelnya dengan memberi warna 1 pada sisi 2 pada sisi

dengan

dengan ganjil, dan warna


112

terhubung. Selanjutnya karena sisi



diberi warna 3, agar

terdapat pelangi sisi terhubung. Sehingga dengan memberikan warna 3 pada setiap sisi

maka akan terdapat pelangi sisi terhubung

secara keseluruhan. Jadi terbukti bahwa e.

.

jika Ambil lintasan

ke

, bila lewat titik

ini menjadi

, titik , dan titik

lintasan


melewati titik

lintasannya menjadi

warna 1, dan sisi

, maka sisi

diberi



ke



ke

. Selanjutnya ambil

lintasan

dan

, maka lintasan ini

ke


menjadi

. Bila lewat titik

menjadi

dan

, maka lintasan ini


menjadi lintasan




lintasan sikel diberi warna 1 pada sisi warna 2 pada sisi melewati titik

dengan

, sisi

dengan ganjil, dan

genap. Sedangkan lintasan yang


diberi warna 2 dengan genap, maka pada lintasan lintasan

ke

yang

dan lintasan

ke

ke

,

tidak terdapat lintasan pelangi.

113

Sehingga haruslah lintasan sikel diberi warna 1 pada sisi dengan ganjil, dan warna 2 pada sisi sisi

dengan



diberi warna 3. Ini akan membuat lintasan ke sisi

menjadi lintasan pelangi. Pada sisi diberi warna 3 maka lintasan

pelangi. Lalu sisi membuat lintasan sisi

ke

dan lintasan

diberi warna 2 dan ke

merupakan lintasan


diberi warna 1

ke

menjadi lintasan pelangi. Selanjutnya karena


haruslah sisi

genap. Lalu


diberi warna 3, agar terdapat pelangi sisi

terhubung. Sehingga dengan memberikan warna 3 pada setiap sisi maka akan terdapat pelangi sisi terhubung. Kecuali pada sisi yang harus diberi warna 1, karena sisi dan sisi

diberi warna 2

diberi warna 3. Begitu juga dengan sisi

harus diberi warna 2, dan sisi

yang

yang harus diberi warna 1.

Sehingga terbukti dengan 3 warna yang berbeda diperoleh pelangi sisi terhubung. Jadi terbukti bahwa Atau

jika ,

. misalkan fungsi pewarnaan sisi

didefinisikan

oleh

secara

berputar. Jadi diperoleh sisi jari-jari adalah 1,2, atau 3. Kemudian sisi daun bunga yang memiliki lintasan jika , dan

mempunyai warna, , jika

jika . Lalu untuk

114

sisi sikelnya diberi warna sama dengan sisi jari-jari. Sehingga terbukti . 2. Bilangan pelangi titik terhubung (rainbow vertex-connection) pada graf

Ambil lintasan

ke

, karena semua titik

dengan titik , maka lintasan ini menjadi

berhubungan langsung , sehingga lintasan lain

dapat diabaikan. Maka dengan memberi warna 1 pada titik

akan

membuat pelangi titik terhubung. sehingga setiap lintasan

akan

melewati titik interior lintasan

diberi warna 1, sedangkan setiap

tidak ada titik interior karena terhubung langsung.

walaupun lintasan dimana

dimana titik

melewati titik interior

, ada lintasan kedua

tidak melewati titik interior. dengan demikian setiap dua

titik terdapat lintasan dengan warna titik interior yang berbeda. Sehingga terbukti bahwa

.

BAB IV PENUTUP

4.1 Kesimpulan Berdasarkan hasil pembahasan pada Bab III, maka dapat diambil kesimpulan, antara lain: ( ) adalah:

1. Rumusan umum untuk bilangan rainbow edge-connection a. Bilangan rainvow edge-connection pada Graf Sikel (

)

:

{ ⌈ ⌉

b. Bilangan rainvow edge-connection pada Graf Roda (

)

{

c. Bilangan rainvow edge-connection pada Graf Gear (

)

:

untuk

d. Bilangan rainvow edge-connection pada Graf Helm (

:

)

(

)

:

untuk

e. Bilangan rainvow edge-connection pada Graf Helm Tertutup (

)

{

f. Bilangan rainvow edge-connection pada Graf Bunga (

)

{

115

:

:

116

2. Rumusan umum untuk bilangan rainbow vertex-connection a. Bilangan rainvow edge-connection pada Graf Sikel

(

)

:

⌈ ⌉ ⌈ ⌉

{

b. Bilangan rainbow vertex-connection dari Graf Roda (

)

)

:

{

d. Bilangan rainbow vertex-connection dari Graf Helm (

:

{

c. Bilangan rainbow vertex-connection dari Graf Gear (

( ) adalah:

)

:

{

e. Bilangan rainbow vertex-connection dari Graf Helm Tertutup

(

:

) {

f. Bilangan rainbow vertex-connection dari Graf Graf Bunga (

)

:

untuk

4.2 Saran Pada skripsi ini, penulis hanya memfokuskan pada pokok bahasan masalah bilangan rainbow connection dan rainbow vertex-connection pada graf yang berkaitan dengan sikel, antara lain Graf Sikel, Graf Roda, Graf Gear, Graf Helm,

117

Graf Helm Tertutup, dan Graf Bunga. Maka dari itu, untuk penulisan skripsi selanjutnya, penulis menyarankan kepada pembaca untuk mengkaji masalah bilangan rainbow connection dan rainbow vertex-connection pada graf yang lain, misalnya graf Kubus dan lain-lain.

DAFTAR PUSTAKA Abdussakir. 2007. Ketika Kyai Mengajar Matematika. Malang: UIN Malang Press. Adi, F.S.. 2012. Bilangan Rainbow Connection dari Hasil Operasi Penjumlahan dan Perkalian Kartesius Dua Graf. Skripsi Tidak Diterbitkan. Malang: Jurusan Matematika UIN Maulana Malik Ibrahim Malang. Alisah, E. dan Dharmawan, E.P.. 2006. Filsafat Dunia Matematika. Jakarta: Prestasi Pustaka Publisher. Ariwibowo, S.. 2012. Total -Defisiensi Titik Graf Terhubung. Skripsi Tidak Diterbitkan. Malang: Jurusan Matematika UIN Maulana Malik Ibrahim Malang. Bondy, J.A. and Murty, U.S.R.. 1976. Graph Theory With Applications. London: MacMillan Press. Caro, Y.. 2008. On rainbow connection, Electronic Journal of Combinatorics, Vol 15, 1-13. Chandran, L.S. 2010. Rainbow Coloring of Graph. Bangalore: Indian Institute of Science. Chartrand, G. and Lesniak, L.. 1986. Graphs and Digraphs Second Edition. California: a Division of Wadsworth, Inc. Gafur, A.. 2008. Pewarnaan Titik pada Graf yang Berkaitan dengan Sikel. Skripsi Tidak Diterbitkan. Malang: Jurusan Matematika UIN Maulana Malik Ibrahim Malang. Gallian. J.A.. 2007. A dynamic Survey of Graph Labeling. Electronic journal combinatorics, Vol 3, 1-7. Hasanah, S.. 2007. Aplikasi Pewarnaan Graf Terhadap Penjadwalan Kuliah di Jurusan Matematika UIN Malang. Skripsi Tidak Diterbitkan. Malang: Jurusan Metematika UIN Maulana Malik Ibrahim Malang. Harary, F.. 1969. Graph Theory. Amerika: Addison-Wesley Publishing Company, inc. Krivelevich, M. dan Yuster, R.. 2010. The Rainbow connection of a graph is (at most) reciprocal to its minimum degree, School of Mathematics, Tel Aviv University. Li, X. and Sun, Y.. 2012. Rainbow Connections of Graphs. New York: Springer Science-Business Media. Li, X. and Liu, S.. 2011. Of 2-Connected Graphs. Tianjin. Nankai University.

118

119

Muftie, A.. 2004 Matematika Alam Semesta, Kodefikasi Bilangan Prima dalam Al-Qur’an. Bandung: PT Kiblat Buku Utama. Purwanto. 1998. Matematika Diskrit. Malang: IKIP Malang. Saondi, O.. 2003. Teori Graf. Kuningan: Rumah Buku Press. Shihab, Q.M.. 2004. Tafsir al-Misbah Pesan Kesan dan Keserasian Al-Qur’an. Jakarta: Lentera Hati.

KEMENTERIAN AGAMA RI UNIVERSITAS ISLAM NEGERI MAULANA MALIK IBRAHIM MALANG FAKULTAS SAINS DAN TEKNOLOGI Jl. Gajayana No. 50 DinoyoMalang (0341)551345 Fax. (0341)572533 BUKTI KONSULTASI SKRIPSI Nama NIM Fakultas/ Jurusan Judul Skripsi Pembimbing I Pembimbing II

: Ainul Rhofiq Tridissuwedhy : 08610015 : Sains dan Teknologi/ Matematika : Bilangan Pelangi Terhubung Pada Graf yang Berkaitan dengan Sikel : Abdussakir, M.Pd : Dr. H. Ahmad Barizi, M.A

No 1. 2. 3. 4. 5. 6.

Tanggal 14 September 2012 26 September 2012 28 September 2012 23 Oktober 2012 24 Oktober 2012 20 Maret 2013

7.

2April 2013

8. 9. 10. 11.

4 April 2013 11 April 2013 28 Mei 2013 28 Mei 2013

Hal Konsultasi Proposal Konsultasi Agama Revisi Proposal KonsultasiKeagamaan KonsultasiKeagamaan Konsultasi BAB III Konsultasi BAB III& BAB IV KonsultasiKeagamaan Revisi BAB III & BAB IV ACC BAB I s.d BAB IV ACC Keagamaan

TandaTangan 1. 2. 3. 4. 5. 6. 7 8. 9. 10. 11.

Malang, 28 Mei 2013 Mengetahui, Ketua Jurusan Matematika


BILANGAN PELANGI TERHUBUNG PADA GRAF YANG BERKAITAN DENGAN SIKEL SKRIPSI. Oleh: AINUL RHOFIQ TRIDISSUWEDHY NIM

Recommend Documents