Penerapan Rainbow 2-Connected Pada Graf Khusus Dan Graf Hasil Operasi Korona Dan Cartesian

Abstract

Salah satu bagian dari matematika diskrit yang sering kali digunakan se- bagai alat bantu untuk menggambarkan suatu permasalahan agar lebih mudah dipahami dan diselesaikan adalah teori graf atau graph theory. Meskipun pada awalnya graf diciptakan untuk diterapkan dalam penyelesaian kasus, namun graf telah mengalami perkembangan yang sangat luas didalam teori graf itu sendiri (Slamin, 2009). Teori graf pertama kali diperkenalkan oleh matematikawan berke- bangsaan Swiss pada 1936 yaitu Leonhard Euler, melalui tulisannya yang berisi tentang pemecahan masalah Jembatan Konigsberg yang sangat sulit dipecahkan pada masa itu. Rainbow connection atau koneksi pelangi yang merupakan salah satu teori pada graf adalah pemberian warna pada sisi graf dimana setiap dua titik yang berbeda harus memiliki minimal satu lintasan yang bisa dilewati (rainbow path) sehingga graf tersebut bersifat rainbow connected. Pewarnaan minimal yang digu- nakan pada graf G agar dapat dikatakan rainbow connected disebut dengan istilah rainbow connection number yang dinotasikan dengan rc(G). Apabila terdapat minimal 2 bagian dalam rainbow path yang terpisah (internaly disjoin rainbow path) yang menghubungkan setiap dua titik berbeda di G, maka graf G dikatakan rainbow 2-connected yang dinotasikan dengan rc2(G) (Chartrand et al., 2006). Rainbow 2-connected dapat diaplikasikan pada proses distribusi pesan, barang, dokumen rahasia, soal-soal ujian dan lain sebagainya agar terjaga kemanannya. Misalnya untuk distribusi dokumen rahasia berupa soal SBMPTN, memberikan pengawalan ketat dan tim pengawas merupakan salah satu cara untuk memini- malisir terjadinya kecurangan dalam proses pendistribusian soal SBMPTN dari pusat penyimpanan soal sampai ke Perguruan Tinggi atau Universitas agar kera- hasiaan soal tetap terjaga, dimana jalur yang akan dilewati distributor dijaga oleh tim pengawas yang berbeda. Hal ini ditujukan agar tim pengawas dapat fokus dalam menjalankan tugasnya di masing-masing jalur yang telah ditentukan. Jalan alternatif juga harus disediakan dalam proses distribusi soal SBMPTN ini demi menghindari kemacetan jalan. Apabila soal sampai ke Universitas dengan jumlah sama seperti semula, maka dapat dikatakan bahwa tidak terjadi kecurangan saat pendistribusian.