BILANGAN KETERHUBUNGAN PELANGI KUAT PADA GRAF SKRIPSI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

BILANGAN KETERHUBUNGAN PELANGI KUAT PADA GRAF SKRIPSI Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun oleh: Natalya Dewi Hutami NIM: 133114002

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2017 i


STRONG RAINBOW CONNECTION NUMBER IN GRAPH A THESIS Presented as Partial Fulfillment of the Requirements to Obtain the Degree of Sarjana Sains Mathematics Study Program

Written by: Natalya Dewi Hutami Student ID: 133114002

MATHEMATICS STUDY PROGRAM DEPARTMENT OF MATEMATICS FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2017

ii


iii


iv


v


vi


ABSTRAK

Pada skripsi ini akan dibahas bilangan keterhubungan pelangi kuat untuk graf terhubung tak trivial dan graf lainnya seperti pohon, graf siklus, graf roda dan graf bipartit. Pendistribusian soal ujian nasional dan kertas suara PILKADA merupakan beberapa penerapan dari bilangan keterhubungan pelangi kuat pada graf. Pada pendistribusian soal ujian nasional dan kertas suara PILKADA, bilangan keterhubungan pelangi kuat digunakan untuk menentukan jumlah kelompok pengawalan pendistribusian. Kata kunci: bilangan keterhubungan pelangi kuat, graf, graf bipartit, graf siklus,graf terhubung tak trivial, graf roda, pohon.

vii


ABSTRACT

In this thesis strong rainbow connection number of a nontrivial connected graph and other graphs such as tree, cycle graph, wheel graph and bipartite graph will be discussed. The distribution of the national examination papers and PILKADA ballot papers are some applications of strong rainbow connection numbers of a graph. In the distribution of the national examination papers and PILKADA ballot papers strong rainbow connection numbers are used to determine the number of distributing escort groups. Keywords: strong rainbow connection number, graph,bipartite graph, cycle graph,nontrivial connected graph, wheel graph, tree.

viii


DAFTAR ISI

HALAMAN JUDUL DALAM BAHASA INDONESIA………………………….i HALAMAN JUDUL DALAM BAHASA INGGRIS…………………………….ii LEMBAR PERSETUJUAN PEMBIMBING…………………………………….iii LEMBAR PENGESAHAN……………………………………………………...iv PERNYATAAN KEASLIAN KARYA…………………………………………..v LEMBAR PERSETUJUAN PUBLIKASI KARYA ILMIAH…………………...vi ABSTRAK………………………………………………………………………vii ABSTRACT……………………………………………………………………viii DAFTAR ISI……………………………………………………………………..ix BAB I PENDAHULUAN………………………………………………………....1 A. Latar Belakang………………………………………………………...1 B. Rumusan Masalah……………………………………………………..7 C. Batasan Masalah……………………………………………………….7 D. Tujuan Penelitian……………………………………………………...7 E. Manfaat Penelitian…………………………………………………….8 F. Metode Penelitian……………………………………………………...8 G. Sistematika Penelitian…………………………………………………8 BAB II GRAF DAN PEWARNAAN SISI………………………………………10 A. Himpunan…………………………………………………………….10

ix


x B. Fungsi………………………………………………………………...14 C. Teori Graf……………………………………………………….........18 D. Jarak dan Keterhubungan………………………………………….....26 E. Macam-macam Graf………………………………………………….32 F. Pewarnaan Sisi Pada Graf………………………………………..…..38 BAB III BILANGAN KETERHUBUNGAN PELANGI KUAT PADA GRAF..45 A. Bilangan Keterhubungan Pelangi Pada Graf…………………………46 B. Bilangan Terhubung Pelangi Kuat Pada Graf………………………..52 C. Aplikasi………………………………………………………………83 BAB IV PENUTUP A. Kesimpulan…………………………………………………………..98 B. Saran………………………………………………………………...100 DAFTAR PUSTAKA


BAB I PENDAHULUAN

Pada bab ini akan dibahas tentang latar belakang, rumusan dan batasan masalah, tujuan dan manfaat penulisan, serta akan disertakan sistematika penulisan skripsi. A. Latar Belakang Teori graf merupakan salah satu cabang matematika yang penting untuk dipelajari karena dapat memberikan banyak manfaat dalam menyelesaikan permasalahan dalam kehidupan. Konsep teori graf diperkenalkan oleh seorang matematikawan Swiss yang bernama Leonhard Euler pada tahun 1736 ketika mencoba menyelesaikan masalah Jembatan Königsberg. Kota Königsberg di Prussia (sekarang menjadi Kaliningrad di Rusia) dibangun pada pertemuan dua buah cabang sungai Pregel. Kota Königsberg terdiri dari sebuah pulau dandaratan sepanjang tepi sungai yang dihubungkan oleh tujuh jembatan yang ditunjukkan pada Gambar 1.1.

Gambar 1.1. Ilustrasi Jembatan Kota Königsberg Pertanyaan yang muncul yaitu apakah mungkin seseorang dapat berjalan – jalan mengelilingi kota dengan diawali dan diahkiri di tempat yang sama dan tepat

1


2 melewati setiap jembatan satu kali. Dalam menyelesaikan masalah tersebut, Euler merepresentasikan peta Kota Königsberg ke dalam graf pada Gambar 1.2, di mana

titik

menggambarkan

daratan

dan

dan

menggambarkan tujuh jembatan.

Gambar 1.2. Graf Kota Königsberg Euler memberikan jawaban bahwa tidak mungkin seseorang dapat berjalan – jalan mengelilingi kotadiawalidan diakhiri di tempat yang sama dengan melewati setiap jembatan tepat satu kali. Graf

adalah pasangan himpunan (V(G), E(G)),dengan

himpunan tak kosong dari obyek – obyek yang disebut titik dan

adalah adalah

himpunan (mungkin kosong) pasangan tak berurutan dari titik – titik yang berbeda dari V yang disebut sisi, di mana setiap sisi dipasangkan dengan himpunan yang elemennya disebut titik ujung dari sisi tersebut. Dua buah titik dan dikatakan bertetangga jika dan hanya jika terhubung oleh sebuah sisi. Sebuah jalan dari titik uke titik v adalah barisan selang seling berhingga yang terdiri dari titik dan sisi yang bertetangga pada G dari titik – titik di G (Epp, 2010). Graf tak trivial jika banyaknya titik minimal dua (Chartrand dan Zhang, 2009).Dua titik u dan v dalam G dikatakan terhubung jika dan hanya jika ada jalan dari u ke v. Graf


3 Gdikatakan terhubung jika dan hanya jika setiap dua titik u, v

terhubung(Epp,

2010). Sebuah pewarnaan sisi pada graf Gadalah sebuah pemberian warna pada sisi – sisi dalam graf G, di mana satu warna untuk setiap sisi. Jika sisi- sisi yang bertetangga diwarnai dengan warna yang berbeda maka pewarnaan sisi dikatakan pewarnaan sisi sejati. Pewarnaan sisi - k adalah suatu pewarnaan sisi sejati yang menggunakan kwarna. Suatu graf G disebut graf yang sisi – sisinya dapat diwarnai –k

jika terdapat pewarnaan sisi –k pada G. Indeks kromatik G

dinotasikan dengan

adalah bilangan bulat positif terkecil k sedemikian

sehingga G merupakan graf yang sisinya dapat diwarnai–k (Chartrand dan Zhang, 2009). Dalam teori graf,konsep pewarnaan sisi mengalami perkembangan. Salah satu konsep baru dari pewarnaan sisi yaitu keterhubungan pelangi pada graf. Konsep keterhubungan pelangi pada graf diperkenalkan pada tahun 2006 oleh G. Chartrand, G.L. Johns, K.A. McKeon dan P. Zhang.Konsep ini termotivasi oleh ditemukannya kelemahan dalam pegiriman informasi pada agen pemerintahan Departemen Keamanan Dalam Negeri Amerika Serikat yang dibentuk tahun 2003, sebagai respon atas ditemukannya kelemahan dalam pengiriman informasi setelah terjadinya serangan teroris pada 11 September 2001. Keamanan informasi harus terjaga karena berhubungan langsung dengan keamanan nasional dan juga terdapat prosedur yang memungkinkan para agen pemerintah untuk mengakses informasi, sehingga setiap jalur pengiriman informasi membutuhkan suatu kata sandi dengan angka yang banyak. Muncul pertanyaan, berapa angka yang


4 dibutuhkan sedemikian sehingga tidak terjadi pengulangan kata sandi angka pada setiap agen pemerintahan. Lintasan dari u ke v adalah jalan dari u ke vdi mana tidak terjadi pe-ngulangan titik maupun sisi (Epp, 2010). Misalkan graf G adalah graf terhubung tak trivial dank adalah sebuah bilangan bulat positif, didefinisikan pewarnaan sisi , sehingga setiap dua sisi yang bertetangga boleh memiliki warna yang sama. Suatu lintasan u – v di G disebut lintasan pelangi jika tidak ada dua sisi pada lintasan tersebut yang memiliki warna yang sama. Graf

dengan

pewarnaanc disebut graf terhubung pelangi jika terdapat lintasan pelangi untuk setiap pasang titik

- ,

. Dalam hal ini pewarnaan c disebut pewarnaan

pelangi. Jika terdapat k warna di G maka pewarnaan c disebut pewarnaan-k pelangi. Selanjutnya bilangan bulat positif terkecilk sedemikian sehingga terdapat pewarnaan pelangi-k pada G disebut bilangan keterhubungan pelangi. Bilangan keterhubungan pelangi dari G dinotasikan dengan

(Chatrand dan Zhang,

2009). Jumlah sisi dalam sebuah jalan pada graf G disebut panjang jalan tersebut.Suatu lintasan geodesik antara dua titik u dan v pada graf G adalah lintasan u-v dengan panjang minimum. Jumlah sisi dalam suatu lintasan geodesik antara u dan v disebut jarak, yang dinotasikan dengan

(Buckley dan

Lewinter, 2003).Geodesik pelangi antara titik u dan v di G adalah suatu lintasan pelangi dengan panjang pewarnaan

.Graf G disebut terhubung pelangi kuat dengan

jika terdapat geodesik pelangi u – v untuk setiap dua titik u dan v

pada G. Dalam kasus ini pewarnaan

disebut pewarnaan pelangi kuat pada G.


5 Selanjutnya bilangan keterhubungan pelangi kuat pada suatu graf terhubung Gadalah bilangan bulat positif terkecilk sedemikian sehingga terdapat pewarnaan pelangi kuat-

pada G. Bilangan keterhubungan pelangi kuat dinotasikan dengan

(Chartrand dan Zhang, 2009). Dapat ditunjukkan bahwa

)

untuk setiap graf terhubung. Yang dimaksud dengan ukuran adalah jumlah sisi pada graf G. Eksetrisitas pada adalah jarak dari titik

ke suatu titik terjauh diG.

Diameter dari Gadalah maksimum dari eksentrisitas titik-titik di G(Buckley dan Lewinter, 2003). Jika terdapat graf terhubung tak trivial Gdengan ukuran dan memiliki diameter yang dinotasikan dengan

yaitu jarak

maksimum antara dua titik di G maka

Salah satu penerapan bilangan keterhubungan pelangi kuat pada graf adalah pendistribusian soal-soal ujian nasional. Pendidikan Nasional (Diknas) akan mendistribusikan soal-soal ujian nasional (UN) ke seluruh sekolah di kabupaten Jember (pelaksanaan UN SMA 2014). Soal ini bersifat rahasia sehingga membutuhkan tim pengawas pendistribusian soal UN yang terdiri dari unsur Universitas Negeri Jember (UNEJ), Lembaga Penjaminan Mutu Pendidikan (LPMP), Polisi resort (Polres), Diknas, dan pihak sekolah. Misal jalur untuk menjangkau sekolah-sekolah direpresentasikan pada Gambar 1.3di manaj merupakan pusat penyimpanan soal dan titik awal pendistribusian soal. Permasalahan yang muncul adalahbagaimana cara menentukan jumlah kelompok pengawalan pendistribusian soal UN.


6

Gambar 1.3.ContohJalur Pendistribusian Soal UN Ke Sekolah- Sekolah Di Kabupaten Jember

Peta jalur distribusi dapat digambar secara ulang menjadi graf dengan bentuk berbeda seperti pada Gambar 1.4.

Gambar 1.4. Graf Jalur Pendistribusian Soal UN Misalkan titik

adalah SMA yang akan

dituju dan setiap sisi pada graf tersebut menggambarkan jalur pendis-tribusian soal UN. Setiap sisi pada graf di atas dapat diberi warna sedemikian sehingga memenuhi pewarnaan pelangi.Dengan menggunakan bilangan keterhu-bungan pelangi kuat pada graf permasalahan ini dapat diselesaikan dengan lebih mudah. Didapatkan bahwa minimal warna yang digunakan untuk mewarnai seluruh sisi pada graf sehingga memenuhi sifat pewarnaan pelangi yaitu lima warna atau . Dengan

demikian dapat disimpulkan bahwa dibutuhkan lima

kelompok pengawal untuk mendistribusikan soal – soal UN dengan aman ke setiap sekolah yang ada.


7 Berdasarkan penjelasan di atas dalam tugas ahkir ini akan dibahas lebih lanjut mengenai bilangan keterhubungan pelangi kuat pada graf .

B. Rumusan Masalah Perumusan masalah yang akan dibicarakan pada tugas akhir ini adalah: 1. Apa yang dimaksud dengan bilangan keterhubungan pelangi kuat pada graf? 2. Bagaimana cara menentukan bilangan keterhubungan pelangi kuatpada graf? 3. Bagaimana penerapan bilangan keterhubunganpelangi kuat pada graf dalam kehidupan?

C. Batasan Masalah Pada tugas akhir ini dibatasi pada masalah-masalah sebagai berikut: 1. Graf yang digunakan yaitu grafpohon, graf siklus, graf roda, graf bipartit. 2. Pewarnaan yang digunakan adalah pewarnaan sisi pada graf. 3. Penulis tidak membahas mengenai algoritma perhitungan.

D. Tujuan Penulisan Tujuan dari penulisan tugas ahkir ini adalah sebagai berikut: 1. Mengetahui apa yang dimaksud bilangan keterhubungan pelangi pada graf. 2. Menentukan bilangan keterhubungan pelangi kuat pada graf.


8 3. Mengetahui penerapan bilangan keterhubungan pelangi kuat pada dalam kehidupan.

E. Manfaat penulisan Manfaat yang diharapkan dari penulisan tugas ahkir ini adalah memberikan motivasi kepada pembaca untuk mempelajari salah satu konsep baru dari teori graf yaitu bilangan keterhubungan pelangi kuat dan dapat mengetahui penerapan bilangan keterhubungan pelangi kuat dalam kehidupan.

F. Metode Penulisan Metode yang digunakan dalam penulisan tugas akhir ini adalah metode studi pustaka yaitu dengan membaca dan mempelajari buku-buku atau jurnal-jurnal yang berkaitan dengan bilangan keterhubungan pelangi kuat pada graf.

G. Sistematika Penulisan BAB I PENDAHULUAN A. Latar Belakang B. Rumusan Masalah C. Batasan Masalah D. Tujuan Penelitian E. Manfaat Penelitian F. Metode Penelitian G. Sistematika Penelitian


9 BAB II GRAF DAN PEWARNAAN SISI A. Himpunan B. Fungsi C. Teori Graf D. Jarak dan Keterhubungan E. Macam-macam Graf F. Pewarnaan sisi pada graf BAB III BILANGAN KETERHUBUNGAN PELANGI PADA GRAF A. Bilangan keterhubungan Pelangi Pada Graf B. Bilangan keterhubungan Pelangi Kuat Pada Graf C. Aplikasi BAB IV PENUTUP A. Kesimpulan B. Saran


BAB II GRAF DAN PEWARNAAN SISI

Pada bab ini akan dijelaskan dasar-dasar teori graf yang digunakan dalam penulisantugas akhir ini. Dasar-dasar teori meliputi: himpunan,fungsi, teori graf, jarak dan keterhubungan, macam-macam graf dan pewarnaan sisi pada graf. A. Himpunan Dalam kehidupan sehari-hari sering dijumpai penggunaan konsep himpunan, misalnya himpunan hewan berkaki empat, himpunan warna pelangi, himpunan fakultas di Universitas Sanata Dharma,

Himpunan

Mahasiswa Matematika (HMM), dan lain-lain. Konsep himpunan tidak hanya diterapkan secara intuitif dalam kehidupan, namun konsep himpunantelah dikembangkan menjadi konsep dasar dalam matematika. Pada subbab ini akan dijelaskan mengenai himpunan. Definisi 2.1 Himpunan adalah suatukumpulan atau koleksi objek-objek yang mempunyai kesamaan sifat tertentu dan dilambangkan dengan huruf besar.

Contoh 2.2 adalah himpunan semua bilangan asli. adalah himpunan semua bilangan bulat. adalah himpunan semua bilangan real.

10


11 Definisi 2.3 Suatu himpunanA dalam semesta X dikatakan himpunan bagian dari himpunan B jika dan hanya jika setiap anggota dari himpunanA juga merupakan anggota dari himpunanB. Secara matematis ditulis dengan

Definisi 2.4 Suatu himpunan Adikatakanberhinggajika banyaknya elemen yang termuat di Adapat dihitung.

Definisi 2.5 Kardinalitas dari himpunan berhinggaX adalah jumlah elemen yang termuat di dalamX. Kardinalitas dari himpunan berhingga X dinotasikan dengan |X|.

Definisi 2.6 Gabungan dua buah himpunan A dan B adalah himpunan semua elemen dari semesta yang merupakan anggota himpunanA atau anggota himpunan Bdan dinotasikan dengan

. Secara matematis ditulis dengan


12 Definisi 2.7 Irisan dua himpunan

dan

adalah himpunan semua elemen dari semesta

yang merupakan anggota dan anggota , dinotasikan dengan

. Secara

matematis ditulis dengan

Bila

maka

dan

disebut dua buah himpunan saling asing atau

saling lepas.

Definisi 2.8 Selisih dua buah himpunan

dan

adalah himpunan semua elemen dalam

semesta yang merupakan anggota himpunan dan dinotasikan dengan

dan bukan anggota himpunan

. Secara matematis ditulis dengan

Definisi 2.9 Hasil kali kartesius buah himpunan yang memuat semua rangkap setiap

, yaitu

terurut (

adalah himpunan A dengan

untuk


13 Definisi 2.10 Hasil kali kartesius dua buah himpunan pasangan terurut

dengan

dan

dan

adalah himpunan semua

dan dinotasikan dengan

.

Secara matematis ditulis dengan

Berikut merupakan contoh dari himpunan berhingga, himpunan bagian, kardinalitas dua buah himpunan, gabungan dua buah himpunan, irisan dua buah himpunan, selisih dua buah himpunan, hasil kali kartesius dua buah himpunan. Contoh 2.11 Misalkan 1.

dan

dan

. Maka diperoleh bahwa:

merupakan himpunan berhingga.

2. 3.

dan

4. 5. 6. 7.

Definisi 2.12 Partisi dari suatu himpunan A adalah himpunan bagian

keluarga berhingga himpunan-

dari A yang memenuhi:


14 a.

untuk setiap

, yaitu setiap himpunan bagian

tidak

kosong. b.

untuk setiap i dan j dengan

, yaitu setiap dua himpunan

bagian yang tidak sama adalah saling lepas (atau secara ekivalen, jika dua himpunan bagian beririsan, maka kedua himpunan bagian itu adalah sama). c.

yaitu gabungan semua himpunan bagian

adalah himpunan

.

Contoh 2.13 Misalkan bagian dari

. Maka keluarga himpunan- himpunan yaitu

merupakan suatu partisi dari .

B. Fungsi Pada subbab ini akan dibahas konsep relasi dan fungsi secara formal dam matematis meliputi definisi dan contoh tentang relasi, fungsi dan jenis fungsi. Definisi 2.14 Relasi dari himpunan A ke himpunan B adalah himpunan bagian dari

.

Ada beberapa cara untuk menyatakan relasi dua himpunanX dan Y, salah satunya menggunakan diagram panah. Pada diagram panah setiap elemen di X yang berelasi dengan elemen di Y dihubungkan dengan suatu anak panah.


15 Berikut merupakan contoh dari relasi dua himpunan dan cara penyajian relasi menggunakan diagram panah. Contoh 2.15 Diberikan dua buah himpunan

dan

maka

. Jadi

merupakan

relasi dari himpunan Cdan himpunanD seperti pada Gambar 2.1

Gambar 2.1. Relasi Dari Himpunan C Ke HimpunanD

Selanjutnya adalahrelasi khusus antara elemen-elemen dalam himpunan X dan elemen-elemen dalam himpunan Y. Definisi 2.16 Fungsi (pemetaan) adalah relasi khusus f antara elemen-elemen dalam suatu himpunan X dengan elemen-elemen dalam himpunan Y. Kekhususannya terletak dalam dua hal, yaitu a. Setiap elemen dalam himpunan Xberelasi dengan suatu elemen dalam himpunanY. b. Elemen dalam himpunan Yyang berelasi dengan elemen dari himpunan Xitu tunggal.


16 Fungsi dari himpunan X ke himpunan Y dinotasikan dengan , maka elemen

yang berelasi dengan elemen

disebut bayangan dari dan dilambangkan dengan

. Jika

itu oleh fungsi f .

Contoh 2.17 Misalkan

dan

.

Maka

relasi

merupakan suatu fungsidari himpunan F ke himpunan G, sedangkanrelasi

bukan merupakan fungsitetapi

merupakan relasi dari himpunan Fke himpunan G, sebab

berelasi

dengan lebih dari satuelemen di G yaitu a dan b,seperti yang terlihat pada Gambar 2.2.(b).

Gambar 2.2. (a) Fungsi Dari Himpunan FKe Himpunan G, (b) Relasi Himpunan FKe Himpunan G

Berikut ini dijelaskan pengertian fungsi injektif, surjektif dan bijektif beserta contohnya. Definisi 2.18 Suatu fungsi berlaku

disebut fungsi injektif jika dan hanya jika untuk setiap maka

.Sedangkan suatu

disebut fungsi surjektif jika dan hanya jika untuk setiap

fungsi terdapat


17 sedemikian sehingga

. Lalu suatu fungsi

bijektif (korespondensi satu-satu) jika fungsi

disebut fungsi

tersebut adalah fungsi injektif

dan sekaligus surjektif.

Contoh 2.19 Misalkan

,

dan

adalah suatu fungsi maka

merupakan fungsi injektif tetapi tidak surjektif sebab untuk

tidak terdapat

sedemikian sehingga

pada Gambar 2.3. Selanjutnya misalkan

seperti terlihat ,


dan merupakan

fungsi surjektif tetapi tidak injektif sebab

tetapi

seperti terlihat

pada Gambar 2.3. Sedangkan misalkan


merupakan fungsi injektif dan surjektif sehingga

dapat disebut fungsi bijektif seperti terlihat pada Gambar 2.3.

Gambar 2.3. (a) Fungsi Injektif, (b) Fungsi Surjektif,(c) Fungsi Bijektif .


18 Definisi 2.20 Atap dari suatu bilangan real x adalah bilangan bulat terkecil yang lebih besar atau sama dengan x dan dinotasikan dengan

.

Contoh 2.22 Misalkanx = 8.3 dan x = 9 maka berdasarkan Definisi 2.21 berturut-turut diperoleh

dan

.

C. Teori Graf Pada subbab ini akan dibahas mengenai teori graf meliputi definisi dan contoh graf, keterhubungan dan jenis graf Definisi 2.23 Graf G adalah pasangan himpunan

dengan

tak kosong dari obyek – obyek yang disebuttitik dan

adalah himpunan adalah himpunan

(mungkin kosong) pasangan tak berurutan dari titik–titik yang berbeda dari yang disebut sisi,di mana setiap sisi dipasangkan dengan himpunan yang elemennya disebut titik ujung dari sisi tersebut.

Contoh 2.24 Gambar 2.4 menyatakan graf A dengan


19

Gambar 2.4Graf A Sedangkantitik

dan

adalah titik ujung dari sisi

Definisi 2.25 Graf trivialadalah graf dengan satu titik. Sedangkangraf tak trivialadalah graf yang memiliki dua titik atau lebih.

Contoh 2.26 Perhatikan gambar di bawah ini.

Gambar 2.5. (a)Graf Taktrivial B, (b) Graf Trivial C Gambar 2.5 menunjukkan bahwa

dan

sehingga

jumlah titik pada graf B dan C berturut-turut 3 dan 1. Jadi graf B merupakan graf tak trivial sedangkan graf C merupakan graf trivial.


20 Definisi 2.27 Dua buah titik dikatakan bertetangga jika dan hanya jika terhubung oleh suatu sisi. Sisi tersebut dikatakan bersisiandengan setiap titik ujungnya.

Contoh 2.28 Perhatikan pada Gambar 2.5(b). Pada gambar tersebut titik dihubungkan oleh sisi titik

sehingga titik

tidak bertetangga dengan titik

sisi, sehingga sisi

dan

dan

dikatakan bertetangga, tetapi

sebab tidak dihubungkan oleh suatu

dikatakan bersisian dengan titik

.

Definisi 2.29 Dua buah sisi yang bersisian pada titik ujung yang sama disebut bertetangga.

Contoh 2.30 Perhatikan Gambar 2.5(a). Gambar tersebut menunjukkan sisi bersisihan pada titik ujung

, sehingga

dan

dan sisi

dikatakan bertetangga.

Definisi 2.31 Misalkan G adalah suatu graf. Gelung dari G adalah suatu sisi dengan satu titik ujung.


21 Contoh 2.32 Perhatikan gambar di bawah ini.

Gambar 2.6. Graf D Sisi

memiliki satu titik ujung yaitu titik

, sehingga

merupakan gelung

dariD.

Definisi 2.33 Misalkan Gadalah suatu graf. Sisi – sisi di G yang mempunyai himpunan ttik ujung yang sama disebut sisi pararel dari G.

Contoh 2.34 Pada Gambar 2.6, sisi dan

sehingga

dan

dan

menghubungkan dua titik yang sama yaitu

merupakan sisi pararel. Sedangkan

menghubungkan dua titik yang sama, maka

dan

dan

tidak

bukan merupakan sisi

pararel.

Definisi 2.35 Misalkan Gadalah graf dan v adalah titik pada G. Derajat v atau deg(v) adalah banyaknya

sisi yang bersisian dengan titik v. Sedangkanderajat


22 maksimal dari G adalah derajat terbesar dari titik-titik pada G dan dinotasikan dengan

.

Contoh 2.36 Perhatikan Gambar2.6.Gambar tersebut menunjukkan bahwa 1. Terdapat tiga sisi yang bersisihan dengan titik sehinggadeg

yaitu sisi

,

.

2. Terdapat dua sisi yang bersisihan dengan titik sehinggadeg

yaitu sisi

Jadi

dan

.

3. Terdapat satu sisi dan satu gelung yang bersisihan dengan titik sisi

dan

dan sehinggadeg

yaitu

.

.

Definisi 2.37 Suatu graf sederhana adalah graf yang tidak mempunyai gelung atau sisi pararel.

Contoh 2.38 PerhatikanGambar 2.5(a). Pada grafB tidak terdapat gelung atau sisi pararel, sehingga graf B merupakan salah satu contoh dari graf sederhana.


23 Definisi 2.39 Misalkan G adalah graf. Orde dari G, dinotasikan dengan

adalah jumlah titik - titik dalam graf

.

Contoh 2.40 Graf A pada Gambar 2.4 menunjukkan bahwa sehingga

,

.

Definisi 2.41 Misalkan G adalah graf, ukuran dari G adalah jumlah sisi dalam graf G. Ukuran graf G dinotasikan dengan

.

Contoh 2.42 Graf

A

pada

sehingga

Gambar

2.4

menunjukkan

bahwa

,

.

Definisi 2.43 Misalkan G adalah graf. Sebuah jalan W dari titik u ke titik v adalah barisan selang seling berhingga yang terdiri dari titik dan sisi yang bertetangga pada G dari titik – titik di G. Sehingga jalan disajikan dalam bentuk -

,


24 di mana

menyatakan titik-titik dan

dan untuk setiap

,

menyatakan sisi-sisi,

dan

-

adalah titik ujung dari

,

,

. Jalan dari

titik u ke titik v singkatnya disebut jalan u-v.

Jalan pada suatu graf

bisa dinyatakan hanya dengan barisan titik asalkan

tidak memuat sisi pararel. Jika di

tidak memuat sisi pararel maka setiap jalan

tidak menimbulkan dwimakna dan dapat dijelaskan dengan barisan titik

saja. Pada skripsi ini jalan dinyatakan dengan barisan titik apabila graf tidak memuat sisi pararel.

Contoh 2.44 Perhatikan Gambar 2.6. Untuk titik Oleh karena

dan

,

merupakan jalan

.

merupakan sisi pararel maka jalan dinyatakan menggunakan

barisan titik dan sisi. Untuk titik

dan

,

merupakan jalan

bisa nyatakan menggunakan barisan titik saja karena

dan

bukan merupakan sisi

pararel.

Definisi 2.45 Misalkan

adalah graf. Lintasan dari u ke v pada Gadalah jalan dari uke v di

mana tidak terjadi pengulangan sisi maupun titik. Lintasan dari uke v singkatnya disebut lintasan u-v.


25 Contoh 2.46 Perhatikan

Gambar

lintasan

2.5(a).

Pada

gambar

tersebut,

merupakan

.

Definisi 2.47 Jalan tertutup adalah jalan yang diawali dan diakhiri di titik yang sama.

Contoh 2.48 Perhatikan Gambar 2.6. Untuk titik

di graf D, jalan

merupakan

jalan tertutup pada graf D.

Definisi 2.49 Sirkuit pada G adalah jalan tertutup yang terdiri dari minimal satu sisi dan tidak terjadi pengulangan sisi.


Gambar 2.7. Graf E Jalan pengulangan sisi.

merupakan sirkuit pada graf E sebab tidak terjadi


26 Definisi 2.51 Siklus adalah lintasan yang diawali dan diakhiri di titik yang sama.

Contoh 2.52 Perhatikan Gambar 2.7. Pada gambar tersebut jalan bukan merupakan siklus karena terdapat pengulangan titik yaitu Sedangkan jalan

dan .

merupakan siklus pada graf E.

Definisi 2.53 Panjang dari suatu jalan adalah jumlah dari sisi – sisi di dalam sebuah jalan

Contoh 2.54 Perhatikan pada Gambar 2.7. Pada graf E, jalan jalan dari titik

ke

panjang jalan dari titik

, di mana , ke

,

merupakan

adalah sisi-sisi pada jalan, maka

adalah jumlah sisi-sisi pada jalan tersebut yaitu

tiga.

Definisi 2.55 Misalkan pada

adalah graf. Sebuah lintasan gedoesik antara titik

adalah lintasan -

antara titik udan vpada

dan titik

dengan panjang minimum. Lintasan gedoesik

singkatnya disebut geodesik - .


27 Contoh 2.56 Perhatikan Gambar 2.7. Untuk dua titik lintasan

dan

, lintasan

merupakan

dengan panjang dua, selanjutnya lintasan

lintasan dari titik

dengan panjang dua, lalu lintasan

merupakan lintasan dari titik

ke

dengan panjang dua, sedangkan lintasan

merupakan lintasan dari titik itu lintasan

merupakan

dengan panjang satu. Oleh karena

merupakan lintasan geodesik antara titik

dan

, sebab

lintasan tersebut memiliki panjang yang minimal dibanding lintasan lainnya.

D. Jarak dan Keterhubungan Definisi 2.57 Misalkan

adalah graf. Dua titik

dan

hanya jika terdapat sebuah jalan dari

ke

di

dikatakan terhubung jika dan

.


Gambar 2.8. Graf F Untuk dua titik titik

dan

Definisi 2.59

dan

terdapat jalan

dapat dikatakan terhubung.

dari

ke

, sehingga


28 Suatu graf

dikatakan graf terhubung jika dan hanya jika untuk setiap dua

titik

pada terhubung.

dan

Contoh 2.60 Perhatikan Gambar 2.8. Untuk setiap dua titik u dan v pada F terdapat jalan dari titik u kev maka Fmerupakan graf terhubung seperti yang terlihat pada Tabel 2.1. Tabel 2.1. Jalan dari titik u ke v untuk setiap , di F Jalan titik u ke v Titik v Titik u

Selanjutnya perhatikan gambar di bawah ini.

Gambar 2.9. Graf G Untuk dua titik

dan

pada graf G, tidak terdapat jalan dari titik

sehingga graf G tidak terhubung. Definisi 2.61

ke ,


29 Misalkan diberikan dua buah titik

pada graf G Jarak antara titik

didefinisikan sebagai banyaknya sisi dari suatu geodesik

-

dan

diG dan

dinotasikan dengan d(u,v).

Contoh 2.62 Perhatikan gambar berikut

Gambar 2.10. Graf H Untuk dua titik dan

ke

pada graf H,

merupakan geodesik antara titik

, dengan jumlah sisi adalah satu. Jadi d(u,v) = 1.

Definisi 2.63 Misal diberikan suatu titik

padaG,eksentrisitas pada v adalah jarak dari

titikv ke suatu titik terjauh di G.Eksentrisitas pada vdinotasikan dengane(v). Secara matematis ditulis dengan


30 Contoh 2.64 Perhatikan gambar berikut , akan dicari e( ).

Gambar 2.11. Graf I Untuk suatu titik 1. Lintasan 2. Lintasan 3. Lintasan

pada grafI diperoleh bahwa: merupakan geodesik

- dengan jumlah sisi 1.

merupakan geodesik


merupakan geodesik


4. Lintasan

merupakan geodesik


5. Lintasan

merupakan geodesik


6. Lintasan

merupakan geodesik


7. Lintasan

merupakan geodesik


Sehingga diperoleh jarak

ke setiap titik di Iseperti pada tabel dibawah ini.

Tabel 2.2.Jarak titik v1 ke setiap titik di I

Nilai d(v1, v) Titik v Titik 1 Jadi e( )

2

3 .

2

2

3

3


31 Definisi 2.65 Misalkan G adalah graf. Diameter dari Gadalah maksimum dari eksentrisitas titik-titik diG dan dinyatakan dengan diam(G).

Contoh 2.66 PerhatikanGambar 2.11, akan cari diam (I). Untuk dua titik setiap u, v di I diperoleh jarak dari titik u ke v dan eksentrisitas titik u, seperti pada Tabel 2.3. Tabel 2.3. Jarak setiap dua titik dan eksentrisitas setiap titik pada graf I Nilai d(u,v) V

Titik 1 1 2 3 2 2 3 3

u

1 2 1 2 3 2

2 1 1 2 2 3 3

3 2 1 3 3 4 5

2 1 2 3 1 1 4

2 1 2 3 1 2 2

3 2 3 4 1 2

e(u) 3 2 3 4 3 3 4 4

3 2 3 4 2 2 2

2

Jadi menurut Tabel 2.3, diam

.

Definisi 2.67 Graf

G

bijektif

dan

H

dikatakan

isomorfis

jika

terdapat

sebuah

fungsi

sedemikian sehingga setiap pasang titik u dan

vbertetangga di G jika dan hanya jika

dan

bertetangga di H. Fungsi

fyang mememenuhi syarat di atas disebut isomorfisma dari GkeH, dan Gdikatakan isomorfis dengan H,dinotasikan dengan

.


32 Contoh 2.68 Gambar 2.12menyatakan graf Jdan K. Fungsi dengan

,

,

f adalah fungsi bijektifdari

didefinisikan

,

. Dapat ditunjukkanbahwa ke

dan untuk setiap dua titik u dan v di

E, u dan v bertetangga jika dan hanya jika f (u)dan f (v) bertetangga pada Gambar 2.12.

(a) Gambar 2.12.(a)Fungsi bijektif dari

(b) ke

, (b) Graf

E. Macam-Macam Graf Pada bagian ini akan dibahas definisi dan contoh dari macam-macam graf dan gabungan graf. Definisi 2.69 Graf lengkap dengan n titik adalah suatu graf sederhana dengan n titik dan tepat satu sisi yang menghubungkan setiap pasang dari titik yang berbeda. Graf lengkap dengan n titik dinotasikan dengan


33 Contoh 2.70 Gambar 2.13 merupakan salah satu contoh dari graf lengkap.

Gambar 2.13. Graf


adalah graf sederhana. Graf

disebut pohon jika dan hanya jika

tidak memuat sirkuit dan terhubung.

Contoh 2.72

Gambar 2.14. Graf PohonL Gambar 2.14merupakan sebuah pohon, sedangkan Gambar 2.15 bukan merupakan sebuah pohon sebab memuat sirkut

Gambar 2.15. Graf M

.


34 Definisi 2.73 Graf bipartit lengkap dengan

titik adalah sebuah graf sederhana di mana

titik-titiknya dapat dipartisi menjadiU danW, dengan dan

yang memenuhi sifat-sifat berikut: untuk semua

i,

dan untuk semuaj, 1.

Terdapat sisi dari setiap titik

ke setiap titik

.

2.

Tidak terdapat sisi dari suatu

ke suatu titik

.

3.

Tidak terdapat sisi dari suatu

ke suatu titik

Graf bipartit lengkap dengan

titik dinotasikan dengan

.


Gambar 2.16. Graf Himpunan titik pada V( dengan U(

) dapat dipartisi menjadi U(

) = {v1, v3} dan U(

berikut: untuk semua i,

)

) = {v2, v4, v6}yang memenuhi sifat- sifat

dan untuk semua j,

1. Terdapat sisi dari setiap titik

ke setiap titik

.

2. Tidak terdapat sisi dari suatu

ke suatu titik

.

3. Tidak terdapat sisi dari suatu

ke suatu titik

Jadi graf di atas adalah graf bipartit

) dan W(

.


35 Definisi 2.75 Untuk

, graf siklusdengan n titik adalah suatu siklus dengan

siklus dengan

titik dinotasikan dengan

titik. Graf

.

Contoh 2.76 Gambar 2.17merupakan salah satu contoh dari graf siklus.

Gambar 2.17. Graf

Definisi 2.77 Jika

dan

adalah graf yang saling asing, gabungan

dengan

dan

adalah graf .

Contoh 2.78 Misalkan diberikan dua buah graf K2 dan K3 seperti gambar di bawah ini.

(a)

(b)

Gambar 2.18. (a) Graf K2, (b) Graf K3


36 HimpunanV(K2) = {v1, v2} dan V(K3) = {v3, v4, v5} maka diperoleh himpunan V(K2 K3) = { v1, v2, v3, v4, v5} dan E(K2 K3) = { v1, v2, v3, v4, v5} sehingga dapat dibentuk gaf K2

K3, seperti pada gambar berikut.

Gambar 2.19. Graf K2 K3

Definisi 2.79 Jika G danHadalah dua graf yang saling asing, penggabungan terbentuk dengan menambahkan sisi pada setiap titik sehingga setiap titik dan graf

sedemikian

terhubung dengan setiap titik

. Jika

berturut-turut memiliki m(G) dan n(H) titik, maka untuk membentuk haruslah menambahkan

sisi pada graf

.

Contoh 2.80 Perhatikan Gambar 2.18, akan dibentuk grafK2

K3.Graf K2 dan K3 berturut-

turut memiliki m(K2) = 2 dan m(K3) = 3 sehingga m(K2).m(K3) = 6. Untuk membentuk graf K2

K3 menambahkan sisi pada setiap titik di K2 sedemikian

sehingga setiap titik di K2 terhubung dengan setiap titik K3, dengan langkahlangkah nya yaitu tambahkan berturut-turut e5, e6 dan e7pada v1


37 sedemikiansehingga v1beturut-turut terhubung dengan v3,v4 dan v5seperti pada Gambar 2.20.

Gambar 2.20. Ilustrasi penambahan sisi pada v1 Selanjutnya tambahkan berturut-turut sisi e5, e6 dan e7 pada v2 sedemikian sehingga v1 berturut-turut terhubung dengan v3, v4 dan v5 seperti pada gambar berikut seperti pada Gambar 2.21.

Gambar 2.21. Ilustrasi penambahan sisi pada v2 Jadi terbentuklah penggabungan K2

K3 seperti pada gambar berikut.

Gambar 2.22. Penggabungan K2

K3


38 Definisi 2.81 Untuk

graf roda adalah graf hasil penggabungan dari

Graf roda dinotasikan dengan

dengan

.

.

Contoh 2.82 Perhatikan gambar-gambar di bawah ini.

Gambar 2.23. (a) Graf Gambar

2.23(a)

merupakan

, (b) Graf

, (c) Graf

penggabunganK1

C4

.Selanjutnya Gambar 2.23(b) merupakan penggabungan disebut

yang

disebut

K1

C5 yang

. Sedangkan Gambar 2.23(c) merupakan penggabungan K1

yang disebut

C6

.

F. Pewarnaan Sisi Pada Graf Pada subbab ini akan dibahas mengenai pewarnaan sisi pada graf, yang diberikan dalam definisi dan contoh-contoh. Definisi 2.83 Misalkan G adalah graf dengan himpunan sisi – sisi dari

. Himpunan bagian

dikatakan himpunan bebas jika tidak ada dua sisi di dalam himpunan


39 tersebut yang bertetangga. Sedangkan bilangan kebebasan sisi adalah jumlah maksimal sisi dari G dalam himpunan bebas.Bilangan kebebasan sisi dinotasikan dengan

.

Contoh 2.84 Diberikan sebuah graf N. Akan dicari bilangan kebebasan sisi dari N.

Gambar 2.24. Graf N Berdasarkan gambar diatas diperoleh bahwaH= J=

,K=

, I=

,

merupakan himpunan kebebasan sisi. Jadi

= 3.

Definisi 2.85 Sebuah pewarnaan sisi pada graf Gadalah pemberian warna pada sisi – sisi dalam graf , di mana satu warna untuk setiap sisi .

Contoh 2.86 Gambar2.25 menunjukkan pewarnaan sisi pada grafO, dengan himpunan warna {1, 2, 3, 4, 5}di mana 1=warna merah, 2=warna biru, 3=warna hijau, 4=warna jingga, 5=warna ungu.


40

Gambar 2.25. Graf

Dengan Pewarnaan Sisi-5

Definisi 2.87 Jika sisi- sisi yang bertetangga diwarnai dengan warna yang berbeda maka pewarnaan sisi dikatakan pewarnaan sisi sejati.

Contoh 2.88 Gambar 2.25 menunjukkan bahwa setiap dua sisi yang bertetangga memiliki warna yang berbeda, sehingga graf O menggunakan pewarnaan sisi sejati.

Definisi 2.89 Pewarnaan sisi - k adalah suatu pewarnaan sisi sejati yang menggunakan k warna.

Contoh 2.90 Pada Gambar 2.25, pewarnaan pada grafO menggunakan pewarnaan sisi-3.


41 Definisi 2.91 Misalkan diberikan pewarnaan sisi – k pada graf tak kosong G, dengan menggunakan 1,2,….,k warna dan misalkan

adalah himpunan

sisi – sisi di G yang diberi warna i. Maka himpunan – himpunan tak kosong dari E(G) disebut kelas warna sisi dari G untuk pewarnaan sisi – k yang diberikan.

Contoh 2.92 Perhatikan Gambar 2.25, akan dicari kelas warna sisi dari graf O. Gambar 2.25 menunjukkan bahwa 1. Sisi

dan

diberi warna warna merah. Jadi

,

, dengan 1 =

warna merah. 2. Sisi

dan

diberi warna warna biru. Jadi

,

, dengan 2 =

warna biru. 3. Sisi

dan

diberi warna warna hijau. Jadi

, dengan 3 =

warna hijau 4. Sisi

diberi warna warna hijau. Jadi

dengan 4 = warna

jingga. 5. Sisi

diberi warna warna ungu. Jadi

dengan 4 = warna ungu.

Definisi 2.93 Misalkan G adalah graf. Suatu graf G disebut graf yang sisi – sisinya dapat diwarnai –k jika terdapat pewarnaan sisi –k pada G.


42 Contoh 2.94 Perhatikan gambar di bawah ini.

Gambar 2.26. Graf O Dengan Pewarnaan Sisi Karena terdapat pewarnaan sisi sisinya dapat diwarnai

denganpadaO maka O adalah graf yang sisi-

.

Definisi 2.95 Misalkan G adalah graf dengan pewarnaan sisi sejati. Indeks kromatik dari G adalah jumlah minimum warna yang diperlukan sedemikian sehingga sisi – sisi yang bertetangga di G diwarnai dengan pewarnaan sisi sejati. Indeks kromatik pada graf G dinotasikan dengan

.

Contoh 2.96 Perhatikan Gambar 2.26. Gambar tersebut menunjukkan bahwa graf O dapat diwarnai menggunakan minimal tiga warna, sehingga indeks kromatiknya atau

.

Teorema 2.97 Jika G adalah graf tak kosong dengan ukuran

maka


43 Bukti: Misalkan G adalah graf dan

. Himpunan

adalah kelas

warna sisi pada pewarnaan sisi – k dari graf G. Berarti ada sisi di G yang tidak termuat di

Karena

maka

dariE(G). Sehingga

Jadi

untuk setiap i

merupakan partisi . Oleh karena itu

yang ekivalen dengan

, sehingga .

 Karena grafG diwarnai dengan pewarnaan sisi-k berarti sisi – sisi yang bertetangga di G diberi kwarna berbeda. Suatu sisi dikatakan bertetangga jika bersisian dengan suatu titik yang sama. Pewarnaan sisi pada sebuah grafG harus memberikan warna yang berbeda pada sisi-sisi yang bertetangga sehingga untuk setiap titik v di G jumlah warna yang digunakan untuk mewarnai sisi yang bersisian dengan titik v harus sesuai dengan derajat titik v pada G atau deg

. Jadi (1)


44 Contoh 2.98 Diberikan graf P dan pewarnaan sisi-4, dengan himpunan warna {1,2,3,4} di mana1=warna merah, 2=warna biru, 3=warna hijau, 4=warna jingga. Akan dicari

.

Gambar 2.27.GrafP Gambar 2.27 menunjukkan graf P dengan orde

dan ukuran

Himpunan kebebasan sisi yang dapat dibentuk antara lain:A={ , B={ ,

,

}, C={ ,

,

,

},

}. Sehingga berdasarkan Definisi 2.83didapatkan

, maka menurut Teorema 2.97 diperoleh bahwa Karena

.

merupakan bilangan bulat maka

pada Gambar 2.27 menunjukkan bahwa

. . Pewarnaan sisi-4

. Jadi didapatkan


BAB III BILANGAN KETERHUBUNGAN PELANGI KUAT PADA GRAF

Konsep bilangan keterhubungan pelangi merupakan salah satu variasi dari pewarnaan sisi. Bilangan keterhubungan pelangi diperkenalkan oleh Chartrand, Johns, McKeon and Zhang pada tahun 2006. Konsep baru ini dilatarbelakangi oleh ditemukannya kelemahan dalam pegiriman informasi pada agen pemerintahan. Departemen Keamanan Dalam Negeri Amerika Serikat dibentuk tahun 2003 sebagai respon atas ditemukannya kelemahan dalam pengiriman informasi setelah terjadinya serangan teroris pada 11 September 2001. Keamanan informasi harus terjaga karena berhubungan langsung dengan keamanan nasional dan juga terdapat prosedur yang memungkinkan para agen pemerintah untuk mengakses informasi, sehingga setiap jalur pengiriman informasi membutuhkan kata sandi angka yang banyak. Muncul pertanyaan, berapa jumlah minimal angka yang dibutuhkan sedemikian sehingga tidak terjadi pengulangan kata sandi angka pada setiap satu lintasan komunikasi atau lebih antara dua agen pemerintahan. Pertanyaan tersebut dapat dimodelkan dengan bilangan keterhubungan pelangi. Pada bab ini akan dijelaskan mengenai bilangan keterhubungan pelangi kuat pada graf meliputi definisi, contoh dan teorema.

45


46

A. Bilangan Keterhubungan Pelangi Pada Graf Pada subbab ini akan dibahas mengenai lintasan pelangi, graf terhubung pelangi, pewarnaan pelangi dan bilangan terhubung pelangi meliputi definisi, contoh dan teorema. Definisi 3.1 Misalkan graf G adalah graf terhubung tak trivial dan

adalah sebuah

bilangan bulat positif. Didefinisikan pewarnaan sisi

,

sehingga dua sisi yang bertetangga dapat memiliki warna yang sama. Suatu lintasan dari titik u ke v di G disebut lintasan pelangi jika tidak ada dua sisi pada lintasan tersebut yang memiliki warna yang sama.

Contoh 3.2 Perhatikan graf

dengan pewarnaan sisi – 3, dengan himpunan

warna {1, 2, 3} di mana 1=warna merah, 2=warna biru, 3=warna hijau. Akan ditunjukkan bahwa terdapat lintasan pelangi di P.

Gambar3.1. Graf Petersen Dengan Pewarnaan Sisi Untuk setiap dua titik u dan v terdapat lintasan pelangi dari titik u ke vsepertiyang dijelaskan pada Tabel 3.1.


47

Tabel 3.1. Lintasan pelangi untuk setiap dua titik pada graf Jalan v

Titik

Tabel 3.2. Lanjutan Tabel 3.1

Titik

Jalan v

Definisi 3.3 Misalkan graf G adalahgraf terhubung tak trivial dan sebuah bilangan bulat positif

. Didefinisikan pewarnaan sisi

, sehingga dua

sisi yang bertetangga dapat memiliki warna yang sama. Graf G dengan


48

pewarnaan sisi

disebut terhubung pelangi jikauntuk setiap pasang titik

terdapat lintasan pelangi.

Contoh 3.4 Graf Petersen pada Gambar3.1dapat dikatakan terhubung pelangi sebab menurut Tabel3.1 dan Tabel 3.2 setiap dua titik pelangi

dan

di

terdapat lintasan

. Sedangkan graf Q dengan pewarnaan sisi 3 yang himpunan

warnanya {1, 2, 3} seperti pada Gambar 3.2 bukan terhubung pelangi, sebab tidak terdapat lintasan pelangi - .Warna merah menyatakan warna 1, warna biru menyatakan warna 2 dan warna hijau menyatakan warna 3.

Gambar3.2. Graf Q Dengan Pewarnaan Sisi

Definisi 3.5 Misalkan jika

adalah graf. Pewarnaan sisi pada

pewarnaan

itumenyebabkan

graf terhubung

pewarnaan pelangi yang menggunakan – .

dikatakan pewarnaan pelangi pelangi.

Sedangkan

warna disebut pewarnaan pelangi


49

Contoh 3.6 Pewarnaan sisi

graf

karena menyebabkan

pada Gambar3.1 merupakan pewarnaan pelangi terhubung pelangi. Sedangkan pewarnaan sisi

graf

Q dengan pada Gambar3.2 bukan pewarnaan pelangi karena tidak menyebabkan Qterhubung pelangi.


adalah graf terhubung tak trivial.Bilangan bulat positif terkecil

sedemikian sehingga terdapat pewarnaan pelangi

pada

disebut bilangan

keterhubungan pelangi pada G. Bilangan keterhubungan pelangi pada dinotasikan dengan

.

Selain dalam pengamanan informasi rahasia antar agen pemerintahan, bilangan keterhubungan pelangi juga diterapkan pada bidang jaringan. Misalkan

menyatakan suatu jaringan seluler. Misalkan akan dikirim sebuah

pesan antara dua titik, pengiriman informasi tersebut dengan syarat bahwa rute antara dua titik (direpresentasikan sebagai sisi pada lintasan di suatu

saluran

atau

(saluran

direpresentasikan

sebagai

) diberikan warna).Akan

diminimalkan jumlah saluran berbeda yang digunakan. Jumlah saluran minimal yang digunakan dimodelkan dengan bilangan keterhubungan pelangi pada graf

. Permasalahannya adalah bagaimana cara untuk menentukan

bilangan keterhubungan pelangi tersebut.Selanjutnya diberikan Teorema 3.8 untuk mempermudah menentukan bilangan keterhubungan pelangi.


50

Teorema 3.8 Misalkan adalah graf terhubung tak trivial maka

.

Bukti: Misalkan G adalah graf dengan pewarnaan sisi c dan

. Sehingga

berdasarkan Definisi 2.61 danDefinisi 2.63maka

Ini berarti terdapat dua titik di , misal dengan panjang

dan

yang dihubungkan geodesik

. Oleh karena geoesik

adalah geodesik

terpanjang sehingga minimal warna yang diperlukan untuk mewarnai graf sedemikian sehingga setiap dua titik adalah

dan

di

terdapat lintasan pelangi

warna .Oleh karena itu

 Contoh 3.9 Berdasarkan Gambar3.1 terdapat pewarnaan pelangi berarti Sebelum mencari

Oleh karena

pada graf Petersen

maka akan dicari

.

terlebih dahulu dicari jarak setiap dua titik dan

eksentrisitas setiap titik di P yang yang disajikan pada Tabel 3.3.


51

Tabel 3.3. Jarak setiap dua titikdi graf Nilai Titik

v 1 1 2 2 2 2 2 1 2 2

u

1 2 2 2 1 2 2 2

2 1 1 2 2 2 2 2 1

2 2 1 1 2 2 1 2 2

2 2 2 1

1 2 2 2 1

1 1 2 2 2

2 2 2 1

2 1 2 2 1 2 2 1 2

1 2 2 1 2 2 2

2 2 2 2 2 2 1 1

1 2

e(v) 2 2 2 2 2 2 2 2 2 2

2 2 1 2 2 1 2 2 1

1

Berdasarkan Tabel 3.2 dan Tabel 3.3didapatkan menurut Teorema 3.8 diperoleh bahwa pewarnaan pelangi

, sehingga Namun tidak terdapat

di , sebab jika diberikan suatu pewarnaan sisi

dan didefinisikan sebagai pemberian dua warna pada sisi-sisi di dua sisi yang berwarna sama yaitu

dan

pada terdapat

seperti pada Gambar3.3.

Gambar3.3. Graf Petersen Dengan Pewarnaan Sisi Sehingga lintasan pelangi. Jadi

bukan lintasan pelangi, maka . Oleh karena

maka

tidak terhubung .


52

B. Bilangan Keterhubungan Pelangi Kuat Pada Graf Pada subbab ini akan dibahas mengenai pelangi geodesik, pewarnaan pelangi kuat, terhubung pelangi kuat,bilangan keterhubungan pelangi dan bilangan keterhubungan pelangi kuat pada graf terhubung tak trivial, graf pohon, graf siklus, graf roda dan graf bipartit meliputi definisi, contoh dan teorema. Definisi 3.10 Misalkan

adalah pewarnaan sisi pada graf terhubung tak trivialG. Untuk dua

titik u dan v di G, suatu pelangi geodesik dengan panjang

adalah lintasan pelangi

-

.

Contoh 3.11 Gambar3.4 menunjukkan graf Petersen dengan pewarnaan sisi suatu titik

dan

, lintasan

adalah lintasan pelangi dengan panjang

. Sehingga lintasan pelangi Sedangkan lintasan

. Untuk

adalah pelangi geodesik - .

bukan pelangi geodesik -

memiliki panjang minimum.

Gambar3.4. Graf Petersen Dengan Pewarnaan Sisi

sebab tidak


53

Definisi 3.12 Suatu graf terhubung tak trivial G dikatakan terhubung pelangi kuat jikaG memuat pelangi geodesiku-v untuk setiap titik u dan v diG.

Contoh 3.13 Graf Petersen P dengan pewarnaan sisi

pada Gambar3.4 terhubung pelangi

kuat sebab graf P memuat lintasan pelangi geodesik u-v untuk setiap titik u danv di . Tabel 3.5. Pelangi geodesik untuk setiap dua titik pada graf P Pelangi geodesik Titik

Tabel 3.6. Lanjutan Tabel 3.5 Pelangi geodesik Titik


54

Sedangkan graf P dengan pewarnaan sisi

pada Gambar3.1 terhubung

pelangi tapi tidak terhubung pelangi kuat sebab tidak terdapat pelangi geodesik

.

Definisi 3.14 Misalkan G adalah graf. Pewarnaan sisi pada G dikatakan pewarnaan sisi pelangi kuat jika pewarnaan itu menyebabkan graf

terhubung pelangi kuat.

Pewarnaan sisi pelangi kuat singkatnya disebut pewarnaan pelangi kuat. Sedangkan pewarnaan pelangi kuat yang menggunakan

warna disebut

pewarnaan pelangi kuat – .

Contoh 3.15 Pewarnaan sisi

graf Petersen pada Gambar3.4 merupakan pewarnaan

pelangi kuat sebab menyebabkan graf Pterhubung pelangi kuat. Sedangkan pewarnaan sisi pelangi kuat

Definisi 3.16

graf Petersen pada Gambar3.1 bukan merupakan pewarnaan sebab tidak menyebabkan graf P terhubung pelangi kuat.


55

Misalkan G adalah graf terhubung tak trivial.Bilangan bulat positif terkecil sedemikian sehingga terdapat pewarnaan pelangi kuat

pada Gdisebut

bilangan keterhubungan pelangi kuat pada G. Bilangan keterhubungan pelangi kuat pada

dinotasikan dengan

.

Teorema3.17 Misalkan G adalah graf terhubung tak trivial, maka Bukti: Misalkan G adalah suatu graf terhubung tak trivial dengan sehingga terdapat pewarnaan pelangi terdapat pewarnaan pelangi

pada G Oleh karena

di G, ini berarti terhubung pelangi. Sehingga

terdapat lintasan pelangiu-v, untuk setiap pasang titik u,v Kasus 1: Misalkan untuk setiap pasang titik pelangi

. Karena

. , terdapat

yang merupakan pelangi geodesik

, berarti

terhubung pelangi kuat sehingga pewarnaan sisi pewarnaan pelangi kuat Kasus 2: Misalkan untuk suatu titik

lintasan

merupakan

. Jadi dan

, setiap lintasan pelangi

bukan merupakan pelangi geodesik, ini berarti pelangi kuat. Oleh karena itu pewarnaan sisi

tidak terhubung bukan pewarnaan

pelangi kuat. Sehingga Jadi berdasarkan kasus 1 dan 2




56

Teorema3.18 Misalkan

adalah graf terhubung tak trivial, dengan ukuran m(G) maka .

Bukti: Sudah cukup jelas bahwa

pasti tidak pernah melampaui ukuran graf .

 Contoh 3.19 Misalkan

adalah graf Petersen dengan

. Menurut Contoh 3.9

maka menurut Teorema 3.17 dan Teorema3.18 diperoleh bahwa . Namun pewarnaan pelangi

pada Gambar3.1 bukan

merupakan pewarnaan pelangi kuat karena tidak menyebabkan pelangi maka

. Karena pewarnaan sisi

pewarnaan pelangi kuat sehingga

Oleh karena

terhubung merupakan dan

maka

Dari Teorema 3.8, Teorema 3.17 dan Teorema3.18 maka didapatkan sebuah pertidaksamaan (2)


57

Contoh 3.20 Akan dicari

dan

untuk graf . Perhatikan gambar berikut

T Gambar 3.5. Graf Penyelesaian:  Akan dicari Tabel 3.7. Jarak tiap dua titik dan eksentrisitas tiap titik pada T Nilai v

Titik 1 1

2

3

2

1

1

2

3

1

2

3

2

2

3

3

1

2

3

3

2

3

1

2

2

1

3

1

3

2

3

2

3

3

1

3

2

1

3

2

1

2

3

2

1

1

2

3

2

1

1

2

3

2

3

2

2

3

2

1

2

3

Berdasarkan Tabel 3.7 didapatkan diam tidaksamaan (2) diperoleh bahwa berarti terdapat pewarnaan pelangi

1

3

maka menurut per. Diasumsikan

di

,

dengan himpunan warna {1,


58

2, 3} di mana 1=warna merah, 2=warna biru, 3=warna hijau. Misalkan ,

.

Gambar 3.6. Graf T Dengan Pewarnaan Sisi Menurut Gambar 3.6 , tidak terdapat lintasan pelangi

, berarti

tidak terhubung pelangi, sehingga tidak terdapat pewarnaan pelangi , muncul kontradiksi. Jadi

maka

di

dengan kata lain

terdapat pewarnaan pelangi-4 dengan himpunan warna {1, 2, 3, 4}, seperti pada Gambar 3.7di mana 1=warna merah, 2=warna biru, 3=warna hijau dan 4=warna ungu.

Gambar 3.7. Graf T Dengan Pewarnaan Sisi


59

 Akan dicari Karena

maka menurut pertidaksamaan (2)

Diasumsikan pelangi

.Bilangan

seperti pada Gambar 3.7. Untuk setiap dua titik

akan dicari lintasan pelangi dengan panjang Tabel 3.8.Pelangi geodesik tiap dua titik diT Pelangi geodesik Titik

Tabel 3.9. Lanjutan Tabel 3.8 Pelangi geodesik Titik

berarti terdapat pewarnaan

.

dan

di


60

Karena untuk setiap dua titik

dan

terdapat lintasan pelangi kuat, maka

T terhubung pelangi kuat, sehingga pewarnaan pelangi pewarnaan pelangi kuat

. Jadi

juga merupakan

.

Teorema 3.21 Misalkan

dan

adalah graf terhubung tak trivial. Maka jika dan hanya jika

Bukti : Untuk

, akan dibuktikan

 Jika

, akan ditunjukkan

(2) dan karena

. Menurut pertidaksamaan

terhubung maka

lengkap. Karena . Graf

jika dan hanya jika

, sehingga

berarti terdapat pewarnaan pelangi

adalah graf lengkap maka setiap dua titik

dan

oleh sebuah sisi. Sehingga pewarnaan pelangi pewarnaan pelangi kuat  Jika

adalah graf

. Jadi

dihubungkan

juga merupakan

.

, akan ditunjukkan

(2) diperoleh bahwa

pada

. Menurut pertidaksamaan

. Karena

adalah graf terhubung maka

. Untuk  Jika

, akan dibuktikan , akan ditunjukkan

3.8 diperoeh bahwa diam bahwa

jika dan hanya jika

. Graf

. Maka menurut Teorema dan menurut Teorema 3.17 diperoleh

bukan graf lengkap maka diam

,


61

dengan kata lain jumlah maksimum sisi-sisi dari suatu geodesik adalah 2. Selanjunya karena pelangi

di

pelangi

. Karena diam

di , maka lintasan pelangi

maka pewarnaan pelangi

di

maka terdapat pewarnaan dan terdapat pewarnaan adalah pelangi geodesik

adalah pewarnaan pelangi kuat

. Jadi

.  Misalkan

adalah graf terhubung tak trivial dengan

Teorema 3.17diperoleh bahwa graf lengkap maka

. Karena

. Menurut bukan merupakan

.

 Contoh 3.22 Perhatikan gambar berikut,

(a) (b) Gambar3.8. (a) Graf , (b) Graf Karena

graf lengkap maka diam

diperoleh bahwa

Dengan Pewarnaan Sisi dan menurut Teorema 3.8

. Karena setiap dua titik

dan

di

dihubungkan oleh sebuah sisi sehingga minimal warna yang digunakan sedemikian sehingga terdapat lintasan pelangi untuk setiap dua titik

dan

di


62

adalah 1 warna, misalkan warna warna merah. Jadi

. Maka

menurut Teorema3.21


adalah graf terhubung tak trivial dengan ukuran

jika dan hanya jika

. Maka

adalah sebuah pohon.

Bukti  Misalkan

akan dibuktikan

pohon. Diasumsikan

adalah sebuah

adalah bukan sebuah pohon. Maka

memuat suatu

sirkuit

di mana

. Maka pewarnaan sisi

warna 1 untuk sisi

dan

yang memberikan

dan

himpinan warna

warna berbeda dari

untuk

sisi lainnya pada

adalah pewarnaan pelangi, dengan 1=warna merah, 2=warna biru, =warna kuning, warna hitam, seperti pada Gambar3.9.

=warna cokelat dan

=


63

Gambar3.9. Graf Jadi

Dengan Pewarnaan

. Kontradiksi dengan

. Sehingga

haruslah sebuah pohon.  Misalkan

adalah sebuah pohon dengan ukuran

. Akan dibuktikan

. Diasumsikan

bahwa

.

Oleh

karena

sehingga terdapat pewarnaan pelangi dari

. Maka terdapat sisi

dan

yang diwarnai dengan

warna yang sama. Misalkan diambil salah satu titik titik

atau

memuat sisi

yaitu titik dan

dan

atau

dan salah satu

sehingga terdapat lintasan

yang

diilustrasikan Gambar3.10.

Gambar3.10. Graf pohon Karena terdapat dua sisi pada lintasan lintasan

bukan lintasan pelangi

yang berwarna sama maka , sehingga terdapat lintasan


64

lain yang tidak memuat sisi pelangii

dan

yang merupakan lintasan

, hal tersebut menunjukkan bahwa terdapat sirkuit di

kontradiksi dengan

adalah pohon dengan ukuran

,

. Jadi

 Contoh 3.24 Gambar3.11 menyatakan suatu graf

Gambar3.11. Graf pohon Karena graf

merupakan pohon dengan

, jadi menurut

Teorema3.42 diperoleh bahwa

.


adalah graf siklus dengan banyak titik di mana

. Maka

. Bukti: Misalkan terdapat graf siklus dan

:

dan untuk setiap

dengan

. Untuk membuktikan pernyataan di atas, akan

dibagi menjadi 2 kasus tergantung nilai dari


65

Kasus 1: Untuk

genap. Misalkan

, untuk setiap bilangan bulat

sehingga

. Maka menurut pertidaksamaan (1), . Pewarnaan sisi

dari

didefinisikan sebagai berikut,

Diilustrasikan dalam Gambar3.12 dengan 1=warna merah, 2=warna biru, k=hijau, (k-1)=ungu.

Gambar3.12. Graf Untuk setiap dua titik

dan

terdapat pelangi geodesik

terlihat dalam Gambar3.11 maka sisi

seperti yang

terhubung pelangi kuat, maka pewarnaan

adalah suatu pewarnaan pelangi kuat– . Karena

pewarnaan pelangi kuat – (2)

Dengan Pewarnaan Sisi

maka

. Oleh karena

merupakan

dan menurut pertidaksamaan ,

jadi


66

Kasus 2: Untuk

ganjil. Misalkan

Didefinisikan pewarnaan sisi

Dengan

kata

, untuk bilangan bulat dari

sebagai berikut,

lain

,…,

, , sehingga untuk setiap dua titik

pelangi geodesik pelangi kuat

, maka pewarnaan pelangi

sehingga

(2)

terdapat

adalah pewarnaan pelangi

, maka menurut pertidaksamaan

. Karena diam atau

sehingga

, jadi

Akan dibuktikan bahwa

Asumsikan misalkan

dan

adalah suatu pewarnaan

. Karena pewarnaan pelangi

kuat

.

.

sehingga terdapat suatu pewarnaan pelangi dan tanpa mengurangi perumuman misalkan

Dipandang titik-titik

dan

adalah pelangi geodesik pelangi geodesik

.

. Misalkan lintasan dan lintasan

maka terdapat sisi di

Karena lintasan

,

: dan

adalah yang diberi warna .

juga merupakan geodesik

, sehingga

. Sebaliknya karena lintasan sehingga

adalah geodesik

,

. Diilustrasikan pada Gambar 3.13 dengan 1=warna

merah, 2=warna biru, 3=warna hijau, k=ungu, (k-1)=warna jingga.


67

Gambar 3.13. Graf


Ini berarti tidak terdapat lintasan pelangi pelangi

. Kontradiksi dengan

. Jadi

pewarnaan pelangi

. Oleh karena

bukan pewarnaan . Jadi

berdasarkan persamaan (2) di-

peroleh bahwa

, sehingga

.

Jadi

 Contoh 3.26 Diketahui graf siklus

, akan dicari nilai

dan

.

Penyelesaian: Menurut Teorema3.46 diperoleh bahwa Karena

berarti terdapat pewarnaan pelangi

. di

dengan himpunan

warna {1,2,3} di mana 1=warna merah, 2=warna biru, 3=warna hijau, seperti pada Gambar3.14.


68

Gambar3.14. Graf


Teorema 3.27 Bilangan keterhubungan pelangi dari graf roda

untuk

adalah

Bukti: Berdasarkan

definisi

,

dan satu titik

itu

berarti

terdapat

dengan

yang terhubung dengan setiap titik di

.

Akan dibagi menjadi 3 kasus: Kasus1: Untuk bahwa

, karena

, menurut pembuktian Teorema3.22 diperoleh

.

Kasus 2: Untuk

, karena graf

Didefinisikan pewarnaan sisi 2= warna biru sebagai berikut,

bukan graf lengkap sehingga

.

, dengan 1=warna merah,


69

dan

Seperti yang terlihat dalam Gambar3.15

(a) (b)

(c)

Gambar 3.15.(a) Graf Pewarnaan Sisi

Dengan Pewarnaan Sisi , (b) Graf , (c) Graf Dengan Pewarnaan Sisi

Oleh karena pewarnaan sisi diperoleh bahwa

merupakan pewarnaan pelangi

Dengan

, maka

.

Kasus 3: Untuk

,karena

wa

. Diasumsikan

pelangi

di

bukan

graf

lengkap

Misalkan dan sehingga

diperoleh

. Ini berarti terdapat pewarnaan

dengan himpunan warna {1, 2} di mana 1=warna merah dan

2=warna biru. Karena terdapat pewarnaan pelangi setiap dua titik

sehingga

dan

di

berarti untuk

terdapat lintasan pelangi


dari

. Diasumsikan

adalah satu-satunya lintasan pelangi untuk setiap

dengan

oleh Gambar3.16 dengan 1=warna merah, 2=warna merah.

dengan panjang

,

yang ditunjukkan


70

Gambar3.16. Graf Karena satu- satunya lintasan sehingga jika

yang memiliki panjang 2 adalah

maka

supaya terdapat lintasan pelangi

. Dengan cara yang sama didapatkan jika . Karena

maka

maka

Selanjutnya jika

. Sehingga karena

maka tidak terdapat lintasan pelangi dengan terdapat pewarnaan pelangi Didefinisikan pewarnaan sisi

maka

pada

Jadi

dengan

dan . Ini kontradiksi . pada

sebagai

berikut

dan

untuk setiap

yang ditunjukan oleh Gambar3.17

dengan 1=warna merah, 2=warna biru, 3=warna hijau.


71

Gambar3.17. Graf Karena setiap dua titik pewarnaan sisi

dan

Dengan Pewarnaan Sisi terdapat lintasan pelangi


Oleh karena

, jadi

untuk

sehingga

sehingga diperoleh .

 Contoh 3.28 Diberikan sebuah graf

, akan dicari nilai dari

Teorema3.46 diperoleh bahwa pelangi

di

. Menurut

, sehingga terdapat pewarnaan

dengan himpunan warna {1,2},di mana 1=warna merah,

2=warna biru, 3=warna hijau.


72

Gambar3.18. Graf

Dengan Pewarnaan Pelangi

Teorema3.29 Bilangan keterhubungan pelangi pada graf roda

untuk

adalah

Bukti: Misalkan

terdiri dari graf

terhubung dengan setiap titik di Kasus 1: Untuk

dan satu titik . Akan dibagi menjadi 3 kasus

, graf

bahwa

yang

dan menurut Teorema 3.27diperoleh maka berdasarkan Teorema 3.21diperoleh bahwa

. Kasus 2: Untuk

,menurut Teorema 3.27 diperoleh bahwa

maka berdasarkan Teorema 3.21. diperoleh bahwa untuk

.


73

Kasus 3: Untuk

, akan dibuktikan

terdapat suatu bilangan bulat

. Misalkan sehingga

maka

. Selanjutnya

akan ditunjukkan Pertama-tama akan ditunjukkan

. Diasumsikan

maka terdapat pewarnaan pelangi kuat

pada

maka dapat dibentuk himpunan dan semua sisi

dengan

terdapat dua titik

sedemikian sehingga

memiliki warna yang sama. Maka

sehingga jumlah sisi pada geodesik

lebih dari sam dengan 3 atau di

sama dengan 2 atau

pelangi geodesik

di

di

, akibatnya tidak terdapat

. Ini berarti tidak terdapat pewarnaan pelangi

Selanjutnya, akan ditunjukkan pada

Karena setiap dua titik pewarnaan sisi bahwa

. Karena

,kontradiksi dengan

sisi

. Jadi

.

Didefinisikan suatu pewarnaan sebagai berikut

terdapat pelangi geodesik

di

adalah pewarnaan pelangi kuat . Jadi

di

dan jumlah sisi pada geodesik

merupakan satu-satunya geodesik

kuat

. Karena

untuk

sehingga

. Maka diperoleh .




74

Contoh 3.30 Diberikan graf sebuah graf

, akan dicari nilai

Teorema3.29 terdapat pewarnaan pelangi kuat

dari pada

. Menurut

, dengan kata lain

3 dengan himpunan warna {1, 2, 3} di mana 1= warna merah, 2= warna biru, 3= warna hijau, seperti pada gambar dibawah ini.

Gambar3.19. Graf


Teorema 3.31 Bilangan keterhubungan pelangi kuat dari graf bipartit bilangan bulat dan

dengan

untuk suatu

adalah

Bukti: Untuk

himpunan titik-titik pada

himpunan, misalkan dihubungkan ke setiap titik di lintasan

dan sehingga

dan juga merupakan geodesik

dapat dipartisi menjadi dua , karena

di

merupakan satu-satunya dengan

dan

, sehingga jumlah warna yang digunakan sedemikian sehingga


75

terdapat pewarnaan pelangi kuat di

adalah seperti yang ditunjukkan pada

Gambar3.20. Jadi benar bahwa

Gambar3.20. Graf

.

Dengan Pewaranaan Pelangi Kuat

Selanjutnya diasumsikan untuk

Sehingga

terdapat pewarnaan

. . Asumsikan

. Himpunan

dapat dipartisi menjadi dua himpunan, misalkan dan dan

berturut- turut

didefinisikan suatu kode warna dari

. Maka

yaitu pewarnaan pelangi kuat

, dengan kardinalitas

, maka

maka

Akan ditunjukkan bahwa

titik-titik

,

, di mana

Gambar3.21. Graf

dan , sehingga

dan . Untuk setiap titik yang disebut kode

untuk

seperti pada Gambar3.21.



76

Karena terdapat pewarnaan pelangi kuat setiap

sehingga

untuk

, maka banyaknya warna berbeda pada kode warna dari titik-

titik di

paling banyak

. Tetapi karena karena

terdapat dua titik berbeda yaitu kode

. Lintasan

dan

dan

di

maka

sehingga kode

berturut- turut merupakan satu- satunya

geodesik

dan geodesik

dan karena

setiap

sehingga tidak terdapat pelangi geodesik

Sehingga tidak terdapat pewarnaan pelangi kuat kontradiksi dengan

di

Jadi

Selanjutnya, akan ditunjukkan

kali dan himpunan

di

.

. Hal tersebut .

. Misalkan

. Himpunan sebanyak

untuk

dan

adalah hasil kali kartesian

adalah hasil kartesian

dan

dan

sebanyak

kali. Sehingga

s kali sehingga,

dan

adalah himpunan hasil kali seluruh elemen dalam setiap pasangan

terurut di

. Selanjutnya

s kali

sehingga,


77

dan

adalah himpunan hasil kali seluruh elemen dalam setiap pasangan

terurut di

.Jadi

.

Misalkan

titik- titik di

anggota dari

sedemikian sehingga

anggota dari dari

dilabeli dengan dilabeli dengan

. Untuk setiap

dengan

didefinisikan label

dengan

untuk setiap

yang diilustrasikan dengan Gambar3.22.

Gambar3.22. Graf sehingga

untuk

. Didefinisikan pewarnaan

dengan

untuk

. Sehingga kode warna dari , maka titik-titik berbeda di Selanjutnya akan ditunjukkan bahwa . Untuk

dan

dan

adalah kode memiliki kode warna berbeda.

adalah pewarnaan pelangi kuat merupakan satu-satunya


78

geodesik

dan karena kode warna berbeda untuk setiap titik- titik

berbeda di

maka geodesik

Diambil sebarang dua titik

dan

adalah pelangi geodesik di

. Karena titik-titik tersebut

memiliki kode warna berbeda sehingga di titik

untuk suatu dengan dan

di

adalah pelangi geodesik . Selanjutnya diambil sebarang dua

sedemikian sehingga

merupakan satu-satunya geodesik dengan adalah pelangi geodesik

. Lintasan dan karena terdapat suatu

sehingga

adalah pewarnaan pelangi kuat

.

, maka geodesik

. Oleh karena itu terbukti bahwa dari

. Jadi

.

 Contoh 3.32 Diberikan graf bipartit

, akan dicari nilai dari

3.31 bahwa pewarnaan pelangi kuat

Menurut Teorema

, dengan kata lain terdapat di

, dengan himpunan warna {1, 2} di mana

1=warna merah, 2=warna biruseperti yang ditunjukkan Gambar3.23.


79

Gambar3.23. Graf


Toerema 3.33 Bilangan keterhubungan pelangi dari graf dengan

untuk suatu bilangan bulat

dan

adalah

Bukti: Diketahui bahwa

sehingga

Misalkan himpunan titik- titik di ,

di

kasus:

dipartisi menjadi himpunan

mana

sehingga kardinalitas

maka

dan dan

berturut- turut

. dan ,

dan . Akan dibagi menjadi 3


80

Kasus 1: Jika

maka

. Menurut Teorema 3.31 diperoleh bahwa

dan pertidaksamaan

karena

(2)

diam

diperoleh

maka

menurut

bahwa

.

Jadi

. Kasus 2: Jika

maka

bahwa

. Menurut Teorema 3.31 diperoleh dan karena diam

pertidaksamaan

(2)

diperoleh

atau

maka menurut

bahwa

.

. Akan dibuktikan

Asumsikan

untuk

maka terdapat dua titik berbeda sehingga kode

dan

sedemikian

jadi tidak terdapat pewarnaaan pelangi . Jadi

maka

Asumsikan

untuk setiap

. Karena

sehingga tidak terdapat lintasan pelangi

Hal ini kontradiksi dengan

di

di

. Ini berarti

untuk setiap

pelangi

di

untuk setiap

dengan

Kasus 3: Jika

.

maka terdapat pewarnaan pelangi

. Sehingga terdapat kode

di

Jadi

di

.

.

. Akan ditunjukkan ini

berarti

terdapat

pewarnaan

. Sehingga terdapat kode di

. Karena

dengan

untuk

maka terdapat dua titik berbeda

sedemikian sehingga kode

dan

. Karena jumlah


81

sisi pada lintasan

genap, maka lintasan pelangi

yang terdapat di

adalah lintasan pelangi

yang

memiliki panjang 2. Namun setiap sisi pada lintasan pelangi tersebut berwarna sama sehingga tidak terdapat lintasan pelangi

di

pelangi

pada

. Sehingga tidak terdapat pewarnaan . Ini kontradiksi dengan

Selanjutnya akan dibuktikan

Untuk membuktikan

akan ditunjukan terdapat pewarnaan pelangi Misalkan Himpunan

. Jadi

di

,

.

,

dan

adalah hasil kali kartesius dari himpunan

.

sebanyak . Dengan

kata lain

Untuk setiap titik

di

didefinisikan,

kode untuk lain

,

dan

dengan

,

, …., ,

Sedangkan untuk setiap titik

di

kode untuk

dan

.

didefinisikan,

.Dengan kata dan seterusnya.


82

Selanjutnya diambil sebarang dua titik pewarnaan pelangi

pada

Kasus 1: Untuk

dengan membagi menjadi 3 kasus:

. Karena kode yang

maka terdapat dengan

. Karena

. Misalkan

. Sehingga lintasan sisi-sisinya berwarna

dan

dan

.

dengan

merupakan lintasan pelangi yang Jadi terdapat pewarnaan pelangi

. Ambil sebarang dan

di

dengan

maka

Kasus3: Untuk

adalah

. Jadi terdapat pewarnaan pelangi

dan

c

kode

). Maka lintasan

lintasan pelangi Kasus 2: Untuk

akan dibuktikan terdapat

di

sedemikian sehingga

maka lintasan

adalah lintasan

pelangi yang sisi-sisinya berwarna , 1, 2 dan 3. Misalkan

dengan

Sehingga terdapat suatu titik lintasan pelangi

adalah lintasan pelangi di

dan

di mana

yang mana di

. . Jadi

, maka terdapat pewarnaan

. Jadi

 Contoh 3.34 Diberikan graf bipartit 3.33

diperoleh

, akan dicari nilai dari bahwa

Menurut Teorema


83

, dengan kata lain terdapat pewarnaan pelangi

di

seperti

yang ditunjukkan Gambar3.24.

Gambar3.24

C. Aplikasi Pada subbab ini akan dijelaskan aplikasi bilangan keterhubungan pelangi kuat pada graf dalam kehidupan sehari-hari. Contoh 3.35 Salah satu penerapan bilangan keterhubungan pelangi kuat

pada graf

adalah pendistribusian soal-soal ujian nasional. Contoh ini diambil daripidato pengukuhan guru besar berjudul Teori Graf, Aplikasi dan Tumbuhnya Keterampilan Berfikir Tingkat Tinggi, yang ditulis oleh Prof. Drs. Dafik,


84

M.Sc, Ph.D. Diknas akan mendistribusikan soal-soal ujian nasional ke seluruh sekolah di kabupaten Jember (pelaksanaan UN SMA 2014). Soal ini bersifat rahasia sehingga membutuhkan tim pengawas pendistribusian soal UN yang terdiri dari unsur Universitas Negeri Jember (UNEJ), Lembaga Penjaminan Mutu Pendidikan (LPMP), Polisi resort (Polres), Pendidikan Nasional (Diknas), dan pihak sekolah. Misal jalur untuk menjangkau sekolah-sekolah direpresentasikan pada graf Rdi manaj merupakan pusat penyimpanan soal dan titik awal pendistribusian soal, sedangkan titik a, b, c, d, e, f, g, h, i, k, l, m, n, o, p mewakili sekolah-sekolah di kabupaten Jember . Permasalahan yang muncul adalah:Bagaimana caramenentukan jumlah kelompok pengawalan pendistribusian soal UN?

Gambar3.25. Graf R

Solusi:

Gambar 3.26. Graf S


85

Diberikan graf S seperti pada gambar di atasdan didefinisikanfungsi dengan , ,

, ,

,

fungsi bijektif dari

, ,

dan ke

,

,

,

,

,

. Dapat ditunjukkan bahwa f adalah seperti pada berikut.

Gambar 3.27. Fungsi Bijektif Dari V(R) Ke V(S) Kemudian dapat ditunjukkan untuk setiap dua titik u dan v di R, u dan v bertetangga jika dan hanya jika f (u)dan f (v) bertetangga di S, yang dijelaskan pada tabel di bawah ini. Jadi graf


86

Tabel 3.10. Dua titik u dan v yang bertetangga di R dan dua titik f(u)dan f(v) yang bertetangga di S Pada graf R Titik a bertetangga dengan b Titik a bertetangga dengan j Titik a bertetangga dengan k Titik a bertetangga dengan e Titik b bertetangga dengan c Titik b bertetangga dengan l Titik b bertetangga dengan f Titik b bertetangga dengan m Titik c bertetangga dengan d Titik c bertetangga dengan n Titik c bertetangga dengan g Titik c bertetangga dengan o Titik d bertetangga dengan i Titik d bertetangga dengan p Titik d bertetangga dengan h Titik e bertetangga dengan j Titik e bertetangga dengan k Titik e bertetangga dengan f Titik f bertetangga dengan l Titik f bertetangga dengan m Titik f bertetangga dengan g Titik g bertetangga dengan n Titik g bertetangga dengan o Titik g bertetangga dengan h Titik h bertetangga dengan p Titik h bertetangga dengan i Titik k bertetangga dengan l Titik m bertetangga dengan n Titik o bertetangga dengan p

Titik

Titik f(a) = Titik f(a) = Titik f(a) = Titik f(a) = Titik f(b) = Titik f(b) = Titik f(b) = Titik f(b) = Titik f(c) = Titik f(c) = Titik f(c) = Titik f(c) = Titik f(c) = Titik f(c) = Titik f(c) = Titik f(e) = Titik f(e) = Titik f(e) = Titik f(f) = Titik f(f) = Titik f(f) = Titik f(g) = Titik f(g) = Titik f(g) = Titik f(h) = Titik f(h) = Titik f(k) = Titik f(m) = Titik f(o) =

Para graf S bertetangga dengan f(b) = bertetangga dengan f(j) = bertetangga dengan f(k) = bertetangga dengan f(e) = bertetangga dengan f(c) = bertetangga dengan f(l) = bertetangga dengan f(f) = bertetangga dengan f(m) = bertetangga dengan f(d) = bertetangga dengan f(n) = bertetangga dengan f(g) = bertetangga dengan f(o) = bertetangga dengan f(i) = bertetangga dengan f(p) = bertetangga dengan f(h) = bertetangga dengan f(j) = bertetangga dengan f(k) = bertetangga dengan f(f) = bertetangga dengan f(l) = bertetangga dengan f(m) = bertetangga dengan f(g) = bertetangga dengan f(n) = bertetangga dengan f(o) = bertetangga dengan f(h) = bertetangga dengan f(p) = bertetangga dengan f(i) = bertetangga dengan f(l) = bertetangga dengan f(n) = bertetangga dengan f(p) =

merepresentasikan titik j pada graf R, sedangkan merepresentasikan sekolah–sekolah pada kabupa-

ten Jember dan sisi-sisi di graf S merepresentasikan jalur pendistribusian dari satu sekolah ke sekolah lainnya. Permasalahan ini dapat diselesaikan


87

menggunakan konsep bilangan terhubung pelangi dan bilangan terhubung pelangi kuat, sebab apabila menggunakan konsep tersebut akan didapatkan minimumjumlah kelompok pengawalan pendistribusian soal UN. Oleh karena graf S tidak termasuk kedalam graf khusus yang dijelaskan pada bab sebelumnya, sehingga untuk menentukan

dan

menggunakan

pertidaksamaan berikut. . Bilangan

dan

menyatakan minimal jumlah kelompok pengawalan

dan warna tiap sisi pada pewarnaan pelangi kuat menunjukkan kelompoknya. Pertama-tama akan dicari

. Untuk menentukan

maka terlebih

dahulu dicari jarak tiap dua titik dan eksentrisitas dari setiap titi di S,seperti yang dijelaskan pada tabel berikut. Tabel 3.11. Jarak setiap dua titik di Nilai Titik 2 2 3 3 4 4 5 5 1 2 3 4 1 2 3 4

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

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

3 3 2 1 3 4 4 2 1 2 3 2 1 2 3

4 4 3 1 2 3 3 3 2 1 2 3 2 1 2

4 4 3 3 2 1 3 3 2 1 2 3 2 1 2

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

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


88

Tabel 3.12. Lanjutan dari Tabel 3.11 dan eksentrisitas tiap titik di Nilai Titik 1 1 2 2 3 3 4 4 1 2 3 1 2 3 4

2 2 1 1 2 2 3 3 1 1 2 2 1 2 3

3 3 2 2 1 1 2 2 2 1 1 3 2 1 2

4 4 3 3 2 2 1 1 3 2 1 4 3 2 1

1 1 2 2 3 3 4 4 1 2 3 4 1 2 3

2 2 1 1 2 2 3 3 2 1 2 3 1 1 2

3 3 2 2 1 1 2 2 3 2 1 2 2 1 1

Menurut Definisi 2.65 diperoleh bahwadiam pertidaksamaan (2) diperoleh bahwa asumsikan

4 4 3 3 2 2 1 1 4 3 2 1 3 2 1

5 5 5 4 4 4 5 5 4 3 3 4 4 3 3 4

, sehingga menurut

. Akan dibuktikan

, berarti terdapat pewarnaan pelangi

,

di S, dengan

himpunan warna {1, 2, 3, 4, 5} di mana 1=warna merah, 2=warna biru, 3=warna hijau, 4=warna jingga, 5=warna ungu, seperti yang ditunjukkan pada Gambar3.28.

Gambar3.28. Graf S Dengan PewarnaanPelangi


89

Akan ditunjukkan bahwa terdapat pewarnaan pelangi-5 pada graf. Perhatikan tabel-tabeldi bawah ini. Tabel 3.13. Lintasan pelangi setiap dua titik di Lintasan pelangi Titik

Tabel 3.14. Lanjutan dari Tabel 3.13 Lintasan pelangi titik


90

Tabel 3.15. Lanjutan dari Tabel 3.14 Lintasan pelangi Titik

Tabel 3.16. Lanjutan dari Tabel 3.15 Lintasan pelangi Titik


91

Tabel- tabel di atas menunjukkan bahwa untuk setiap dua titik terdapat lintasan pelangi dengan kata lain

di S. Jadi terdapat pewarnaan pelangi

panjang

di

maka menurut pertidaksamaan (2) diperoleh

. Akan dibuktikan

. Asumsikan bahwa

Tabel 3.13-Tabel 3.16 juga menunjukkan bahwa lintasan pelangi setiap dua titik

di S

.

Oleh karena bahwa

dan

dan

di S juga merupakan pelangi geodesik

. untuk dengan

, sehingga pewarnaan pelangi-5 juga merupakan pewarnaan

pelangi kuat-5. Jadi maka

. .Apabila

Oleh dihubungkan

karena dengan

graf

R S

permasalahan

pendistribusian soal UN dapat disimpulkan bahwa jumlah minimal kelompok pengawalan pendistribusian soal UN ke seluruh sekolah di kabupaten Jember adalah 5 kelompok danwarna-warna pada pewarnaan pelangi-5 menyatakan kelompok pengawalan, di mana warna 1=kelompok 1, warna 2=kelompok 2, warna 3=kelompok 3, warna 4=kelompok 4 dan warna 5=kelompok 5, seperti pada Gambar 3.29.


92

Gambar3.29. Jalur Pendistribusian Soal UNKeSekolah-Sekolah

Contoh 3.36 Komisi pemilihan umum (KPU) merilis tahapan Pemilihan Kepala Daerah (PILKADA) serentak pada tahun 2017. PILKADA gelombang kedua serentak dilakukan pada tahun 15 Februari 2017. Salah satu Kota yang melakukan PILKADA adalah Kota Bekasi. KPU Kota Bekasi menargetkan akan selesai mendistribusikan kertas suara selesai sehari sebelum PILKADA. Pada Kota Bekasi kertas suara akan didistribusikan pada 12 kecamatan. Kertas suara ini bersifat rahasia sehingga membutuhkan tim pengawalan pendistribusan yang terdiri dari unsur Polres, Satpol PP, Camat, Panitia Pengawas Pemilu (PANWASLU), KPU Bekasi. Misal jalur untuk menjangkau kecamatankecamatan direpresentasikan pada graf Xdi manaP merupakan pusat penyimpanan kertas suara dan titik awal pendistribusian kertas suara, sedangkan titik A, B, C, D, E, F, G, H, I, K mewakili kecamatan-kecamatan di Kota Bekasi . Permasalahan yang muncul adalah adalah: Bagaimana cara menentukkan banyaknya kelompok pengawalan pendistribusian kertas suara?


93

Gambar 3.30. Graf X

Penyelesaian:

Gambar 3.31. Graf Diberikan graf

seperti pada gambar di atasdan didefinisikanfungsi

dengan ,

,

, ,

,

, ,

Dapat ditunjukkan bahwa f adalah fungsi bijektif dari pada Gambar 3.32.

, dan ke

, . seperti


94

Gambar 3.32.Fungsi Bijektif Dari Himpunan V(X) Ke V(

)

Kemudian dapat ditunjukkan untuk setiap dua titik u dan v di X, u dan v bertetangga jika dan hanya jika f(u)dan f(v) bertetangga di dijelaskan pada tabel di bawah ini. Jadi graf

, yang

.

Tabel 3.10. Dua titik u dan v yang bertetangga di X dan dua titik f(u)dan f(v) yang bertetangga di Pada graf X Titik A bertetangga dengan B Titik B bertetangga dengan C Titik C bertetangga dengan D Titik D bertetangga dengan D Titik E bertetangga dengan F Titik F bertetangga dengan G

Titik f(A) = Titik f(B) = Titik f(C) = Titik f(D) = Titik f(E) = Titik f(F) =

Titik G bertetangga dengan H Titik H bertetangga dengan I Titik I bertetangga dengan J Titik J bertetangga dengan K Titik K bertetangga dengan L

Titik f(G) = bertetangga dengan f(H) = Titik f(H) = bertetangga dengan f(I) = Titik f(I) = bertetangga dengan f(J) = Titik f(J) = bertetangga dengan f(K) = Titik f(K) = bertetangga dengan f(L) =

Para graf bertetangga dengan f(B) = bertetangga dengan f(C) = bertetangga dengan f(D) = bertetangga dengan f(E) = bertetangga dengan f(F) = bertetangga dengan f(G) =


95

Titik

vdi

merepresentasikan

titik

P

diX,

sedangkan

titik

merepresentasikan kecamatan di Kota Bekasi dan sisi-sisi di graf Y merepresentasikan jalur pendistribusian dari satu kecamatan ke kecamatan lain.Permasalahan pendistribusian kertas suara PILKADA dapat diselesaikan menggunakan konsep bilangan terhubung pelangi dan bilangan terhubung pelangi kuat, sebab apabila menggunakan konsep tersebut akan didapatkan minimum jumlah kelompok pengawalan pendistribusian kertas suara.Pada permasalahan ini bilangan rc(X) dan src(X) menyatakan minimum jumlah kelompok pengawalan pendistribusian kertas suara. Selanjutnya akan dicari rc(X) dan src(X), karenaX Y sehingga rc(X)=rc( rc(

) dan src(X)=src(

). Menurut Teorema 3.27 diperoleh bahwa

)=3, sehingga terdapat pewarnaan pelangi

pada

, dengan

himpunan warna {1, 2, 3},di mana 1= warna merah, 2=warna biru, 3=warna hijau, seperti pada Gambar 3.33.

Gambar 3.33. Graf

Dengan Pewarnaan Pelangi


96

Sedangkan menurut Teorema 3.29 diperoleh bahwa sehingga terdapat pewarnaan pelangi kuat

pada

, dengan himpunan

warna {1, 2, 3, 4} di mana 1=warna merah, 2=warna biru, 3=warna hijau dan 4=warna unguseperti pada Gambar 3.34.

Gambar 3.34. Graf

Dengan Pewarnaan Pelangi Kuat

Berdasarkan perhitungan sebelumnya didapatkan rc(X)=3 dan src(X)=4. Pada permasalahan pendistribusian kertas suara rc(X)=3 menyatakan bahwa minimum jumlah kelompok pengawal pendistribusian kertas suara adalah 3 kelompok. Sedangkan src(X)=4 menyatakan bahwa minimum jumlah kelompok pengawal pendistribusian kertas suara adalah 4 kelompok. Jadi untuk menyelesaikan persoalan pendistribusian kertas suara akan lebih baik menggunakan bilangan terhubung pelangi kuat karena akan lebih cepat mendistribusikan surat menggunakan minimal 4 kelompok pengawalan dibanding 3 kelompok pengawalan.Selanjutnya warna-warna pada pewarnaan pelangi-4 menunjukkan kelompok pengawalan pendistribusian kertas suara di mana warna 1=kelompok 1,


97

warna 2=kelompok 2, warna 3=kelompok 3 dan warna 4=kelompok 4, seperti pada gambar berikut.

Gambar 3.35. Jalur Pendistribusian Kertas Suara Dilengkapi Kelompok Pengawalan Pendistribusian


BAB IV PENUTUP

Pada bab ini dituliskan kesimpulan dari pembahasan bab-bab sebelumnya, serta saran bagi penelitian selanjutnya.

A. Kesimpulan Misalkan G adalah graf terhubung tak trivial.Bilangan keterhubungan pelangi kuat pada grafGmerupakan bilangan bulat positif terkecil sedemikian sehingga terdapat pewarnaan pelangi kuat Untuk graf terhubung tak trivial

padaG.

dalam skripsi ini telah dibuktikan

beberapateorema: Untuk menunjukkan hubungan antara diameter graf, bilangan keterhubungan pelangi, bilangan keterhubungan pelangi kuat dan ukuran graf, yaitu . Untuk menentukan

apabila diketahui

,

yaitu jika dan hanya jika

.

Sedangkan untuk graf- graf khusus yang digunakan dalam skripsi ini telah dibuktikan beberapa teorema untuk menentukan bilangan keterhubungan pelangi kuat antara lain:

98

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 99

Untuk graf pohon: Misalkan dengan ukuran

adalah graf terhubung tak trivial

, maka

jika dan hanya jika adalah sebuah pohon. Untuk graf siklus: Misalkan di mana

adalah graf siklus dengan banyak titik

, maka .

Untuk graf roda, bilangan keterhubungan pelangi pada graf roda untuk

adalah .

Untuk graf bipartit,bilangan keterhubungan pelangi kuat dari graf bipartit

untuk suatu bilangan bulat s dant dengan

adalah

. Dalam kehidupan sehari-hari salah satu penerapan bilangan keterhubungan pelangi kuat yang dibahas dalam skripsi ini yaitu pada pendistribusian barang yang bersifat rahasia sehingga membutuhkan kelompok pengawalan keamanaan, seperti soal UN dan kertas suara PILKADA. Pada pendistribusian barangbilangan keterhubungan pelangi kuat berguna dalam menentukan jumlah kelompok pengawalan.

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 100

B. Saran Bilangan keterhubungan pelangi kuat yang dibahas dalam skrpsi ini merupakan bilangan keterhubungan pelangi kuat untuk graf dengan ukuran kecil dan tidak semua bilangan pelangi tehubung kuat pada graf dibahas dalam skripsi ini,sehingga masih terbuka untuk diteliti lebih lanjut khususnya untuk graf dengan ukuran besar. Selain itu sampai saat skripsi ini selesai ditulis, belum ada literatur tentang algoritma untuk memudahkan mencari bilangan keterhubungan pelangi suatu graf, sedangkan secara umum cukup sulit untuk menentukan bilangan keterhubungan kuat terutama bila grafnya berukuran besar, sehingaa masih terbuka kesempatan meneliti algoritma untuk mencari bilangan keterhubungan pelangi kuat khususnya untuk graf dengan ukuran besar.


DAFTAR PUSTAKA

Buckley, F. and Lewinter, M. (2003). A Friendly Introduction To Graph Theory.New Jersey: Pearson Education Inc.

Chartrand, G. and Zhang, P. (2009). Chromatic Graph Theory. New York: CRC Press Company.

Chartrand, G.,Johns, G. L., McKeon, K.A. and Zhang, P. (2008).Rainbow Connection in graphs.Math.Bohemica, 133(2): 85-98.

Dafik. (2015). Teori Graf, Aplikasi dan Tumbuhnya Keterampilan Berfikir Tingkat Tinggi. Pidato Pengukuhan Guru Besar. Universitas Jember.

Epp, S.S. (2010). Discrete Mathematics with Applications.Fourth Edition. Boston: Brooks/Cole Cengage Learning.

Jek, J.S. (2002). Matematika Diskrit dan Aplikasinya pada Ilmu Komputer.Edisi Kedua. Yogyakarta: Andi Offset.

Johnsonbaugh,R. (1997).Discrete Mathematics. New Jersey: Prentice Hall Inc.

Susilo, F. (2012). Landasan Matematika. Yogyakarta: Graha Ilmu.

101

BILANGAN KETERHUBUNGAN PELANGI KUAT PADA GRAF SKRIPSI

Recommend Documents