PENERAPAN RAINBOW CONNECTION PADA GRAF-GRAF HASIL OPERASI

Abstract

Salah satu teori yang dikembangkan dalam teori graf adalah Rainbow Connection. Rainbow Connection adalah pemberian warna pada sisi graf dengan syarat dua sisi yang bertetangga boleh diberi warna yang sama. Namun sisi yang masuk dalam rainbow path tidak boleh ada dua sisi atau lebih yang memiliki warna sama. Pewarnaan di sini disebut Rainbow Coloring, dan pewarnaan minimal dalam suatu graf G disebut Rainbow Connection Number yang dilambangkan dengan rc(G). Untuk pemberian Rainbow Coloring harus menggambarkan pola fungsi agar mudah dalam mencari fungsi dari pewarnaannya. Rainbow Connection dapat diterapkan pada graf yang merupakan hasil operasi dari beberapa graf khusus, misalnya seperti hasil operasi dari graf lintasan (path), graf lingkaran (cycle), graf bintang (star) dan graf roda (wheel). Sedangkan operasi graf adalah beberapa cara untuk memperoleh graf baru dengan melakukan suatu operasi terhadap dua graf. Adapun graf-graf hasil operasi yang digunakan dalam penelitian ini yaitu (Pn+Cn, Cn+Sn, Pn+Wn, Cn+Wn, Sn+Wn, Pn Wm, Pn⊗Cn, Pn[Cm], Pn[Wm], Pn[Sm], Amal(Cn, r) P2, Amal(Pn, r) P2 dan Amal(Wn, r) P2). Pada penelitian ini menggunakan metode penelitian eksploratif dan terapan. Tujuan dari penelitian ini adalah untuk menentukan kardinalitas titik dan sisi, rainbow connection number, dan fungsi rainbow coloring pada graf (Pn+Cn, Cn+ Sn, Pn + Wn, Cn + Wn, Sn + Wn, Pn Wm, Pn ⊗ Cn, Pn[Cm], Pn[Wm], Pn[Sm], Amal(Cn, r) P2, Amal(Pn, r) P2 dan Amal(Wn, r) P2).