Page 106 - Trends in Science and Technology fo Sustainable Living

Trends in Science and Technology 67
for Sustainable Living

(a) (b)
Gambar 18. Pewarnaan-3 Pelangi Graf Petersen (a) dengan Label
Angka (Chartrand & Zhang, 2020), (b) dengan Warna

Sebagai contoh, perhatikan graf Petersen pada Gambar 18.
Misalkan graf Petersen G mempunyai pewarnaan-3 pelangi dengan
pewarnaan sisi seperti yang ditunjukkan pada Gambar 18 sehingga
berlaku rc(G)≤3. Selanjutnya, karena diam(G) = 2 diperoleh rc(G)≥2.
Namun tidak ada pewarnaan-2 pelangi pada graf Petersen, maka
andaikan terdapat pewarnaan sisi c. Karena graf Petersen G adalah
graf kubik, terdapat dua sisi bertetangga, misalkan uv dan vw, yang
berwarna sama yaitu c. Karena girth g(G) = 5, lintasan u - w yaitu
(u, v, w) adalah lintasan dengan panjang 2. Karena lintasan tersebut
bukan lintasan pelangi, c bukan pewarnaan pelangi, maka rc(G)=3.
Misalkan c adalah pewarnaan sisi suatu graf terhubung non-
trivial G. Untuk setiap pasang titik u dan v di G, geodesik u - v pelangi
adalah lintasan pelangi u - v dengan panjang d(u, v). Jika G memuat
suatu geodesik u - v pelangi untuk setiap pasang titik u dan v di G
maka G dikatakan terhubung pelangi kuat. Adapun pewarnaan c
disebut pewarnaan pelangi kuat di G. Bilangan terhubung pelangi
kuat, yang dinotasikan dengan src(G), adalah k bilangan asli terkecil
sedemikian hingga G mempunyai pewarnaan-k pelangi kuat.
Bilangan ini disebut juga bilangan diameter pelangi (Chakraborty
dkk, 2011). Secara umum, jika G adalah graf terhubung non-trivial
berukuran m, maka

diam()G ≤ rc ()G ≤ src ()G ≤ m (1)