ANALISIS RAINBOW VERTEX CONNECTION PADA BEBERAPA GRAF KHUSUS DAN OPERASINYA

Abstract

Salah satu teori yang dikembangkan dalam teori graf adalah rainbow connection. Teori rainbow connection dikembangkan menjadi 2 jenis yaitu rain- bow edge connection yang biasa disebut rainbow connection dan rainbow vertex connection. Rainbow connection adalah pemberian warna pada sisi suatu graf G jika setiap titik pada graf G dihubungkan oleh lintasan yang memiliki sisi-sisi yang berbeda. 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. Sedangkan rainbow vertex connection adalah pemberian warna titik pada graf G jika setiap titik pada graf G dihubungkan oleh lintasan memiliki titik-titik interior dengan warna yang berbeda. Namun titik yang masuk dalam rainbow vertex path tidak boleh ada dua titik atau lebih yang memiliki warna sama. Pe- warnaan di sini disebut rainbow vertex coloring, dan pewarnaan minimal dalam suatu graf G disebut rainbow vetex connection number yang dilambangkan dengan rvc(G). Untuk pemberian rainbow vertex coloring harus menggambarkan pola fungsi agar mudah dalam mencari fungsi dari pewarnaannya. Berdasarkan penelitian rainbow vertex connection yang diterapkan pada hasil operasi dari beberapa graf khusus ini, seperti hasil operasi dari graf lin- tasan (path graph), graf bintang (star graph), graf kincir angin (windmill graph), graf kipas (fan graph), graf siklus (cycle graph), dan graf buku segitiga (trian- gular book graph). Operasi graf merupakan operasi terhadap dua buah graf atau lebih sehingga menghasilkan graf baru. Adapun graf-graf hasil operasi yang digunakan dalam penelitian ini yaitu amal(F1;m, v, n), amal(Btm, v, m), F1;m¤Pn, Wd3;m¤Pn, Pm ¯ F1;n, Pm ¯ Wd3;n, Wd3;m ¯ Cn, Pm + F1;n, F1;m + Cn, Wd3;m + Cn, shack(F1;m, v, n), shack(Btn, v, m), dan shack((Sm + Cn), v, r). Berikut hasil penelitian rainbow vertex connection pada beberapa graf khusus dan operasinnya.