Page 105 - Trends in Science and Technology fo Sustainable Living

66 Fakultas Sains dan Teknologi
Universitas Terbuka (2023)

Sumber: Wardani dkk., 2018
Gambar 17. Graf P  P
3 4
TERHUBUNG PELANGI PADA GRAF

Pada tahun 2008, Chartrand dkk. mengembangkan konsep
terhubung pelangi pada graf sebagai berikut. Misalkan G graf
terhubung non-trivial. Untuk k bilangan asli, suatu pemetaan
c : ( )E G → { 1,2, ,k } adalah pewarnaan sisi pada graf G. Lintasan
pada graf G disebut lintasan pelangi jika tidak ada dua sisi di lintasan
tersebut yang memiliki warna sama. Graf G disebut terhubung
pelangi (terkait dengan c) jika G memuat suatu lintasan u - v pelangi
untuk setiap pasang titik u dan v di G. Adapun pewarnaan c disebut
pewarnaan sisi pelangi atau pewarnaan pelangi. Jika warna yang
digunakan dalam pewarnaan pelangi graf G sebanyak k, maka c
disebut pewarnaan-k pelangi. Bilangan terhubung pelangi adalah
k bilangan asli terkecil sehingga terdapat pewarnaan-k pelangi
pada graf G. Bilangan terhubung pelangi dinotasikan dengan rc(G).
Dalam hal ini, jika diam(G) = k, maka berlaku rc(G)≥k.