Rainbow Connection Number pada Graf Hasil Operasi Perkalian Kartesian Graf Bintang dan Graf Segitiga

Abstract

Salah satu teori yang dikembangkan dalam teori graf adalah koneksi pelangi (rainbow connection). Rainbow Connection pertama kali diperkenalkan oleh Chartrand pada tahun 2006. Graf dengan rainbow connection adalah graf yang setiap dua titik-titiknya dihubungkan oleh minimal satu rainbow path. Rainbow path (lintasan pelangi) merupakan lintasan yang setiap sisi pada lintasan tersebut memiliki warna berbeda. Pewarnaan sisi pada graf dengan rainbow connection disebut rainbow coloring. Bilangan koneksi pelangi (rainbow connection number) merupakan banyaknya pewarnaan minimal dari graf dengan rainbow connection. Rainbow connection number dari graf dinotasikan dengan rc(G). Jika setiap lintasan pelangi yang terbentuk antara sebarang dua titik pada graf merupakan lintasan dengan jarak minimum, maka banyaknya pewarnaan minimal dari graf dengan rainbow connection disebut dengan koneksi pelangi kuat (strong rainbow connection number) yang dinotasikan dengan src(G) (Chatrand et al., 2008). Operasi pada graf dapat dilakukan terhadap dua atau lebih graf berbeda maupun graf yang sama. Salah satu jenis operasi graf adalah operasi perkalian kartesian (cartesian product). Operasi tersebut merupakan operasi graf yang digunakan dalam penelitian ini yaitu dengan graf yang dioperasikan adalah graf bintang dan graf segitiga (SnC3). Penelitian ini menggunakan metode deduktif aksiomatik dan metode pendeteksian pola (patern recognition). Tujuan penelitian ini adalah untuk menentukan rainbow connection number dan strong rainbow connection number pada hasil perkalian kartesian graf bintang dan graf segitiga (SnC3). Penelitaian ini menghasilkan rainbow connection number dari bernilai 3 untuk n=3 di mana 3 tersebut merupakan diameter dari dan bernilai 4 untuk n > 3. Penelitian ini juga menghasilkan strong rainbow connection number dari (SnC3) bernilai untuk n>= 3 .