Oleh : Rindi Eka Widyasari NRP Dosen pembimbing : Dr. Darmaji, S.Si., M.T

“Study of Total Chromatic Number of Unichord-free and Windmill Graphs”

Oleh : Rindi Eka Widyasari NRP 1208100024 Dosen pembimbing : Dr. Darmaji, S.Si., M.T.

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2012

PENDAHULUAN TINJAUAN PUSTAKA METODOLOGI ANALISIS DAN PEMBAHASAN PENUTUP DAFTAR PUSTAKA

KAJIAN BILANGAN KROMATIK TOTAL PADA GRAF BEBAS UNICHORD DAN KINCIR

PENDAHULUAN Latar Belakang Rumusan Masalah Batasan Masalah

Tujuan Manfaat TINJAUAN PUSTAKA

METODOLOGI ANALISIS DAN PEMBAHASAN PENUTUP DAFTAR PUSTAKA

PENDAHULUAN

LATAR BELAKANG • PENDAHULUAN Latar Belakang

• •

Rumusan Masalah Batasan Masalah


• • •

Sebuah graf berisikan dua himpunan yaitu himpunan simpul dan himpunan sisi. Beberapa contoh graf adalah graf kincir, graf siklus, graf chordal dan graf bebas unichord. Pewarnaan graf adalah fungsi yang memasangkan elemen-elemen pada graf dengan himpunan bilangan asli yang merepresentasikan warna. Bilangan kromatik adalah jumlah warna minimal, χ(G) Bilangan kromatik total, . Tahun 1967 Behzad mangkaji bilangan kromatik total untuk graf lengkap:


•

•

Yap mengkaji bilangan kromatik total pada graf r-partit: (G) = Δ(G) + 2 Bilangan kromatik total pada graf bebas unichord dan kincir.

RUMUSAN MASALAH PENDAHULUAN

1.

Latar Belakang Rumusan Masalah

Batasan Masalah

Tujuan

2.

Bagaimana mengkaji bilangan kromatik total pada graf bebas unichord. Bagaimana mendapatkan bilangan kromatik total pada graf kincir.

Manfaat TINJAUAN PUSTAKA


BATASAN MASALAH Batasan yang akan diberikan dalam pengerjaan tugas akhir ini adalah graf bebas unichord dan kincir.

TUJUAN PENDAHULUAN Latar Belakang Rumusan Masalah Batasan Masalah

1. Mengkaji bilangan kromatik total pada graf bebas unichord. 2. Mendapatkan bilangan kromatik total pada graf kincir.



MANFAAT memberi kontribusi pada penelitian dalam bidang teori graf dan memberi informasi terutama mengenai bilangan kromatik total pada graf bebas unichord dan kincir.

PENDAHULUAN

TINJAUAN PUSTAKA Terminologi dasar graf Pengelompokan Graf Pewarnaan Graf Beragam tipe pewarnaan total pada graf


TINJAUAN PUSTAKA

Terminologi Dasar Graf

PENDAHULUAN

TINJAUAN PUSTAKA

Graf G digambarkan dalam bentuk diagram (gambar), misal graf G dengan 4 simpul dan 5 sisi. Graf H dengan 4 simpul dan 8 sisi sebagai berikut: Graf G

Graf H

Terminologi dasar graf Pengelompokan Graf Pewarnaan Graf Beragam tipe pewarnaan total pada graf


Graf yang tidak memiliki sisi-rangkap dan tidak memiliki loop disebut graf sederhana. Loop adalah sisi yang menhubungkan sebuah simpul dengan dirinya sendiri

Terminologi Dasar Graf (lanjutan) PENDAHULUAN

TINJAUAN PUSTAKA Terminologi dasar graf Pengelompokan Graf

• Derajat adalah jumlah sisi yang menempel pada simpul v dan dinotasikan deg (v). • Derajat minimal dilambangkan • Derajat maksimal dinotasikan Δ(G). • Graf G yang setiap simpulnya mempunyai derajat sama maka graf G disebut graf reguler.

Pewarnaan Graf Beragam tipe pewarnaan total pada graf


Contoh Graf reguler berderajat 3

Terminologi Dasar Graf (lanjutan) PENDAHULUAN

TINJAUAN PUSTAKA Terminologi dasar graf Pengelompokan Graf Pewarnaan Graf Beragam tipe pewarnaan total pada graf

• Jalan (walk) pada graf G dinotasikan W(G) adalah

barisan yang elemen-elemennya bergantian antara simpul dan sisi yang di awali dan diakhiri oleh simpul. • Jejak (trail) : suatu jalan yang sisinya tidak berulang.

• Lintasan (path) : suatu jalan yang simpulnya tidak berulang. • Siklus (cycle) : Sebuah jalan tertutup tanpa pengulangan simpul kecuali simpul awal dan simpul akhir.


Contoh

Pengelompokan graf •

PENDAHULUAN

TINJAUAN PUSTAKA Terminologi dasar graf Pengelompokan graf

•

• •

Graf siklus adalah beberapa simpul yang terhubung dalam rantai tertutup. Graf chordal jika setiap siklus dengan simpul empat atau lebih memiliki sebuah chord, yaitu sisi yang menghubungkan dua simpul dalam siklus yang tidak bersisihan. Graf bebas unichord adalah graf yang tidak memiliki sebuah chord unik. Graf kincir adalah graf yang dibentuk dari hasil operasi korona m buah kopi graf lengkap dengan .

Pewarnaan Graf Beragam tipe pewarnaan total pada graf


Contoh graf siklus, graf chordal, graf kincir, dan graf petersen beserta subgraf terinduksinya.

PEWARNAAN GRAF PENDAHULUAN

TINJAUAN PUSTAKA Terminologi dasar graf Pengelompokan Graf Pewarnaan graf

Beragam tipe pewarnaan total pada graf


Pewarnaan simpul Pewarnaan simpul pada graf G adalah suatu fungsi dengan V(G) merupakan himpunan simpul dan himpunan bilangan asli N sedemikian hingga jika maka . Dengan kata lain pewarnaan simpul merupakan pemberian warna pada simpul di graf G, sehingga setiap simpul yang bersisihan diberi warna berbeda.

PEWARNAAN GRAF (lanjutan)

PENDAHULUAN

TINJAUAN PUSTAKA Terminologi dasar graf Pengelompokan Graf Pewarnaan graf



Algoritma Welch-Powell adalah sebagai berikut : 1. Labeli simpul pada graf G dengan 1, 2, …, sehingga deg ( 1) ≥ deg ( 2) ≥ ... ≥ deg ( ); 2. Warnai simpul 1 dengan warna 1; 3. Warnai setiap simpul yang tidak bersisihan dengan 1 dengan warna 1; 4. Misalkan i adalah bilangan asli terkecil sedemikian hingga simpul i belum diwarnai, gunakan warna 2 untuk mewarnai . Warnai setiap simpul yang tidak bersisihan dengan i dengan warna 2, lanjutkan sampai semua simpul terwarnai dan simpul yang bersisihan mendapatkan warna yang berbeda; 5. Jika semua simpul telah terwarnai maka proses mewarnai berhenti; 6. Jika belum ulangi langkah 4).

PEWARNAAN GRAF (lanjutan) Pewarnaan sisi PENDAHULUAN


Pewarnaan sisi pada graf G adalah suatu fungsi dengan E(G) merupakan himpunan sisi dan himpunan bilangan asli N sedemikian hingga jika adalah dua sisi yang bersisihan maka . Dengan kata lain pewarnaan sisi pada graf G sehingga sisi yang bersisihan memperoleh warna yang berbeda.

Pewarnaan graf



Pewarnaan total Pewarnaan total adalah sebuah fungsi . 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.


PENDAHULUAN


Jika sebuah graf mempunyai bilangan kromatik total , maka dikatakan Tipe 1, jika mempunyai bilangan kromatik total , maka dikatakan Tipe 2. Beberapa kelas graf yang mempunyai tipe 1 dan tipe 2 adalah sebagai berikut [6]:

Pewarnaan graf



1. Graf lengkap G mempunyai jika gasal, dan jika genap. [6] 2. Graf bipartit lengkap mempunyai jika dan jika . [6]

PENDAHULUAN TINJAUAN PUSTAKA METODOLOGI Diagram Alir

ANALISIS DAN PEMBAHASAN PENUTUP DAFTAR PUSTAKA

METODOLOGI PENELITIAN

DIAGRAM ALIR METODOLOGI PENELITIAN PENDAHULUAN TINJAUAN PUSTAKA

Mengidentifikasi graf

Menganalisa pewarnaan total pada graf

Simpulan dan saran

Membuktikan warna minimal pada graf

METODOLOGI Diagram Alir

ANALISIS DAN PEMBAHASAN PENUTUP DAFTAR PUSTAKA

PENDAHULUAN TINJAUAN PUSTAKA

METODOLOGI ANALISIS DAN PEMBAHASAN Graf Bebas Unichord Contoh Pewarnaan Total Graf Bebas Unichord Komponenkomponen untuk Graf Bebas Unichord Hasil analisa Bilangan Kromatik Total Dari Graf Bebas Unichord Graf Kincir

PENUTUP DAFTAR PUSTAKA

ANALISIS DAN PEMBAHASAN

Graf Bebas Unichord PENDAHULUAN TINJAUAN PUSTAKA



Graf bebas unichord adalah graf yang tidak memiliki sebuah chord unik. Dalam [7], graf bebas unichord dikelompokkan dalam kelas C . Pada paper yang sama, dinyatakan bahwa sebarang graf terhubung dalam 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 salah satu partisinya hanya memuat simpul berderajat dua, dan subgraf terinduksi dari graf Heawood atau graf Petresen. Graf G dikatakan dapat didekomposisi ke dalam subgraf H1,H2, ..., Ht jika sebarang subgraf Hi dan Hj tidak memiliki sisi yang sama, dan union dari semua subgraf Hi adalah G .

Contoh Pewarnaan Total Graf Bebas Unichord




Subgraf terinduksi graf Petersen membutuhkan 4 warna, sehingga didapat pewarnaan total adalah 4 atau . Pewarnaan total subgraf terinduksi dengan penghapusan satu simpul juga membutuhkan 4 warna atau

Contoh Pewarnaan Total Graf Bebas Unichord (lanjutan)


METODOLOGI

Subgraf terinduksi dari graf Heawood dengan penghapusan satu sampai tujuh simpul membutuhkan 5 warna atau , namun pada penghapusan delapan simpul hanya membutuhkan 4 warna atau karena subgraf terinduksi tersebut merupakan path (lintasan).

ANALISIS DAN PEMBAHASAN Graf Bebas Unichord Contoh Pewarnaan Total Graf Bebas Unichord Komponenkomponen untuk Graf Bebas Unichord Hasil analisa Bilangan Kromatik Total Dari Graf Bebas Unichord Graf Kincir


Graf Heawood

Contoh Pewarnaan Total Graf Bebas Unichord (lanjutan)




Pewarnaan total pada graf bipartit dengan satu sisi hanya memuat simpul berderajat dua, yaitu membutuhkan 4 warna atau , untuk graf bipatit membutuhkan 4 warna atau dan membutuhkan 5 warna atau

Komponen-komponen untuk graf bebas unichord Graf PENDAHULUAN

terdiri dari graf bipartit lengkap , untuk , dengan menambahkan anting sisi disetiap t simpul yang berderajat t-1.

TINJAUAN PUSTAKA



Lemma 1. [4] Pertimbangkan graf , dengan . 1. Ada (t+1)-pewarnaan total dari graf dengan setiap t simpul dalam memiliki warna berbeda. 2. Dalam beberapa (t+1)-pewarnaan total dari graf , setiap anting sisi memiliki warna sama.

Komponen-komponen untuk graf bebas unichord (lanjutan)

PENDAHULUAN

Selanjutnya konstruksi graf bipartit dengan meletakkan dua kopi graf dan menyatukan t-2 anting sisi dari kopi pertama dengan t-2 anting sisi dari kopi kedua.

TINJAUAN PUSTAKA

METODOLOGI ANALISIS DAN PEMBAHASAN

Graf

dan skemanya

Graf Bebas Unichord Contoh Pewarnaan Total Graf Bebas Unichord Komponenkomponen untuk Graf Bebas Unichord Hasil analisa Bilangan Kromatik Total Dari Graf Bebas Unichord Graf Kincir


Konsekuensi Lemma 1 sebagai berikut: Lemma 2. [4] Diberikan . 1. Pertimbangkan (t+1)-pewarnaan total parsial dari graf dengan empat anting sisi berwarna sama dan empat anting simpul semua tidak berwarna sama. 2. Dalam beberapa (t+1)-pewarnaan total dari , empat anting sisi memiliki warna sama.

Komponen-komponen untuk graf bebas unichord (lanjutan) Komponen selanjutnya yang digunakan adalah graf “replacement” R. Sehingga diperoleh hasil sebagai berikut: PENDAHULUAN TINJAUAN PUSTAKA

METODOLOGI

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.

Komponen-komponen untuk graf bebas unichord (lanjutan)

PENDAHULUAN

Terakhir, didefinisikan graf “forcer”. Untuk integer dan dikonstruksikan graf forcer, , dengan 2n anting sisi dengan menggabungkan n kopi dari graf dalam siklus.

TINJAUAN PUSTAKA

METODOLOGI

Graf “forcer”

n=5



Lemma 4. [4] Pertimbangkan graf , dengan dan . 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.

Hasil Analisa Bilangan Kromatik Total Dari Graf Bebas Unichord


Dalam pembahasan ini akan dianalisa pewarnaan total yang terbatas pada graf bebas unichord dengan menggunakan komponen-komponen yang telah dibahas. Teorema 1 menunjukkan bahwa pewarnaan total adalah NP-lengkap untuk graf reguler dari kelas dengan



Teorema 1. [5] Untuk setiap , pewarnaan total graf bipartit k-reguler adalah NP-lengkap. 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. Kemudian untuk mengkonstruksi pembuktian tersebut, maka digunakan komponen-komponen sebagai berikut:





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=2p simpul. Konstruksi dari graf G’ diselesaikan dengan cara berikut: 1. Konstruksi graf Eulerian G” dari graf G dengan menambahkan simpul baru dan hubungkan pada setiap simpul dalam graf G. Graf eulerian





2. Uraikan simpul 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 , dan p sisi diarahkan langsung pada anting simpul dengan sisa p anting sisi dalam .





3. Terakhir, ganti setiap simpul dari graf asli dengan kopi dari graf relacement R.



Untuk . Akan ditunjukkan transformasi polinomial dari masalah pewarnaan total bipartit k-reguler sampai pewarnaan total bipartit (k+1)-reguler dan melengkapi pembuktian teorema.



Transformasi untuk k umum maka terbukti bahwa Teorema 1 Untuk setiap , pewarnaan total graf bipartit k-reguler adalah NP-lengkap.

Graf Kincir




Bilangan kromatik total graf kincir

dengan

Graf Kincir

PENDAHULUAN

(lanjutan)


dengan

TINJAUAN PUSTAKA



2 3 4

1 1 1

2 2 2

3 3 3

1

2

3

Graf Kincir

PENDAHULUAN

(lanjutan)


dengan

TINJAUAN PUSTAKA



2 3 4

3 3 3

2 2 2

3

2

4,5 4,5,6,7 4,5,6,7,8,9

1 1 1

1

Graf Kincir

PENDAHULUAN

(lanjutan)


dengan

TINJAUAN PUSTAKA



Bilangan kromatik total graf kincir adalah

.

Graf Kincir




(lanjutan)


minus chordal dengan

Graf Kincir

(lanjutan)

Bilangan kromatik total graf kincir PENDAHULUAN TINJAUAN PUSTAKA




Graf Kincir

(lanjutan)


METODOLOGI ANALISIS DAN PEMBAHASAN

2 3 4 5

4,5 4,5,6,7 4,5,6,7,8,9 4,5,6,7,8,9,10 ,11

3 3 3 3

2 2 2 2

3

2

1 1 1 1

5 5 5 5

2 2 2 2

1

5

2

Graf Bebas Unichord Contoh Pewarnaan Total Graf Bebas Unichord Komponenkomponen untuk Graf Bebas Unichord Hasil analisa Bilangan Kromatik Total Dari Graf Bebas Unichord Graf Kincir

PENUTUP

2 3 4 5

DAFTAR PUSTAKA


Graf Kincir

(lanjutan)





Graf Kincir

(lanjutan)





Graf Kincir

(lanjutan)





Graf Kincir

(lanjutan)






Bilangan kromatik total graf kincir adalah

Graf Kincir

PENDAHULUAN

(lanjutan)

Bilangan kromatik total graf kincir sebarang


TINJAUAN PUSTAKA



Berdasarkan pada analisa sebelumnya untuk m secara umum, graf kincir minus chordal mempunyai bilangan kromatik total seperti dinyatakan oleh Teorema berikut; Teorema 2 Untuk graf kincir secara umum dengan , berlaku bilangan kromatik total

minus chordal , maka .

PENDAHULUAN TINJAUAN PUSTAKA METODOLOGI ANALISIS DAN PEMBAHASAN PENUTUP Kesimpulan Saran DAFTAR PUSTAKA

PENUTUP

Kesimpulan PENDAHULUAN TINJAUAN PUSTAKA METODOLOGI ANALISIS DAN PEMBAHASAN PENUTUP Kesimpulan Saran

DAFTAR PUSTAKA

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 dan , adalah .

Saran PENDAHULUAN TINJAUAN PUSTAKA METODOLOGI ANALISIS DAN PEMBAHASAN PENUTUP Kesimpulan

Saran DAFTAR PUSTAKA

1. Bilangan kromatik total pada graf bebas unichord selain dengan mempertimbangkan graf bipartit k-reguler, juga dapat dilakukan dengan mempertimbangkan graf seri-paralel, graf planar, dan graf terhubung. 2. Bilangan kromatik total graf minus chordal ini masih ada kemungkinan untuk bisa dikembangkan lagi, baik dengan memodifikasi daun kincir yang lainnya, misal dengan penambahan anting-anting simpul atau antinganting sisi.

DAFTAR PUSTAKA

PENDAHULUAN TINJAUAN PUSTAKA METODOLOGI ANALISIS DAN PEMBAHASAN PENUTUP 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] Chartrand, G. Zhang, P. 2009. ”Chromatic Graf Theory“. New York : Taylor & Francis Group. [7] Yap, H. P. 1996. “Total Colourings of graphs”. in: Lecture Notes in Methematics, Springer-Verlag, Germany.

Oleh : Rindi Eka Widyasari NRP Dosen pembimbing : Dr. Darmaji, S.Si., M.T

Recommend Documents