Perpustakaan Digital ITB

Misalkan G adalah graf terhubung nontrivial dengan himpunan titik V(G) dan himpunan sisi E(G). Jarak antara dua titik pada graf adalah panjang lintasan terpendek yang menghubungkan kedua titik tersebut. Jarak terjauh antara dua titik pada graf disebut diameter graf. Misalkan k ? N, dan fungsi c: E(G) ? {1, 2, … , k}. Lintasan u – v disebut lintasan pelangi, jika tidak ada 2 sisi pada lintasan tersebut yang memiliki warna sama. Graf G dikatakan terhubung pelangi di bawah c, jika untuk setiap u dan v di V(G), terdapat lintasan u-v pelangi. Pewarnaan c sehingga G terhubung pelangi disebut pewarnaan pelangi pada G. Jika pewarnaan c pada G merupakan pewarnaan pelangi yang menggunakan sebanyak k warna, maka c disebut pewarnaan-k pelangi pada G. Nilai k minimum sehingga terdapat pewarnaan-k pelangi pada G disebut bilangan terhubung pelangi, dinotasikan dengan rc(G). Setelah lebih dari sepuluh tahun sejak konsep bilangan terhubung pelangi pertama kali dipublikasikan pada jurnal, beberapa peneliti berhasil menentukan bilangan terhubung pelangi beberapa kelas graf. Pada tugas akhir ini dikonstruksi program untuk mendefinisikan suatu pewarnaan pelangi pada sebarang graf dan untuk menentukan suatu batas atas bilangan terhubung pelanginya dengan input berupa orde dan matriks ketetanggaan graf. Pengkonstruksian program yang dikembangkan menggunakan bahasa pemrograman Python.