1
Kajian Bilangan Kromatik Total Pada Graf Bebas Unichord dan Kincir Rindi Eka Widyasari, Dr. Darmaji, S.Si., M.T. Jurusan Matematika, Fakultas MIPA, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected]
Abstrak— Pewarnaan total graf G adalah fungsi yang memasangkan himpunan simpul dan himpunan sisi dengan himpunan bilangan asli yang merepresentasikan warna, sehingga tidak ada dua simpul atau dua sisi berdekatan memiliki warna yang sama. Pada umumnya, pewarnaan total hanya mewarnai elemen-elemen pada graf yang saling berdekatan dan melekat menggunakan warna yang berbeda. Kemudian muncul teori pewarnaan total dengan jumlah warna minimal. Jumlah warna minimal yang digunakan untuk mewarnai simpul dan sisi pada graf G disebut bilangan kromatik total G, dinotasikan dengan χ T (G ) . Pada Tugas Akhir ini dikaji bilangan kromatik total pada graf bebas unichord adalah NP-lengkap dan graf kincir adalah ∆ (G ) + 1 . Kata kunci: Pewarnaan Total, Bilangan Kromatik Total, Graf Bebas Unichord, Graf Kincir.
I. PENDAHULUAN EBUAH graf G = (V , E ) berisikan dua himpunan yaitu himpunan berhingga tak kosong V (G ) dari elemenelemen yang disebut simpul dan himpunan berhingga (mungkin kosong) E (G ) yang elemen-elemennya disebut
S
sisi, sehingga setiap elemen
e dalam
E (G ) merupakan
pasangan tak berurut dari simpul-simpul di V (G ) . Beberapa contoh graf adalah graf kincir, graf siklus, graf chordal dan graf bebas unichord. Graf kincir dinotasikan dengan Wnm , yaitu m buah kopi graf lengkap yang disjoint dikenakan operasi korona terhadap K1 . Graf siklus adalah graf yang terdiri dari siklus tunggal, atau dengan kata lain, beberapa simpul yang terhubung dalam rantai tertutup. Sebuah graf disebut graf chordal jika setiap siklus dengan simpul empat atau lebih memiliki sebuah chord, yaitu sisi yang menghubungkan dua simpul dalam siklus yang tidak berdekatan. Sedangkan disebut graf bebas unichord adalah graf yang tidak memiliki sebuah chord unik. Dalam graf terdapat subgraf (graf bagian). Sebuah graf H disebut subgraf dari graf G , ditulis H ⊆ G , jika V ( H ) ⊆ V (G ) dan
E ( H ) ⊆ E (G ) .
Teori graf dapat digunakan untuk menyelesaikan masalahmasalah berikut, penjadwalan ujian, penjadwalan truk pengangkut sampah dan pembagian tugas (tugas yang banyak dapat dibagi menjadi tugas-tugas kecil). Permasalahan tersebut dapat diselesaikan dengan pewarnaan graf. Pewarnaan graf merupakan sebuah fungsi yang memasangkan elemen-elemen pada graf, berupa simpul, sisi, ataupun keduanya, dengan himpunan bilangan asli yang merepresentasikan warna sehingga elemen-elemen yang saling berdekatan memiliki warna yang berbeda. Pewarnaan graf mengusahakan agar jumlah warna yang digunakan minimal, jumlah warna minimal yang digunakan disebut bilangan kromatik G , χ (G ) Sulistyowati [1] melakukan kajian teori mengenai bilangan kromatik simpul pada graf menggunakan algoritma Welch-Powell. Kemudian muncul teori pewarnaan total dengan jumlah warna minimal dan dinotasikan dengan χ T (G ) . Bilangan kromatik total pada graf pertama kali dikaji oleh Behzad [2] dan membuat konjektur yang menyatakan bahwa untuk sebarang graf G bilangan kromatik totalnya kurang dari atau sama dengan derajat maksimal ditambah dengan dua warna. Pada tahun 1967 Behzad dkk., mengkaji bilangan kromatik total untuk graf lengkap dan mendapatkan ∆( K n ) + 1, ganjil , χT ( K n ) = ∆( K n ) + 2, genap kemudian Yap [3] mengkaji bilangan kromatik total pada graf berderajat maksimal ∆(G ) = 3 dan graf r-partit lengkap dan mendapatkan
χ T (G ) = ∆(G ) + 2 . Dengan merujuk pada
paper [4] maka dalam makalah ini, penulis melakukan kajian bilangan kromatik total pada graf bebas unichord dan kincir. II. DASAR-DASAR GRAF A. Deskripsi Pengelompokan Graf Graf yang digunakan dalam penelitian ini termasuk graf sederhana, berhingga dan terhubung. Graf siklus adalah graf yang terdiri dari siklus tunggal, atau dengan kata lain, beberapa simpul yang terhubung dalam rantai tertutup. Graf
2 siklus dengan
n simpul disebut
C n . Gambar 1 merupakan
siklus C6 . Sebuah graf disebut graf chordal jika setiap siklus dengan simpul empat atau lebih memiliki sebuah chord, yaitu sisi yang menghubungkan dua simpul dalam siklus yang tidak berdekatan. Gambar 2 merupakan graf chordal dengan 8 simpul. Graf bebas unichord adalah graf yang tidak memiliki sebuah chord unik. Dalam [5], graf bebas unichord dikelompokkan dalam kelas C . Kelas C berada dalam kelas dasar atau yang mempunyai dekomposisi. Graf dalam kelas dasar adalah graf siklus chordless, cliques (subgraf yang maksimum), graf bipartit dengan satu sisi hanya memuat simpul berderajat dua dan subgraf terinduksi dari graf Heawood atau graf Petresen. Gambar 3 merupakan graf Petersen dan subgraf terinduksinya. Graf kincir Wnm adalah graf yang dibentuk dari hasil operasi korona m buah kopi graf lengkap yang disjoint dengan K1 . Gambar 4 merupakan graf kincir W25 .
Gambar 1 Graf siklus C6 .
Gambar 2 Graf chordal
2. Pewarnaan Sisi Pewarnaan sisi pada graf G adalah suatu fungsi d : E (G ) → N dengan E (G ) merupakan himpunan sisi dan himpunan bilangan asli N. Dengan kata lain pewarnaan sisi pada graf G sehingga sisi yang bersisihan memperoleh warna yang berbeda. Jumlah warna minimal yang digunakan disebut dengan indeks kromatik, dinotasikan dengan χ ' (G ) . 3. Pewarnaan Total Misalkan diberikan graf G , pewarnaan total adalah sebuah fungsi f : V E → N . Secara teori pewarnaan total bertujuan mewarnai himpunan simpul dan himpunan sisi pada graf G sehingga simpul dan sisi yang melekat, dua simpul yang bersisihan dan dua sisi yang bersisihan memiliki warna yang berbeda. Jumlah warna minimal yang digunakan disebut dengan bilangan kromatik total, dinotasikan dengan χ T (G ) . C. Beragam Tipe Bilangan Kromatik Total dalam Graf G Jika sebuah graf G mempunyai bilangan kromatik total ∆(G ) + 1 , maka G dikatakan Tipe 1, jika G mempunyai bilangan kromatik total ∆(G ) + 2 , maka G dikatakan Tipe 2. Beberapa kelas graf yang mempunyai tipe 1 dan tipe 2 adalah sebagai berikut [6]: 1. Graf lengkap G mempunyai χ T (G ) = ∆(G ) + 1 jika | V (G ) | gasal, dan χ T (G ) = ∆(G ) + 2 jika | V (G ) | genap. [6] mempunyai 2. Graf bipartit lengkap G = K m,n
χ T (G ) = ∆(G ) + 1 jika m ≠ n dan χ T (G ) = ∆(G ) + 2
jika
Gambar 3 Graf Petersen dan subgraf terinduksinya.
m = n . [6]
III. KOMPONEN-KOMPONEN UNTUK GRAF BEBAS UNICHORD A. Graf S t Graf S t terdiri dari graf bipartit lengkap K t −1,t , untuk
t ≥ 3 , dengan menambahkan anting sisi disetiap t simpul yang berderajat t = 3 . Gambar 5 menunjukkan graf S 3 . Gambar 4 Graf kincir W25 . B. Pewarnaan Graf Pewarnaan graf adalah sebuah fungsi yang memasangkan elemen-elemen pada graf, berupa simpul, sisi, ataupun keduanya. Pewarnaan graf terdiri dari tiga macam, yaitu: 1. Pewarnaan Simpul Pewarnaan simpul pada graf G adalah suatu fungsi c : V (G ) → N dengan V (G ) merupakan himpunan simpul dan himpunan bilangan asli N. Dengan kata lain pewarnaan simpul merupakan pemberian warna pada simpul di graf G , sehingga setiap simpul yang bersisihan diberi warna berbeda. Jumlah warna minimal yang digunakan disebut dengan bilangan kromatik, dinotasikan dengan χ (G ) .
Gambar 5 Graf S t , t = 3 Lemma 1. [4] Pertimbangkan graf S t , dengan t ≥ 3 . 1.
2.
Ada (t + 1) -pewarnaan total dari graf S t dengan setiap t simpul dalam B' = {b1 , b2 ,..., bt } memiliki warna berbeda. Dalam beberapa (t + 1) -pewarnaan total dari graf S t , setiap anting sisi memiliki warna sama.
3 B. Graf Bipartit H t Graf bipartit H t adalah dua kopi graf S t dan menyatukan t − 2 anting sisi dari kopi pertama dengan t − 2 anting sisi dari kopi kedua. Lihat Gambar 6.
Gambar 6 Graf H t , t = 3 dan skemanya. Konsekuensi Lemma 1 sebagai berikut: Lemma 2. [4] Diberikan t ≥ 3 . 1. Pertimbangkan (t + 1) -pewarnaan total parsial dari graf H t dengan empat anting sisi berwarna sama dan 2.
empat anting simpul semua tidak berwarna sama. Dalam beberapa (t + 1) -pewarnaan total dari H t , empat anting sisi memiliki warna sama.
C. Graf “Replacement” R Graf “replacement” R merupakan graf lengkap K 4 yang setiap simpulnya diganti dengan kopi graf H t dan ditambah simpul baru di setiap sisi asli K 4 . Lihat Gambar 7.
Gambar 7 Graf “replacement” R dan skemanya. Lemma 3. [4] Pertimbangkan graf replacement R . 1. Beberapa parsial 4-pewarnaan total dari graf R dengan empat anting sisi berwarna beda dan anting simpul juga berwarna beda, diperluas sampai 4pewarnaan total dari graf R . 2. Dalam setiap 4-pewarnaan total dari graf R , empat anting sisi harus berwarna beda. D. Graf “Forcer” F Graf “forcer”. Untuk integer n ≥ 2 dan k ≥ 3 dikonstruksikan graf forcer, Fn ,k , dengan 2n anting sisi dengan menggabungkan n kopi dari graf H k dalam siklus seperti pada Gambar 8.
Gambar 8 Graf “forcer” Fn, k , n = 5 . Lemma 4. [4] Pertimbangkan graf F = Fn, k , dengan n ≥ 2 dan k ≥ 3. 1. Pertimbangkan parsial (k + 1) -pewarnaan total dari F dengan setiap anting sisi berwarna sama (misalkan warna 1) dan setiap anting simpul berwarna berbeda. Maka diperluas sampai (k + 1) -pewarnaan total dari F . 2. Dalam beberapa (k + 1) -pewarnaan total dari F , setiap anting sisi memiliki warna sama. IV. BILANGAN KROMATIK TOTAL PADA GRAF BEBAS UNICHORD
A. Hasil Analisa Bilangan Kromatik Total dari Graf Bebas Unichord Dalam pembahasan ini akan dianalisa pewarnaan total yang terbatas pada graf bebas unichord adalah NP-lengkap. Dalam teori kompleksitas komputasi, kelas kompleksitas NPlengkap adalah kelas masalah keputusan. Sebuah L masalah keputusan adalah NP-lengkap jika berada dalam konfigurasi permasalahan NP (nonpolinomial), sehingga setiap solusi yang diberikan untuk masalah keputusan dapat dibuktikan dalam waktu polinomial, dan setiap masalah NP dapat diubah menjadi L dengan transformasi dalam waktu polinomial. Teorema 1 menunjukkan bahwa pewarnaan total pada graf bebas unichord adalah NP-lengkap untuk graf reguler dari kelas C dengan k ≥ 3 . Teorema 1. [4] Untuk setiap k ≥ 3 , pewarnaan total graf bipartit k -reguler adalah NP-lengkap. Bukti. Untuk pembuktian Teorema 1 akan didapat dengan mereduksi dari masalah pewarnaan sisi graf 3-reguler sampai pewarnaan total graf bipartit 3-reguler dan mereduksi dari pewarnaan total graf bipartit k -reguler sampai pewarnaan total graf bipartit k + 1 -reguler. Secara sederhana, pembuktian akan dibagi ke dalam dua bagian. Pertimbangkan kasus pertama k = 3 . Dengan graf kubik G akan ditunjukkan bagaimana mengkonstruksi graf bipartit kubik G ' dengan 4-pewarnaan total jika dan hanya jika graf G adalah 3-pewarnaan sisi. Misalkan graf G mempunyai n = 2 p simpul. Konstruksi dari graf G ' diselesaikan dengan cara berikut: 1. Konstruksi graf Eulerian G" dari graf G dengan menambahkan simpul baru v setiap simpul dalam graf G .
*
dan hubungkan
v * pada
4
v*
Gambar 9 Graf Eulerian. *
2. Uraikan simpul v ke dalam n simpul. Identifikasi sisi p diarahkan pada anting simpul dalam graf yang dihasilkan dengan p anting sisi dengan simpul akhir hitam pada graf forcer Fp ,3 , dan p sisi diarahkan langsung pada anting simpul dengan sisa p anting sisi dalam Fp ,3 .
k-reguler sampai pewarnaan total bipartit k + 1 -reguler dan melengkapi pembuktian teorema. Diberikan graf G bipartit k-reguler, dengan bipartisi ( A, B ) (dengan | A |=| B |= n ). Dikonstruksi graf G ' bipartit k + 1 -reguler sebagai berikut. Ambil graf forcer Fn , k +1 dan identifikasi n anting simpul putih dari graf forcer Fn, k +1 dengan n simpul dalam B . Terakhir identifikasi n anting simpul hitam dari graf forcer Fn, k +1 dengan n simpul dalam
A , seperti yang ditunjukkan oleh Gambar 12. Jelas, hasil graf G ' adalah bipartit dan k + 1 -reguler. Sekarang harus ditunjukkan bahwa graf G adalah ( k + 1 )-pewarnaan total jika dan hanya jika graf G ' adalah ( k + 2 )-pewarnaan total. B
Gambar 10 Uraian
A k G
v * dan menggabungkan graf forcer.
Terakhir, ganti setiap simpul v dari graf asli dengan kopi dari graf relacement R pada Gambar 7. Cara kerja di atas digambarkan dalam Gambar 11. Gambar tersebut mudah dilihat bahwa hasil graf G ' adalah kubik dan bipartit. Kemudian akan ditunjukkan bahwa graf G adalah 3-pewarnaan sisi jika dan hanya jika G ' adalah 4pewarnaan total.
Satu bagian mudah dengan bagian 2 dari Lemma 4. jika
3.
Gambar 11 Transformasi untuk k = 3 . Pertimbangkan 4-pewarnaan total untuk graf G ' . Dengan bagian 2 dari Lemma 4 n sisi yang menghubungkan graf forcer Fp ,3 pada graf G diberi warna sama. Oleh karena itu, semua harus menjamin bahwa empat anting sisi dari setiap graf replacement menerima warna berbeda; akibat dari bagian 2 Lemma 3. Oleh karena itu, graf G adalah 3-pewarnaan sisi. Sekarang pertimbangkan 3-pewarnaan sisi dari graf G adalah warna 1,2 dan 3. Hasil pewarnaan sesuai sisi pada graf G ' . Warnai sisi dengan warna 4 yaitu anting sisi pada graf forcer. Diperluas parsial pewarnaan pada setiap graf replacement R disekitarnya. Dengan bagian 1 dari Lemma 3, dapat dilakukan pewarnaan dengan cara yang sama. Terakhir, dengan bagian 1 dari Lemma 4 dapat diperluas parsial pewarnaan pada bagian graf forcer dari graf G ' . Maka dapat dihasilkan 4-pewarnaan total dari graf G ' , lengkap sudah pembuktian dari kasus k = 3 . Untuk kasus kedua diberikan k ≥ 3 . Akan ditunjukkan transformasi polinomial dari masalah pewarnaan total bipartit
G’
Gambar 12 Transformasi untuk k umum.
G ' adalah ( k + 2 )-pewarnaan total semua anting sisi dari graf forcer Fn, k +1 berwarna sama dan sisi-sisi yang melekat atau berdekatan pada setiap elemen dalam graf G . Akibatnya, G adalah ( k + 1 )-pewarnaan total. Misalkan ada ( k + 1 )-pewarnaan total dari graf G dengan warna 1,..., k + 1 . Maka dapat digunakan k + 2 warna untuk memberi warna 2n anting sisi dari graf forcer Fn, k +1 . Dengan bagian 1 dari Lemma 4 parsial pewarnaan ini dapat diperluas sampai ( k + 2 )-pewarnaan total dari graf forcer Fn , k +1 . Akibatnya, graf G ' dapat menjadi ( k + 2 )-pewarnaan total. Dari analisa di atas maka terbukti bahwa Teorema 1 Untuk setiap k ≥ 3 , pewarnaan total graf bipartit k -reguler adalah NP-lengkap.
V. BILANGAN KROMATIK TOTAL PADA GRAF KINCIR A. Graf Kincir Wnm Graf kincir Wnm adalah graf yang dibentuk dari hasil operasi korona m buah kopi graf lengkap dengan K1 . Himpunan simpul dari graf Wnm adalah V (Wnm ) = {v0 , v1 ,..., v n } dan himpunan sisi adalah E (Wnm ) = {a1 ,..., a n ,..., b1 , b2 ,..., bn } . m 1. Bilangan kromatik total pada graf kincir W2 dengan m ≥ 2. Untuk mendapatkan bilangan kromatik total dilakukan pewarnaan dengan algoritma welch-powell.
5 Bilangan
kromatik χT (W ) = ∆(G ) + 1 .
total
graf
kincir
W2m
adalah
m 2
m 2. Bilangan kromatik total pada graf kincir W3 minus chordal dengan m ≥ 2 . Graf kincir W3m adalah graf yang mempunyai chordal.
Gambar 13 Pewarnaan total pada graf kincir W2m
Untuk memenuhi graf yang bebas unichord, dilakukan penghapusan chordal atau minus chordal.
Tabel 1 Pewarnaan simpul graf kincir W2m n=2
f (v i )
m
i=0
i = 1,3,5,...,2m − 1
i = 2,4,6,...,2m
2 3 4
1 1 1
2 2 2
3 3 3
m
1
2
3
1, i = 0 f (vi ) = 2,1 ≤ i ≤ 2m − 1 3,2 ≤ i ≤ 2m
Gambar 14 Pewarnaan total pada graf kincir minus chordal W3m .
Tabel 2 Pewarnaan sisi graf kincir W2m
Tabel 4 Pewarnaan simpul graf kincir W3m minus chordal
n=2
f (ai )
f (bi )
m
i = 3,4,..., m
i = 1,2,..., m
2 3 4
i =1
3 3 3
i=2
2 2 2
4,5 4,5,6,7 4,5,6,7,8,9
n=3
1 1 1
m
3
2
i+2
1
3, i = 1 f (ai ) = 2, i = 2 i + 2,3 ≤ i ≤ m
f (v i )
m
i=0
i = 1,4,...,3m − 2
i = 2,5,...,3m − 1
i = 3,6,...,3m
2 3 4 5
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
m
1
2
3
4
f (bi ) = 1, i = 1,2,..., m
Tabel 3 Partisi graf kincir W2m minus chordal Bentuk partisi Banyak m partisi 2 5 {v0 , b1 , b2 },{v1 , v3 , a2 }, {v2 , v4 , a1},{a3},{a4 }
3 4
1, i = 0 2,1 ≤ i ≤ 3m − 2 f (v i ) = 3,2 ≤ i ≤ 3m − 1 4,3 ≤ i ≤ 3m
Tabel 5 Pewarnaan sisi graf kincir W3m minus chordal n=3
f (ai )
{v0 , b1 , b2 , b3},{v1 , v3 , v5 , a2 }, {v2 , v4 , v6 , a1},{a3},{a4 },{a5 },{a6 }
7
m
i =1
i=2
i = 3,4,5..., m
{v0 , b1 , b2 , b3 }, {v1 , v3 , v5 , a2 }, {v2 , v4 , v6 , a1}, {a3 }, {a4 }, {a5 }, {a6 }, {a7 }, {a8 }
9
2 3 4 5
3 3 3 3
2 2 2 2
4,5 4,5,6,7 4,5,6,7,8,9 4,5,6,7,8,9,10,11
6
VI. SIMPULAN
m n=3
3
2
i +1
m
i = 1,3,..,2m − 1
i=2
i = 4,6,..,2m
1. Graf bebas unichord adalah NP-lengkap dengan mempertimbangkan masalah pewarnaan total pada graf bipartit k-reguler. 2. Bilangan kromatik total graf kincir minus chordal dengan n ≥ 2 dan m ≥ 2 , adalah ∆ (G ) + 1 .
2 3 4 5
1 1 1 1
5 5 5 5
2 2 2 2
m
1
5
2
f (bi )
DAFTAR PUSTAKA
[1] Sulistyowati. 2003. “Bilangan Kromatik dan Graf Kritis”. Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jember. [2] Behzad, M. 1965. “Graphs and their chromatic numbers”. Doctoral Thesis-Michigan State University. [3] Yap, H.P. 1989. Total Colourings of Graphs. Bull. London Math. Soc. 21 159-163 [4] Machado, R.C.S. de FigueiredoFaieghi, C.M.H. 2011. “Total Chromatic Number of Unichord-free Graphs”. Discrete Applied Mathematics, Hal. 1851-1864. [5] Trotignon, N. Vuskovic, K. 2009. “A Structure Theorem for Graphs with No Cycle with a Unique Chord and Its Consequences”. Journal of Graph Theory, Hal. 31-38 [6] Yap, H.P. 1996. Total Colourings of graphs. in: Lecture Notes in Methematics, Springer-Verlag, Germany.
3, i = 1 f (a i ) = 2, i = 2 i + 1,3 ≤ i ≤ m
1,1 ≤ i ≤ 2m − 1 f (bi ) = 5, i = 2 2,4 ≤ i ≤ 2m
Tabel 6 Partisi simpul dan sisi graf kincir W3m minus chordal Bentuk partisi Banyak m partisi 2 5 {v0 , b1 , b3 }, {v1 , v4 , a2 , b4 }, {v2 , v5 , a1}, {v3 , v6 , a3 }, {a4 , b2 }
3
{v0 , b1 , b3 , b5 }, {v1 , v4 , v7 , a2 , b4 , b6 }, {v2 , v5 , v8 , a1}, {v3 , v6 , v9 , a3 }, {a4 , b2 }, {a6 }, {a7 }
7
4
{v0 , b1 , b3 , b5 , b7 }, v v v v a b b b { , , , , , , }, 1 4 7 10 , 2 4 6 8 {v2 , v5 , v8 , v11 , a1}, {v3 , v6 , v9 , v12 , a3 }, {a4 , b2 }, {a5 }{a6 }, {a7 }, {a8 }
9
Bilangan
kromatik
total
graf
kincir
W3m
adalah
χT (W ) = ∆(G ) + 1 . m 3
3. Bilangan kromatik total pada graf kincir Wnm minus chordal dengan m dan n sebarang Berdasarkan pada analisa sebelumnya untuk m secara umum, graf kincir Wnm minus chordal mempunyai bilangan kromatik total seperti dinyatakan oleh Teorema berikut; Teorema 2 Untuk G graf kincir Wnm minus chordal secara umum dengan n ≥ 2 , m ≥ 2 , maka berlaku bilangan kromatik total χ T (G ) = ∆(G ) + 1 .
