Bilangan Khromatik Pewarnaan Sisi pada Graf Khusus dan Operasinya

Bilangan Khromatik Pewarnaan Sisi pada Graf Khusus dan Operasinya Ilham Saifudin1 , Dafik2 of Jember 2 Department of Mathematics FMIPA University of Jember [email protected] 3 Department of Mathematics Education FKIP University of Jember [email protected] 1 CGANT-University

Abstract Misal G adalah graf sederhana dan tidak berarah. Representasi visual dari graf G adalah dinyatakan dengan himpunan titik dan sisi ditulis G = (V, E). Salah satu kajian terhadap graf G yang mempunyai aplikasi luas adalah graph colouring yang terdiri dari pewarnaan simpul, sisi, dan wilayah. Dalam makalah ini akan dibahas pewarnaan sisi. Pewarnaan sisi adalah pemberian warna pada sisi graf G sedemikian sehingga tidak ada dua sisi yang bersisian mempunyai warna yang sama. Jumlah warna minimum yang dapat digunakan untuk mewarnai graf dinyatakan dengan bilangan khromatik. Makalah ini fokus mengkaji tentang bilangan kromatik pada grafgraf khusus dan operasinya. Key Words :Pewarnaan sisi graf, Bilangan kromatik.

Pendahuluan Graf adalah salah satu pokok bahasan Matematika Diskrit yang telah lama dikenal dan banyak diaplikasikan pada berbagai bidang. Dalam merepresentasikan visual dari suatu graf yaitu dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau vertex, sedangkan hubungan antara objek dinyatakan dengan garis atau edge. Secara umum, graf [4] adalah pasangan himpunan (V, E) di mana V adalah himpunan tidak kosong dari simpul simpul (vertex atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul pada graf tersebut. V = v1 , v2 , v3 , ..., vn ; E = e1 , e2 , e3 , ..., en atau E = (v1 , v2 ), (v2 , v3 ), (v3 , v4 ), ..., (vn−1 , vn ) Di mana e = (vi , vj ) yang artinya sisi yang menghubungkan simpul vi dan vj . Salah satu topik yang menarik adalah masalah pewarnaan graf (graph coloring). Bidang ini memiliki sejarah menarik dan teori-teorinya telah menimbulkan banyak perdebatan pada kalangan matematikawan. Umumnya pewarnaan graf [6] digunakan untuk memodelkan suatu masalah sehingga menjadi lebih mudah, yaitu dengan cara merepresentasikan objek-objek tersebut. Contoh

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . .

203

pemodelan suatu masalah dengan menggunakan pewarnaan graf dapat dilihat pada penggambaran rangkaian listrik, penyusunan jadwal, jaringan komunikasi, jaringan network komputer, analisis algoritma, peta, struktur hierarki sosial, dan lain-lain. Dalam paper ini, akan membahas salah satu aplikasi pewarnaan graf (graph colo ring), khususnya pewarnaan pada sisi graf G sedemikian sehingga tidak ada dua sisi yang bersisian mempunyai warna yang sama, sehingga akan diperoleh jumlah minimum warna dengan notasi ϕ(G) dan nantinya akan dinyatakan dengan bilangan kromatik dengan notasi χ(Cn ). Penelitian terkait Pewarnaan Sisi berkembang cukup pesat, lihat [2],[7],[8],[9]. Graf yang digunakan dalam penelitian fokus pada beberapa graf khusus beserta operasinya [3], diantaranya yaitu: Prims graph (Hm,n ), Ladder Graph (Ln ), Fan Graph (Fn ), Crown Graph (Pn ⊙ P3 ), Graph Composition (G2 [G1 ]).

Pewarnaan Graf Pewarnaan graf (graph coloring) adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu. Pewarnaan sisi (edge coloring) adalah memberi warna berbeda pada sisi yang bersisian sehingga tidak ada dua sisi yang bersisian mempunyai warna yang sama. Jumlah warna minimal ϕ(G) [1],[5]yang dapat digunakan untuk mewarnai sisi-sisi dalam suatu graph G disebut bilangan khromatik G. Theorem 1 Teorema (Vizing 1964)[10]. Jika G adalah graph sederhana, maka χ(G) ≤ ∆(G) atau χ(G) ≤ ∆(G) + 1

Hasil Pewarnaan Sisi Graf Khusus dan Operasinya Dalam penelitian diperoleh beberapa teorema yang berhubungan dengan Khromatik Pewarnaan Sisi Graf Khusus dan Operasinya meliputi: Prims graph Hm,n , Ladder Graph Ln , Fan Graph (Fn ), Crown Graph (Pn ⊙ P3 ), Graph Composition (G2 [G1 ]). 3 Teorema 1 Diberikan G = Hm,n untuk m ≥ 3 dan n ≥ 3, bilangan khromatik χ(Hm,n ) = 4.

204

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . .

xm,1

3 1

2

x3,1 4

xm,n

2

3

1

x3,n

4

1

x2,n 3

x1,1

3

1

x1,2

x1,n 2 1

1

1

1 3 4

x2,2

2

x1,5 2

x2,5

x3,2

4

3

2

xm,2

3

x2,1

1

x1,3 3

x1,4 2

2

2

2

x2,3 4 1

3 3

x3,3

x3,5 2

3

x2,4 1

xm,5

xm,3

4 2 x3,4

1

3

xm,4

Figure 1: Prims graph Hm,n Bukti. Prims graph adalah graf yang memiliki V (Hm,n ) = {xi,j ; 1 ≤ i ≤ m; 1 ≤ j ≤ n}, E(Hm,n ) = {xi,j xi+1,j ; 1 ≤ i ≤ m−1; 1 ≤ j ≤ n} ∪ {xm,j x1,j ; 1 ≤ j ≤ n} ∪ {xi,j xi,j+1 ; 1 ≤ i ≤ m; 1 ≤ j ≤ n}, p = |V |=m.n dan q = |E|=2m.n−n. Untuk n = 6 pada Prims graph Hm,n akan dinyatakan batas atas dan bawah χ(Hm,6 ) ≤ ∆(Hm,6 ) atau χ(Hm,6 ) ≤ ∆(Hm,6 ) + 1 dengan derajat χ(Hm,6 ) = ∆(Hm,6 ) atau χ(Hm,6 ) = ∆(Hm,6 ) + 1. Dengan demikian karena ∆(Hm,6 ) = 3 diperoleh χ(Hm,6 ) = 4, sehingga terbukti bahwa bilangan khromatik χ(Hm,6 ) = 4 dengan batas χ(Hm,6 ) ≤ 4. Untuk m ≥ 3 dan n ≥ 3, graf G = Hm,n diwarnai sisinya dengan menggunakan fungsi berikut:

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . . Untuk ekspan n ganjil:   1, e = xi,j xi ,j+1 ;      1, e = xi,n xi+1 ,n ;      2, e = xi,j xi ,j+1 ;  f (e) = 2, e = xi,1 xi,1 ;    3, e = xi,n xi,1 ;      3, e = xi,j xi+1 ,j ;     4, e = xi,j xi+1 ,j ; Untuk ekspan n genap:   1, e = xi,j xi ,j+1 ;       2, e = xi,j xi ,j+1 ; f (e) = 2, e = xi,n xi,1 ;    3, e = xi,j xi+1,j ;     4, e = xi,j xi+1 ,j ;

205

untuk 1 ≤ i ≤ m, jika j adalah ganjil, 1 ≤ j < n − 1 jika i adalah ganjil untuk 1 ≤ i ≤ m, jika j adalah genap, 1 < j < n − 1 jika i adalah ganjil untuk 1 ≤ i ≤ m jika i adalah ganjil, 1 < j < n − 1 jika i adalah genap, 1 ≤ j ≤ n

untuk 1 ≤ i ≤ m, jika j adalah ganjil, 1 ≤ j < n − 1 untuk 1 ≤ i ≤ m, jika j adalah genap, 1 < j ≤ n untuk 1 ≤ i ≤ m jika i adalah ganjil, 1 ≤ j ≤ n jika i adalah genap, 1 ≤ j ≤ n

Jelas bahwa bilangan khromatik χ(Hm,n ) = 4, untuk n ganjil maupun genap jelas memenuhi batas bawah dan atas pewarnaan sisinya ϕ(Hm,n ) ≤ 4. 2 3 Teorema 2 Diberikan G = Ln untuk n ≥ 3, bilangan khromatik χ(Ln ) = 3.

x1

3

1

x2

1 3

2

x3

y3 1

3

y4 2

2

xn

y2 2

3

1

x4

y1

3

yn

Figure 2: Ladder Graph Ln Bukti. Ladder Graph adalah graf yang memiliki V (Ln ) = {xi ; 1 ≤ i ≤ n; n ≤ 2} ∪ {yi ; 1 ≤ i ≤ n; n ≤ 2}, E(Ln ) = {xi yi ; 1 ≤ i ≤ n; n ≤ 2} ∪ {xi xi+1 ; 1 ≤ i ≤ n; n ≤ 1}∪ {yi yi+1 ; 1 ≤ i ≤ n; n ≤ 1}, p = |V |=4.n dan q = |E|=3.n + 1.

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . .

206

Untuk n = 3 pada Ladder Graph Ln akan dinyatakan batas atas dan bawah χ(L3 ) ≤ ∆(L3 ) atau χ(L3 ) ≤ ∆(L3 ) + 1 dengan derajat χ(L3 ) = ∆(L3 ) atau χ(L3 ) = ∆(L3 ) + 1. Dengan demikian karena ∆(L3 ) = 3 diperoleh χ(L3 ) = 3, sehingga terbukti bahwa bilangan khromatik χ(Ln ) = 3 dengan batas χ(Ln ) ≤ 3. Untuk n ≥ 3, graf G = Ln diwarnai sisinya dengan menggunakan fungsi berikut:   1, e = xi xi+1 ; jika i adalah ganjil       2, e = xi xi+1 ; jika i adalah genap f (e) = 1, e = yi yi+1 ; jika i adalah ganjil    2, e = yi yi+1 ; jika i adalah genap     1≤i≤n 3, e = xi yi ; Jelas bahwa bilangan khromatik χ(Ln ) = 3, untuk n ganjil maupun genap, jelas memenuhi batas bawah dan atas pewarnaan sisinya ϕ(Ln ) ≤ 3. 2 3 Teorema 3 Diberikan G = Fn untuk n ≥ 2, bilangan khromatik χ(Fn ) = 2n

1 xn

x1 3

yn n

y1

1 2

7 c 6

5

3 4 x2

y3 1

x3

y2 1

Figure 3: Fan Graph (Fn ) Bukti. Fan Graph adalah graf yang memiliki V (Fn ) = {c} ∪ {xi ; 1 ≤ i ≤ n; n ≥ 3} ∪ {yi ; 1 ≤ i ≤ n; n ≥ 3}, E(Fn ) = {cxi ; 1 ≤ i ≤ n; n ≥ 3} ∪ {cyi ; 1 ≤ i ≤ n; n ≥ 3} ∪ {xi yi ; 1 ≤ i ≤ n; n ≥ 3}, p = |V |=2.n + 1 dan q = |E|=3.n. Untuk n = 3 pada Fan Graph G = (Fn ) akan dinyatakan batas atas dan bawah χ(F3 ) ≤ ∆(F3 ) atau χ(F3 ) ≤ ∆(F3 ) + 1 dengan derajat χ(F3 ) = ∆(F3 ) atau χ(F3 ) = ∆(F3 ) + 1. Dengan demikian karena ∆(F3 ) = 6 diperoleh χ(F3 ) = 6, sehingga terbukti bahwa bilangan khromatik χ(Fn ) = 2n dengan batas χ(Fn ) ≤ 2.n. Untuk n ≥ 2, graf G = Fn diwarnai sisinya dengan menggunakan fungsi berikut:

207

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . .

  1, e = xi yi ;     3, e = x y ; 1 1 f (e) =  2.n; e = cxi ;     2.n; e = cy ; i

untuk 1 < i ≤ n untuk i = 1 1 ≤ i ≤ n, jika i adalah ganjil 1 ≤ i ≤ n, jika i adalah genap

Jelas bahwa bilangan khromatik χ(Fn ) = 2n, untuk n ganjil maupun genap, jelas memenuhi batas bawah dan atas pewarnaan sisinya ϕ(Fn ) ≤ 2n. 2 3 Teorema 4 Diberikan G = (Pn ⊙ P3 ) untuk n ≥ 3, bilangan khromatiknya χ(Pn ⊙ P3 ) = 5.

1 y1 3

1

2 y2 4 x1

2

y7

y3

3

5 x2

1 3

4

y4

y9

4 5

2

x3

5 y6

y5 1

y8

2

Figure 4: Crown Graph (Pn ⊙ P3 ) Bukti. Joint Graph adalah graf yang memiliki V (Pn ⊙ P3 ) = {xi ; 1 ≤ i ≤ n} ∪ {yi ; 1 ≤ i ≤ n}, E(Pn ⊙ P3 ) = {xi yi ; 1 ≤ i ≤ n} ∪ {yi yi+1 ; 1 ≤ i ≤ n}, p = |V |=4.n dan q = |E|=6.n−1. Untuk n = 3 pada Crown Graph Pn ⊙P3 akan dinyatakan batas atas dan bawah χ(P3 ⊙ P3 ) ≤ ∆(P3 ⊙ P3 ) atau χ(P3 ⊙ P3 ) ≤ ∆(P3 ⊙ P3 ) + 1 dengan derajat χ(P3 ⊙ P3 ) = ∆(P3 ⊙ P3 ) atau χ(P3 ⊙ P3 ) = ∆(P3 ⊙ P3 ) + 1. Dengan demikian karena ∆(P3 ⊙ P3 ) = 5 diperoleh χ(P3 ⊙ P3 ) = 5, sehingga terbukti bahwa bilangan khromatik χ(Pn ⊙ P3 ) = 5 dengan batas χ(Pn ⊙ P3 ) ≤ 5. Untuk n ≥ 3, graf G = Pn ⊙ P3 diwarnai sisinya dengan

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . . menggunakan fungsi berikut:   1, e = xi xi+1 ;      1, e = y3.i−2 y(3.i−2)+1 ;       2, e = xi xi+1 ; f (e) = 2, e = y3.i−1 y(3.i−1)+1 ;    3, e = xi y3.i−2 ;      4, e = xi y3.i−1 ;     5, e = xi y3.i ;

208

jika i adalah ganjil untuk 1 < i ≤ n jika i adalah genap untuk 1 < i ≤ n untuk 1 < i ≤ n untuk 1 < i ≤ n untuk 1 < i ≤ n

Jelas bahwa bilangan khromatik χ(Pn ⊙ P3 ) = 5, untuk n ganjil maupun genap, 2 jelas memenuhi batas bawah dan atas pewarnaan sisinya ϕ(Pn ⊙ P3 ) ≤ 5. 3 Teorema 5 Diberikan G = (G2 [G1 ]) untuk n ≥ 3, bilangan khromatiknya χ(G2 [G1 ]) = 5.

1

x1 3

2

4

xn

2

1

3

y4 4

4

5

y3

1

x4 5

4

2

3

y2

1

x3 3

2 1

x2 5

y1

5

yn

Figure 5: Graph Composition G2 [G1 ] Bukti. Graph Composition adalah graf yang memiliki V (G2 [G1 ]) = {xi ; 1 ≤ i ≤ n; n ≤ 2} ∪ {yi ; 1 ≤ i ≤ n; n ≤ 2}, E(G2 [G1 ]) = {xi yi ; 1 ≤ i ≤ n; n ≤ 2} ∪ {xi xi+1 ; 1 ≤ i ≤ n; n ≤ 2} ∪ {xi xi+1 ; 1 ≤ i ≤ n; n ≤ 2} ∪ {yi yi+1 ; 1 ≤ i ≤ n; n ≤ 2}, p = |V |=4.n dan q = |E|=5n + 1. Untuk n = 4, batas atas dan bawah χ(G2 [G1 ]) ≤ ∆(G2 [G1 ]) atau χ(G2 [G1 ]) ≤ ∆(G2 [G1 ]) + 1 dengan derajat χ(G2 [G1 ]) = ∆(G2 [G1 ]) atau χ(G2 [G1 ]) = ∆(G2 [G1 ]) + 1. Dengan demikian karena ∆(G2 [G1 ]) = 5 diperoleh χ(G2 [G1 ]) = 5, sehingga terbukti bahwa bilangan khromatik χ(G2 [G1 ]) = 5 dengan batas χ(G2 [G1 ]) ≤ 5. Untuk

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . .

209

n ≥ 3, graf G = G2 [G1 ] diwarnai sisinya dengan menggunakan fungsi berikut:   1, e = xi yi ; untuk 1 < i ≤ n      2, e = xi yi+1 ; jika i adalah ganjil      2, e = xi yi−1 ; jika i adalah genap       3, e = xi xi+1 ; jika i adalah ganjil f (e) = 3, e = yi yi+1 ; jika i adalah ganjil    4, e = xi yi+1 ; jika i adalah genap      4, e = xi yi−1 ; jika i adalah ganjil      5, e = xi xi+1 ; jika i adalah genap     5, e = yi yi+1 ; jika i adalah genap Jelas bahwa bilangan khromatik χ(G2 [G1 ]) = 5, untuk n ganjil maupun genap, 2 jelas memenuhi batas bawah dan atas pewarnaan sisinya: ϕ(G2 [G1 ]) ≤ 5.

Kesimpulan Bilangan khromatik pewarnaan sisi pada graf khusus dan operasinya adalah Prims graph Hm,n adalah ϕ(Hm,n ) ≤ 4, Ladder Graph Ln adalah ϕ(Ln ) ≤ 3, Fan Graph Fn adalah ϕ(Fn ) ≤ 2n, Crown Graph Pn ⊙ P3 adalah ϕ(Pn ⊙ P3 ) ≤ 5, Graph Composition G2 [G1 ] adalah ϕ(G2 [G1 ]) ≤ 5.

References [1] Asmiati, H. Assiyatun, dan E.T. Baskoro, Locating-chromatic number of amalgamation of stars. ITB J. Sci, 2011, 1-8. [2] Budajova, Julius Czap, Locating-chromatic number of amalgamation of stars FACIAL R-ACYCLIC EDGE-COLORINGS OF PLANE GRAPHS. Technical University of Kosice,2013, Volume 85 No. 1 141-147 [3] Dafik, F. Alfin, F. M. Kunti, Super Antimagicness of A Well-defined Graph Indonesia, Saintifika 14 (2012), 106–118. [4] Dafik, Structural Properties and Labeling of Graphs. University of Ballarat, 2007. [5] Gary Chartrand and Ping Zhang, Chromatic Graph Theory. Chapman and Hall, 2008.

Ilham S., et.al: Bilangan Khromatik Pewarnaan Sisi pada . . .

210

[6] Marx, Daniel, Graph Coloring Problems And Their Applications In Scheduling, Sabri, New Graph Coloring, Algorithms. Springer, Berlin, 2007 [7] Preeti Gupta, A study of Vertex - Edge Coloring Techniques with Application. Department of Engg. Mathematics, 2014 Volume 1, Issue 2 [8] Poornima B,Dr. V. Ramaswamy, Application of Edge Coloring of a Fuzzy Graph. I.S and E Department, B.I.E.T. Davangere, 2010. Volume 6 [9] R.Cole, J. Hopcroft, On edge coloring bipartite graphs,SIAM Journal on Computing11 (1982) 540-546. [10] Vizing, On an estimate of the chromatic class of ap-graph, (in Russian), Diskret. Analiz, 1964, 25-30