Jurnal Matematika UNAND Vol. VI No. 1 Hal. 148 – 152 ISSN : 2303–2910 c
Jurusan Matematika FMIPA UNAND
PENENTUAN RAINBOW CONNECTION NUMBER PADA HASIL OPERASI CARTESIAN PRODUCT TERHADAP GRAF LINGKARAN DAN GRAF BIPARTIT LENGKAP DENGAN GRAF LINTASAN RESNITA YURI Program Studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Andalas, Kampus UNAND Limau Manis Padang, Indonesia, email :
[email protected]
Abstrak. Misalkan terdapat graf terhubung taktrivial G. Jika setiap sisi-sisi G diberi pewarnaan sehingga sebarang dua titik di G dihubungkan oleh suatu lintasan yang memiliki warna berbeda disetiap sisi, maka G disebut rainbow connected. Pewarnaan sisi dari G ditulis c : E(G) → {1, 2, · · · , k}; k ∈ N. Rainbow connection number dari graf G, dinotasikan dengan rc(G), adalah minimum dari banyaknya warna yang dibutuhkan untuk mewarnai G sehingga G rainbow connected. Cartesian product terhadap dua graf G1 dengan G2 dinotasikan dengan G1 × G2 . Dalam makalah ini akan dibahas kembali makalah [1] tentang penentuan bilangan rainbow connection dari graf Pn × K2,2 dan P3 × Cn . Diperoleh bahwa rc(Pn × K2,2 ) = n + 1 dan rc(P3 × Cn ) = d n e + 2. 2 Kata Kunci: Graf lingkaran, Graf lintasan, Graf bipartit lengkap, Rainbow connection number
1. Pendahuluan Misalkan G adalah graf terhubung tak-trivial. Definisikan pewarnaan c : E(G) → {1, 2, · · · , k}; k ∈ N, dimana sisi G yang bertetangga boleh memiliki warna yang sama. Suatu lintasan u − v ∈ G dikatakan rainbow path jika tidak ada dua sisi pada lintasan yang memiliki warna sama. Graf G dikatakan rainbow connected jika setiap dua titik yang berbeda di G dihubungkan oleh rainbow path. Dalam tulisan ini akan dibahas tentang rainbow connection number pada graf hasil operasi cartesian product antara graf lintasan dengan graf lingkaran, serta antara graf lintasan dengan graf bipartit lengkap K2,2 . Misalkan terdapat graf terhubung G dengan ukuran m. Ukuran m menyatakan banyaknya sisi yang ada dalam graf G. Hubungan antara diam(G), rc(G), src(G) dan ukuran m dijelaskan pada proposisi berikut. Proposisi 1.1. [3] Misalkan G adalah graf terhubung tak trivial berukuran m. Jika c : E(G) → {1, 2, · · · , k}, k ∈ N merupakan pewarnaan rainbow coloring, maka diam(G) ≤ rc(G) ≤ src(G) ≤ m. 148
Rainbow Connection Number untuk Graf Pn × K2,2 dan P3 × Cn
149
2. Rainbow Connection Number pada Hasil Operasi Cartesian Product Terhadap Graf Lingkaran dan Graf Bipartit Lengkap, dengan Graf Lintasan Pada Teorema 2.1 diberikan bilangan Rainbow Connection untuk graf hasil Cartesian Product graf bipartit lengkap K2,2 dengan graf lintasan Pn , untuk n ≥ 2. Teorema 2.1. [1] Untuk n ≥ 2, rainbow connection number untuk graf (Pn × K2,2 ) adalah n + 1. Bukti. Perhatikan bentuk graf Pn × K2,2 pada Gambar 1 berikut. Dapat dilihat
Gambar 1. Hasil operasi Pn × K2,2
bahwa graf G ' Pn × K2,2 mempunyai himpunan titik dan himpunan sisi sebagai berikut. V (Pn × K2,2 ) = {ai , bi , ci , di ; 1 ≤ i ≤ n}, E(Pn × K2,2 ) = {ai bi , ai di , bi ci , ci di ; 1 ≤ i ≤ n} [ {ai ai+1 , bi bi+1 , ci ci+1 , di di+1 ; 1 ≤ i ≤ n − 1}, dimana a1 = u1 v1 , b1 = u1 v3 , c1 = u1 v2 , d1 = u1 v4 , a2 = u2 v1 , b2 = u2 v3 , c2 = u2 v2 , d2 = u2 v4 , · · · , an = un v1 , bn = un v3 , cn = un v2 , dn = un v4 . Dapat dilihat bahwa p = |V (G)| = 4n dan q = |E(G)| = 8n − 4. Selanjutnya ditentukan jarak masing-masing titik pada graf Pn × K2,2 . Himpunan d(x, y) dimana x, y adalah sebarang titik pada graf Pn × K2,2 adalah d(x, y) = {1, 2, · · · , n + 1}. Maka diperoleh bahwa diam(Pn × K2,2 ) = max{d(x, y)|x, y ∈ V (Pn × K2,2 )} = n + 1. Karena diam(Pn × K2,2 ) = n + 1 maka rc(Pn × K2,2 ) ≥ n + 1.
(2.1)
Konstruksikan pewarnaan pada sisi-sisi graf Pn ×K2,2 , yang dapat dinyatakan dalam bentuk fungsi pewarnaan c : E(Pn × K2,2 ) → {1, 2, · · · , n + 1} sebagai berikut. 1, e = ai vi ; e = bi ui ; 1 ≤ i ≤ n, c(e) = 2, e = ai bi ; e = ui vi ; 1 ≤ i ≤ n, j, e = ai ai+1 ; e = bi bi+1 ; e = ui ui+1 ; e = vi vi+1 ; 1 ≤ i ≤ n − 1; 3 ≤ j ≤ n + 1.
150
Resnita Yuri
Berdasarkan pewarnaan tersebut diperoleh bahwa rc(Pn × K2,2 ) ≤ n + 1.
(2.2)
Dari (2.1) dan (2.2) diperoleh bahwa rc(Pn × K2,2 ) = n + 1. Pada Teorema 2.2 diberikan bilangan Rainbow Connection untuk graf hasil Cartesian Product graf lingkaran Cn dengan graf lintasan P3 , untuk n ≥ 3. Teorema 2.2. [1] Untuk n ≥ 3, rainbow connection number untuk graf (P3 × Cn ) adalah d n2 e + 2. Bukti. Perhatikan bentuk graf P3 × Cn pada Gambar 2 berikut.
Gambar 2. P3 × Cn
Misalkan V (P3 ) = {u1 , u2 , u3 } dan V (Cn ) = {v1 , v2 , · · · , vn }. Maka graf H ' P3 × Cn mempunyai himpunan titik dan himpunan sisi sebagai berikut. V (P3 × Cn ) = {ai , bi , ci ; 1 ≤ i ≤ n}, E(P3 × Cn ) = {ai bi , bi ci ; 1 ≤ i ≤ n} [ {an a1 , bn b1 , cn c1 },
[
{ai ai+1 , bi bi+1 , ci ci+1 ; 1 ≤ i ≤ n − 1}
dimana a1 = u1 v1 , b1 = u2 v1 , c1 = u3 v1 , a2 = u1 v2 , b2 = u2 v2 , c2 = u3 v2 , · · · , an = u1 vn , bn = u2 vn , cn = u3 vn . Dapat dilihat bahwa p = |V (H)| = 3n, q = |E(H)| = 5n. Selanjutnya ditentukan jarak masing-masing titik pada graf P3 × Cn . Himpunan d(x, y) dimana x, y adalah titik sebarang pada graf P3 × Cn adalah d(x, y) = {1, 2, · · · , d n2 e + 2}. Maka diperoleh bahwa n diam(P3 × Cn ) = max{d(x, y)|x, y ∈ V (P3 × Cn )} = d e + 2. 2
Rainbow Connection Number untuk Graf Pn × K2,2 dan P3 × Cn
151
Karena diam(P3 × Cn ) = d n2 e + 2 maka n (2.3) rc(Pn × K2,2 ) ≥ d e + 2. 2 Konstruksikan pewarnaan pada sisi-sisi graf P3 × Cn , yang dapat dinyatakan dalam bentuk fungsi pewarnaan c : E(P3 × Cn ) → {1, 2, · · · , d n2 e + 2} sebagai berikut. i, e = ai ai+1 ; e = bi bi+1 ; e = ci ci+1 ; 1 ≤ i ≤ d n2 e, n genap, e = ad n2 e+i ad n2 e+i+1 ; e = bd n2 e+i bd n2 e+i+1 ; e = cd n2 e+i cd n2 e+i+1 , 1 ≤ i ≤ d n2 e − 1, n genap, e = ai ai+1 ; e = bi bi+1 ; e = ci ci+1 ; 1 ≤ i ≤ d n2 e − 1, n ganjil, e = ad n2 e+i−1 ad n2 e+i ; e = bd n2 e+i−1 bd n2 e+i ; e = cd n2 e+i−1 cd n2 e+i , c(e) = 1 ≤ i ≤ d n2 e − 2, n ganjil, n d 2 e − 1, e = an−1 an ; e = bn−1 b1 ; cn−1 cn ; e = an a1 ; e = bn b1 ; e = cn c1 , d n2 e, d n2 e + 1, e = ai bi ; 1 ≤ i ≤ n, n d 2 e + 2, e = bi ci ; 1 ≤ i ≤ n. Berdasarkan pewarnaan tersebut diperoleh bahwa n rc(P3 × Cn ) ≤ d e + 2. 2 Dari (2.1) dan (2.2) diperoleh bahwa rc(P3 × Cn ) = d n2 e + 2.
(2.4)
Pewarnaan pada (P3 × C5 ) dapat dilihat pada Gambar 3.
Gambar 3. rc(P3 × C5 )
Pewarnaan pada (P3 × C6 ) dapat dilihat pada Gambar 4. 3. Kesimpulan Pada makalah ini telah dibahas kembali makalah [1] tentang penentuan bilangan rainbow connection dari graf Pn ×K2,2 dan P3 ×Cn . Diperoleh bahwa rc(Pn ×K2,2 ) = n + 1 dan rc(P3 × Cn ) = d n2 e + 2.
152
Resnita Yuri
Gambar 4. rc(P3 × C6 )
4. Ucapan Terima Kasih Penulis mengucapkan terima kasih kepada Bapak Prof. Dr. Syafrizal Sy, Bapak Dr. Effendi, Ibu Dr. Lyra Yulianti, Bapak Narwen, M.Si, dan Bapak Dr. Admi Nazra, yang telah memberikan masukan dan saran sehingga makalah ini dapat diselesaikan dengan baik. Daftar Pustaka [1] Arnasyitha, Yulianti. dan Dafik. Rainbow Connection Number Pada Operasi Graf. Prosiding Seminar Nasional Matematika 2014. Universitas Jember, hal. 83 – 87 [2] Bondy, J. A. dan U. S. R. Murty. 1976. Graph Theory with Applications. Macmillan. London [3] G. Chartrand, G.L. Johns, K.A. McKeon, dan P. Zhang. 2008. Rainbow connection in graphs. Math. Bohem., 133(2) : 85 – 98 [4] Darmawan, R. N. 2015. Analisis Rainbow Connection Number pada Graf Khusus dan Hasil Operasinya. Tesis S-2, tidak diterbitkan, Universitas Jember. Jember [5] Harary, F. 1970. Graph Theory. Wesley Publishing Company. London [6] Kitaev, S. dan Lozin,V. 2015. Words and Graphs. Springer. New York [7] Li, Xueliang, and Liu, Sujuan, Rainbow Connection Number and Connectivity. 2012. The Electronic Journal of Combinatorics 19 : P20 [8] Li, X. dan Sun, Y.2012. Rainbow Connection of Graphs. Springer. New York.
