ANALISA RAINBOW CONNECTION DAN STRONG RAINBOW CONNECTION PADA GRAF HASIL OPERASI

Abstract

Salah satu teori yang dikembangkan dalam teori graf adalah rainbow connection dan strong 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. Graf G dikatakan strongly rainbow connected jika untuk setiap dua titik u dan v di G, terdapat suatu rainbow u-v geodesic. Dimana rainbow u-v geodesic pada G adalah rainbow u-v path yang panjangnya d(u; v), dimana d(u; v) adalah jarak antara u dan v (panjang u ¡ v path terpendek di G). Pewarnaan di sini disebut strong rainbow coloring, dan pewarnaan minimal dalam suatu graf G disebut strong rainbow connection number yang dilambangkan dengan src(G). Untuk pemberian strong rainbow coloring harus menggambarkan pola fungsi agar mudah dalam mencari fungsi dari pewarnaannya. Rainbow connection dapat diterapkan pada graf hasil operasi dari beberapa graf khusus, seperti hasil operasi dari graf lintasan, graf lingkaran, graf roda, graf lengkap dan graf kipas. 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 F2;6¤Pm, Amal(F1;3; v = 1; 2)¤Pm, Amal(W4; v = 1; 2)¤Pm, P2[F2;n], P2[Amal (F1;n; v = 1; 2)], P2[Amal(Wn; v = 1; 2)], Amal(F1;n; v = 1; 2) + Amal(Wn; v = 1; 2), gshack(Kn; P2; r), gshack(Kn; C3; r), gshack(Amal((K1 + Kn); v = 1; 2); Kn; r), gshack(W6;C3; r) dan gshack (W6;C1 4 ; r). Pada penelitian ini menggunakan metode penelitian eksploratif dan terapan. Tujuan dari penelitian ini adalah untuk menentukan kardinalitas titik dan sisi, rainbow connection number, strong rainbow connection number, fungsi rainbow coloring dan strong rainbow coloring pada graf F2;6¤Pm, Amal(F1;3; v = 1; 2)¤Pm, Amal(W4; v = 1; 2)¤Pm, P2[F2;n], P2[Amal (F1;n; v = 1; 2)], P2[Amal (Wn; v = 1; 2)], Amal(F1;n; v = 1; 2) + Amal(Wn; v = 1; 2), gshack(Kn; P2; r), gshack(Kn; C3; r), gshack(Amal((K1 + Kn); v = 1; 2); Kn; r), gshack(W6;C3; r) dan gshack (W6;C1 4 ; r). Pada penelitian ini dihasilkan 3 akibat dan 12 teorema baru, antara lain: 1. Akibat 4.1.1 Misal G adalah cartesian product dari graf kipas F2;6 dan graf lintasan Pm. Untuk m ¸ 2, rainbow connection number dari graf G = F2;6¤Pm adalah m + 1; 2. Teorema 4.1.1 Misal G adalah cartesian product dari graf kipas F2;6 dan graf lintasan Pm. Untuk m ¸ 2, strong rainbow connection number dari graf G = F2;6¤Pm adalah m + 1; 3. Akibat 4.1.2 Misal G adalah cartesian product dari graf Amal(F1;3; v = 1; 2) dan graf lintasan Pm. Untuk m ¸ 2, rainbow connection number dari graf G = Amal(F1;3; v = 1; 2)¤Pm adalah m + 1; 4. Teorema 4.1.2 Misal G adalah cartesian product dari graf Amal(F1;3; v = 1; 2) dan graf lintasan Pm. Untuk m ¸ 2, strong rainbow connection number dari graf G = Amal(F1;3; v = 1; 2)¤Pm adalah m + 1; 5. Akibat 4.1.3 Misal G adalah cartesian product dari graf Amal(W4; v = 1; 2) dan graf lintasan Pm. Untuk m ¸ 2, rainbow connection number dari graf G = Amal(W4; v = 1; 2)¤Pm adalah m + 1; 6. Teorema 4.1.3 Misal G adalah cartesian product dari graf Amal(W4; v = 1; 2) dan graf lintasan Pm. Untuk m ¸ 2, strong rainbow connection number dari graf G = Amal(W4; v = 1; 2)¤Pm adalah m + 1; 7. Teorema 4.1.4 Misal G adalah composition dari graf P2 dan F2;n. Untuk n ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = P2[F2;n] adalah 2; Teorema 4.1.5 Misal G adalah composition dari graf P2 dan Amal(F1;n; v = 1; 2). Untuk n ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = P2[Amal(F1;n; v = 1; 2)] adalah 2; 9. Teorema 4.1.6 Misal G adalah composition dari graf P2 dan Amal(Wn; v = 1; 2). Untuk n ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = P2[Amal(Wn; v = 1; 2)] adalah 2; 10. Teorema 4.1.7 Misal G adalah joint dari graf Amal(F1;n; v = 1; 2) dan Amal(Wn; v = 1; 2). Untuk n ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = Amal(F1;n; v = 1; 2) + Amal (Wn; v = 1; 2) adalah 2; 11. Teorema 4.1.8 Misal G adalah graf hasil operasi generalized shackle dari graf lengkap Kn, dimana n ¸ 4 dan r ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = gshack(Kn; P2; r) adalah r; 12. Teorema 4.1.9 Misal G adalah graf hasil operasi generalized shackle dari graf lengkap, dimana n ¸ 3 dan r ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = gshack(Kn;C3; r) adalah r; 13. Teorema 4.1.10 Misal G adalah graf hasil operasi generalized shackle dari graf Amal((K1 + Kn); v = 1; 2), dimana n ¸ 3 dan r ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = gshack(Amal((K1 + Kn); v = 1; 2);Kn; r) adalah 2r; 14. Teorema 4.1.11 Misal G adalah graf hasil operasi generalized shackle dari graf roda W6, dimana r ¸ 2, rainbow connection number dan strong rainbow connection number dari graf G = gshack(W6;C3; r) adalah 2r; 15. Teorema 4.1.12 Misal G adalah graf hasil operasi generalized shackle dari graf roda W6, dimana r ¸ 3 dengan r ganjil, rainbow connection number dan strong rainbow connection number dari graf G = gshack(W6;C1 4 ; r) adalah r + 1.