pewarnaan graf

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell

Permasalahan 4 warna

TEORI GRAFPEWARNAAN GRAF

Rukmono Budi Utomo30115301

March 9, 2016

Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Graf

1 Pewarnaan Titik(simpul)

2 2. Algotitma Welch-Powell

3 Permasalahan 4 warna

Definisi 1Pewarnaan Titik

Misalkan G graf tanpa lup dan sisi ganda dan memiliki k titik.Pewarnaan titik pada graf G adalah memberikan warna berbedakepada titik-titik di graf G tersebut dengan tujuan setiap dua titikyang bertetangga memiliki warna yang berbeda.

Secara mudah, graf G dengan k titik dapat diwarnai sajadengan k warna yang berbeda

Figure: Graf G dengan 4 titik di atas diwarnai dengan 4 warna berbeda

lanjutan

Persoalannya adalah berapa banyak warna minimal yangdiperlukan untuk mewarnai sebuah graf sederhana?

Figure: Graf G 4 titik seperti contoh di awal dapat diwarnai denganhanya 2 warna berbeda saja

lanjutan

Persoalannya adalah berapa banyak warna minimal yangdiperlukan untuk mewarnai sebuah graf sederhana?

Figure: Graf G 4 titik seperti contoh di awal dapat diwarnai denganhanya 2 warna berbeda saja

Bilangan Kromatik

Jumlah warna minimum yang digunakan untuk mewarnai titik-titikpada suatu graf G disebut bilangan kromatik dari graf G dandinotasikan dengan (G )

Contoh 1

Figure: Bilangan kromatik graf G di atas (G ) = 2

Bilangan Kromatik

Jumlah warna minimum yang digunakan untuk mewarnai titik-titikpada suatu graf G disebut bilangan kromatik dari graf G dandinotasikan dengan (G )

Contoh 1

Contoh 2

Teorema1

Jika ada sebuah pewarnaan k pada graf G , maka (G ) k

Bukti

Jika terdapat pewarnaan k pada graf G , maka semua titikpada graf G tersebut dapat diwarnai dengan k warna

Karena bilangan kromatik merupakan minimum banyaknyawarna yang digunakan untuk mewarnai semua titik pada grafG , sedemikian sehingga syarat pewarnaan titik terpenuhi,maka terbukti (G ) k

Teorema1

Bukti

Teorema1

Bukti

Contoh 3

Figure: Bilangan kromatik graf G , (G ) = 3 < 7 = k

Contoh 4

Figure: Bilangan kromatik graf G , (G ) = k = 3

Contoh 3

Contoh 4

Figure: Bilangan kromatik graf G , (G ) = k = 3

Contoh 3

Contoh 4

Figure: Bilangan kromatik graf G , (G ) = k = 3Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Teorema 2

Jika H merupakan graf bagian dari graf G , maka (H) (G )

Bukti

Misalkan H merupakn graf bagian dari graf G , makaV (H) V (G ) dan E (H) E (G )Karena setiap pewarnaan titik di graf H dapat diperluas kesebuah pewarnaan titik di graf G, maka (H) (G )

Contoh 5

Figure: Graf H adalah graf bagian dari graf G dengan(H) = 2 (G ) = 3

Teorema 2

Bukti

Misalkan H merupakn graf bagian dari graf G , makaV (H) V (G ) dan E (H) E (G )

Karena setiap pewarnaan titik di graf H dapat diperluas kesebuah pewarnaan titik di graf G, maka (H) (G )

Contoh 5

Teorema 2

Bukti

Contoh 5

Teorema 2

Bukti

Contoh 5

Contoh 6

Figure: Graf H adalah graf bagian dari graf G dengan (H) = (G ) = 2

Teorema 3

Jika G1,G2, ...,Gk adalah komponen-komponen graf G , maka

(G ) = max { (Gi ) |1 i k }

Bukti

Misalkan Gi untuk suatu 1 i k ditulis denganG1,G2, ...,Gk adalah komponen-komponen graf G yangmemiliki bilangan kromatik maksimum, katakan t

Berdasarkan hal tersebut t warna yang digunakan untukmewarnai semua titik di Gi , dapat digunakan untuk mewarnaisemua titik di G pada komponen selain Gi , dengan demikiandiperoleh sebuah pewarnaan t pada G

karena (G ) t, dan karena Gi adalah graf bagian dari Gserta (Gi ) = t, maka (G ) (Gi ) = tDengan mengingat bahwa (G ) t, maka (G ) = t

Teorema 3

(G ) = max { (Gi ) |1 i k }

Bukti

Teorema 3

(G ) = max { (Gi ) |1 i k }

Bukti

Teorema 3

(G ) = max { (Gi ) |1 i k }

Bukti

karena (G ) t, dan karena Gi adalah graf bagian dari Gserta (Gi ) = t, maka (G ) (Gi ) = t

Dengan mengingat bahwa (G ) t, maka (G ) = t

Teorema 3

(G ) = max { (Gi ) |1 i k }

Bukti

Contoh 7

Figure: Graf G dengan komponen-komponennya G1,G2 dan G3

Teorema 4

Jika G adalah graf komplit dengan n titik, maka (G ) = n

BuktiKarena pada graf komplit setiap dua titik berhubungan langsung,sesuai dengan definisi pewarnaan titik maka semua titik harusdiwarnai dengan warna yang berbeda.contoh 8

Figure: Graf komplit G dengan 4 titik memiliki bilangan kromatik(G ) = 4

Teorema 4

BuktiKarena pada graf komplit setiap dua titik berhubungan langsung,sesuai dengan definisi pewarnaan titik maka semua titik harusdiwarnai dengan warna yang berbeda.

contoh 8

Teorema 4

BuktiKarena pada graf komplit setiap dua titik berhubungan langsung,sesuai dengan definisi pewarnaan titik maka semua titik harusdiwarnai dengan warna yang berbeda.contoh 8

Teorema 5

Jika G adalah graf kosong, maka (G ) = 1

BuktiKarena graf kosong hanya terdiri dari titik-titik dan tidak ada sisiyang menghubungkan dua titik, dengan demikian setiap titik dapatmemiliki warna yang sama.Contoh9

Figure: Graf kosong G memiliki bilangan kromatik (G ) = 1

Teorema 5

BuktiKarena graf kosong hanya terdiri dari titik-titik dan tidak ada sisiyang menghubungkan dua titik, dengan demikian setiap titik dapatmemiliki warna yang sama.

Contoh9

Teorema 5

BuktiKarena graf kosong hanya terdiri dari titik-titik dan tidak ada sisiyang menghubungkan dua titik, dengan demikian setiap titik dapatmemiliki warna yang sama.Contoh9

Teorema 6

Diberikan graf tak kosong G . Graf G bipartisi jika dan hanya jika(G ) = 2

Bukti Jika G graf bipartisi, maka (G ) = 2

karena G graf bipartisi maka G dapat dibagi menjadi duahimpunan, katakan X dan Y

Gunakan warna 1 untuk mewarnai semua titik di X . Hal inidiperbolehkan karena tiap titik di X tidak saling berhubungan.

Dengan alasan yang sama, kita dapat mewarnai semua titik diY dengan warna 2

Dengan demikian hanya dibutuhkan 2 warna untuk mewarnaigraf bipartit tersebut G, sehingga terbukti (G ) = 2

Teorema 6

Contoh 10

Figure: Graf bipartisi G memiliki bilangan kromatik (G ) = 2

Bukti Jika graf G memiliki bilangan kromatik (G ) = 2 maka graftersebut adalah bipartisi

Misalkan semua titik yang diwarnai dengan warna 1 diletakkandalam himpunan X dan semua titik yang diwarnai denganwarna 2 diletakkan dalam himpunan Y .

Hal ini menandakan titik-titik yang terletak dalam himpunanX tidak mungkin saling berhubungan (karena memiliki warnasama), begitu juga untuk titik- titik yang terletak dalamhimpunan Y

Titik-titik yang terletak dalam himpunan X dan titik-titikyang teletak dalam himpunan Y pastilah berhubungan agarterbentuk suatu graf, dengan demikian graf yang terbentukadalah bipartisi.

Contoh 11

Figure: Suatu graf dengan bilangan kromatik (G ) = 2 dan graf tersebutbipartisi

Teorema 7

Jika Cn adalah sikel dengan n titik, maka

(Cn) =

{2, n = genap3, n = ganjil

Bukti

Misalkan Cn adalah sikel dengan n titik, maka panjang sikelCn adalah n.

Jika n genap, maka Cn adalah graf bipartisi. Berdasarkanteorema 6 bilangan kromatik Cn adalah 2.

Jika n ganjil maka Cn bukan graf bipartisi, dengan demikianCn bukan graph kosong dan (Cn) 3misalkan titik-titik dari graf Cn dituliskan sebagai v1, v2, ..., vn

Teorema 7

(Cn) =

Bukti

Teorema 7

(Cn) =

Bukti

Teorema 7

(Cn) =

Bukti

Jika n ganjil maka Cn bukan graf bipartisi, dengan demikianCn bukan graph kosong dan (Cn) 3

misalkan titik-titik dari graf Cn dituliskan sebagai v1, v2, ..., vn

Teorema 7

(Cn) =

Bukti

lanjutan

Untuk n ganjil dan 1 i n 2, warnai titik vi denganwarna 1.

Untuk n genap dan 1 i n 1, warnai titik vi denganwarna 2, dan terakhir warnai titik vn dengan warna 3.

Dengan demikian diperoleh sebuah pewarnaan 3 pada graf Cn,sehingga berdasarkan definisi bilangan kromatik, (Cn) 3Karena (Cn) 3 dan(Cn) 3, maka (Cn) = 3Dengan demikian untuk Cn adalah sikel dengan n titik makauntuk n genap (Cn) = 2 dan untuk n ganjil , (Cn) = 3

Terbukti

lanjutan

Terbukti

lanjutan

Dengan demikian diperoleh sebuah pewarnaan 3 pada graf Cn,sehingga berdasarkan definisi bilangan kromatik, (Cn) 3

Karena (Cn) 3 dan(Cn) 3, maka (Cn) = 3Dengan demikian untuk Cn adalah sikel dengan n titik makauntuk n genap (Cn) = 2 dan untuk n ganjil , (Cn) = 3

Terbukti

lanjutan

Dengan demikian diperoleh sebuah pewarnaan 3 pada graf Cn,sehingga berdasarkan definisi bilangan kromatik, (Cn) 3Karena (Cn) 3 dan(Cn) 3, maka (Cn) = 3

Dengan demikian untuk Cn adalah sikel dengan n titik makauntuk n genap (Cn) = 2 dan untuk n ganjil , (Cn) = 3

Terbukti

lanjutan

Terbukti

Contoh 12

Figure: graf C6 memiliki (C6) = 2 dan graf C5 memiliki (C5) = 3

Teorema 8

Jika G graf sederhana dengan derajat maksimum (G ), maka(G ) (G ) + 1

Bukti Bukti akan dilakukan dengan Induksi

Misalkan G graph sederhana dengan n titik, maka |V (G )| = nUntuk |V (G )| = 1 maka G = K1 atau graf kosong, sehingga(G ) = 1 dan (G ) = 0. Akibatnya(G ) = 1 0 + 1 = (G ) + 1. Dengan demikian pernyataanbenar untuk n = 1

Diasumsikan pernyataan benar untuk graf G dengan|V (G )| = n 1, untuk n > 1 dan misalkan dalampembahasan ini G graf sederhana dengan |V (G )| = nPandang sebarang titik v di G dan hapus titik v tersebutsehingga terbentuk graph baru yakni Gv dengan n 1 titik.

Teorema 8

Misalkan G graph sederhana dengan n titik, maka |V (G )| = n

Untuk |V (G )| = 1 maka G = K1 atau graf kosong, sehingga(G ) = 1 dan (G ) = 0. Akibatnya(G ) = 1 0 + 1 = (G ) + 1. Dengan demikian pernyataanbenar untuk n = 1

Teorema 8

Diasumsikan pernyataan benar untuk graf G dengan|V (G )| = n 1, untuk n > 1 dan misalkan dalampembahasan ini G graf sederhana dengan |V (G )| = n

Pandang sebarang titik v di G dan hapus titik v tersebutsehingga terbentuk graph baru yakni Gv dengan n 1 titik.

Teorema 8

lanjutan

Berdasarkan asumsi, diperoleh (G v) (G v) + 1yang memberi arti bahwa semua titik di graph G v dapatdiwarnai dengan (G v) + 1 warna.

Karena titik v dihapus pada graf G maka(G v) (G )Dari (G v) (G )) terdapat 2 kasus,yaitu :

1 (G v) = (G )Karena (G v) (G ) + 1 , menandakan semua titik diG v dapat diwarnai dengan (G ) + 1 warna sedemikianhingga syarat pewarnaan terpenuhi

Karena banyaknya warna yang diperlukan untuk mewarnaiNG(v di G v sebanyak banyaknya (G ), padahalpewarnaan (G ) + 1 di graf G v , maka terdapat palingsedikit satu warna di G v yang tidak muncul pada NG(v diG , sehingga warna tersebut dapat digunakan untuk mewarnaititik v di G . diperoleh pewarnaan(G ) + 1 pada graf G .

lanjutan

Berdasarkan asumsi, diperoleh (G v) (G v) + 1yang memberi arti bahwa semua titik di graph G v dapatdiwarnai dengan (G v) + 1 warna.Karena titik v dihapus pada graf G maka(G v) (G )

Dari (G v) (G )) terdapat 2 kasus,yaitu :1 (G v) = (G )

Karena (G v) (G ) + 1 , menandakan semua titik diG v dapat diwarnai dengan (G ) + 1 warna sedemikianhingga syarat pewarnaan terpenuhi

lanjutan

Dari (G v) (G )) terdapat 2 kasus,yaitu :

1 (G v) = (G )Karena (G v) (G ) + 1 , menandakan semua titik diG v dapat diwarnai dengan (G ) + 1 warna sedemikianhingga syarat pewarnaan terpenuhi

lanjutan

Akibatnya, berdasarkan definisi bilangan kromatik diperoleh(G ) (G ) + 1

1 (G v) < (G )

Berdasarkan asumsi diperoleh (G v) (G v) + 1

Karena (G v) (G ) + 1 dan (G v) < (G ), maka(G v) < (G ) + 1 atau (G v) (G ) + 1 (karenabilangan kromatik dari graph G v adalah bilangan bulat).Artinya ada pewarnaan (G ) pada graph G vWarnai titik v di G dengan warna (warna baru) selain warnayang muncul di graf G v sehingga diperoleh pewarnaan(G ) + 1 pada graf G .

Dari kasus 1 dan kasus 2 , maka diperoleh (G v) (G ) + 1

lanjutan

1 (G v) < (G )

Berdasarkan asumsi diperoleh (G v) (G v) + 1Karena (G v) (G ) + 1 dan (G v) < (G ), maka(G v) < (G ) + 1 atau (G v) (G ) + 1 (karenabilangan kromatik dari graph G v adalah bilangan bulat).Artinya ada pewarnaan (G ) pada graph G v

Warnai titik v di G dengan warna (warna baru) selain warnayang muncul di graf G v sehingga diperoleh pewarnaan(G ) + 1 pada graf G .

lanjutan

1 (G v) < (G )

Berdasarkan asumsi diperoleh (G v) (G v) + 1Karena (G v) (G ) + 1 dan (G v) < (G ), maka(G v) < (G ) + 1 atau (G v) (G ) + 1 (karenabilangan kromatik dari graph G v adalah bilangan bulat).Artinya ada pewarnaan (G ) pada graph G vWarnai titik v di G dengan warna (warna baru) selain warnayang muncul di graf G v sehingga diperoleh pewarnaan(G ) + 1 pada graf G .

lanjutan

1 (G v) < (G )

Berdasarkan asumsi diperoleh (G v) (G v) + 1Karena (G v) (G ) + 1 dan (G v) < (G ), maka(G v) < (G ) + 1 atau (G v) (G ) + 1 (karenabilangan kromatik dari graph G v adalah bilangan bulat).Artinya ada pewarnaan (G ) pada graph G vWarnai titik v di G dengan warna (warna baru) selain warnayang muncul di graf G v sehingga diperoleh pewarnaan(G ) + 1 pada graf G .

Algoritma Welch Powell

Pewarnaan Titik pada suatu graf sederhana G dapat dilakukandengan menggunakan algoritma Welch-Powell

Algoritma Welch-Powell

Urutkan titik-titik dari G dalam derajat menurund(v1) > d(v2) > ... > d(vn). Pengurutan derajat titik dapatmenggunakan bantuan tabel

Gunakan warna 1 untuk mewarnai titik pertama (yangmemiliki derajat tertinggi (v1) )dan titik yang tidakbertetangga dengan v1

Gunakan warna kedua untuk mewarnai titik dengan derajattertinggi berikutnya

U langi penambahan warna-warna sampai semua titikterwarnai

Contoh 13Berikan warna seminimal mungkin pada graf dibawah inisedemikian hingga setiap dua titik yang bertetangga berbeda warna

solusiKita dapat mewarnai titik-titik pada graf tersebut denganmenggunakan algoritma Welch-Powell

Urutkan titik-titik pada graf G dari derajat yang paling tinggi.Pengurutan derajat titik disajikan pada tabel di bawah ini:

Titik v1 v3 v5 v7 v2 v4 v6Derajat 5 4 4 4 3 3 3warna a b b c c a d

Dari tabel diperoleh v1 mempunyai derajat tertinggi yaitu 5,warnai titik v1 dengan warna a dan warnai titik lain (yaitutitik v4) yang tidak berhubungan langsung dengan titik v1dengan warna a.

lanjutan

Lanjutkan mewarnai titik yang mempunyai derajat tertinggiberikutnya yaitu titik v3 (dengan derajat 4) dengan warna b,dan cari titik lain yang tidak berhubungan langsung dengantitik v3 yaitu titik v5, kemudian warnai titik v5 dengan warnayang sama dengan titik v3 yaitu warna b.

Lanjutkan mewarnai titik yang mempunyai derajat tertinggiberikutnya yaitu titik v7 (dengan derajat 4) dengan warna c ,dan cari titik lain yang tidak berhubungan langsung dengantitik v7 yaitu titik v2, kemudian warnai titik v2 dengan warnayang sama dengan titik v7 yaitu warna c .

warnai titik terakhir yang belum terwarnai yaitu titik v6dengan warna d .

lanjutan

lanjutanDengan demikian, hasil pewarnaan graf G dalam contoh ini adalahsebagai berikut:

Figure: Graf G dalam contoh ini terwarnai dalam 4 warna

Contoh 14Diberikan graf sederhana G di bawah ini

Figure: Graf G dalam contoh ini terwarnai dalam 3 warna

lanjutanPewarnaan graf sederhana G pada contoh 14 adalah sbb

Figure: Bilangan Kromatik dari Graf G dalam contoh ini adalah (G ) = 3

Pada akhir abad kesembilan belas, seorang kepala sekolahmemberikan soal yang sangat menantang kepada murid-muridnya.Soal itu sebagai berikut:Tunjukkan bahwa semua peta hanya memerlukan empat warna,sehingga negara-negara atau propinsi-propinsi yang bertetanggamendapat warna yang berbeda

Kepala sekolah tersebut mengatakan hanya mau menerimapembuktian tidak lebih dari 30 baris tulisan dan satu halamandiagram.

Tampaknya soal ini sederhana sekali, tetapi sebenarnya tidakdemikian. Soal ini menjadi masalah besar di duniamatematika, yang kemudian terkenal dengan nama KonjekturEmpat Warna.

lanjutan

Baru pada Tahun 1976 ditemukan penyelesaian masalah ini.Pada tahun tersebut Kenneth Appel dan Wolfgang Haken,dua matematikawan dari Universitas Illionis di AmerikaSerikat, dapat membuktikan (dengan bantuan komputer)dugaan empat warna dengan menyita waktu sekitar 1.200 jamkomputer untuk menghasilkan beratus-ratus halaman kertashasil analisis menyeluruh terhadap sekitar 2.000 graph denganjutaan kemungkinan bentuknya.

Salah satu cara yang digunakan adalah menggunakan graphyang titiknya menunjukkan propinsi dan garis menunjukkanhubungan dua propinsi itu sebagai tetangga.

lanjutan

Baru pada Tahun 1976 ditemukan penyelesaian masalah ini.Pada tahun tersebut Kenneth Appel dan Wolfgang Haken,dua matematikawan dari Universitas Illionis di AmerikaSerikat, dapat membuktikan (dengan bantuan komputer)dugaan empat warna dengan menyita waktu sekitar 1.200 jamkomputer untuk menghasilkan beratus-ratus halaman kertashasil analisis menyeluruh terhadap sekitar 2.000 graph denganjutaan kemungkinan bentuknya.

Salah satu cara yang digunakan adalah menggunakan graphyang titiknya menunjukkan propinsi dan garis menunjukkanhubungan dua propinsi itu sebagai tetangga.

Teorema 9

Graf Planar G dapat terwarnai dengan 4 warna

Bukti Sederhana

Menurut De Morgan tidak ada lebih dari 4 wilayah padasebuah bidang dapat saling kontak satu sama lain

Peta yang terdiri dari tiga wilayah adalah sebuah segitiga danbila ditambahkan satu wilayah lagi maka hal tersebut akanditunjukkan oleh sebuh titik lagi

Titik ini harus diletakan di dalam segitiga agar menunjukkansetiap wilayah saling berdampingan(adjoint)

Teorema 9

Bukti Sederhana

Teorema 9

Bukti Sederhana

lanjutan Hasil penggambaran kondisi ini adalah graf planardibawah ini:

Figure: Graf Planar dengan V = 4 dan E = 6

Bila titik kelima ditambahkan, maka titik tersebut hanya akanmencapai tiga dari empat titik laninnya, dan akan terwarnaisama dengan warna untuk titik yang sudah ada dikarenakankeempat simpul tadi sudah terhubung dengan tiga sisi secaramenyeluruh, sehingga membangun akses ke setiap simpullainnya.

lanjutan

Namun, tidak adanya graf dengan lima simpul yangberdampingan tidak otomatis meniadakan graf yangmembutuhkan lima warna berbeda

Bila kita membuat jumlah maksimum hubungan antar simpulpada sebuah graf planar, selalu didapatkan bidang graf yangterbagi menjadi wilayah bersegitiga (triangular), yaitu wilayahyang dibatasi oleh tiga sisi dan berhubungan hanya dengantiga simpul.

Dengan demikian benarlah bahwa empat warna cukup untuksemua graf seperti ini

Bukti Lebih Kompleks

Apabila jumlah simpul, sisi dan wilayah berturut-turutdisimbolkan dengan V , E dan F , maka rumus Euler untukbidang (atau ruang) adalah V E + F = 2

Setiap wilayah pada graf planar dibatasi oleh tiga sisi, dansetiap sisi dibatasi oleh 3 wilayah, sehingga F = 2E3 dan rumusEuler untuk graf planar sederhana menjadi 2E = 6V 12,dan rata-rata sisi terhubung persimpul adalah 6 12vSelanjutnya untuk semua graf, jumlah rata-rata sisi terhubungpersimpul kurang dari 6. Hal ini memberi arti berdasarkanrumus Euler, tidak ada graf yang membutuhkan lebih darienam warna

Bukti Lebih Kompleks

Apabila jumlah simpul, sisi dan wilayah berturut-turutdisimbolkan dengan V , E dan F , maka rumus Euler untukbidang (atau ruang) adalah V E + F = 2Setiap wilayah pada graf planar dibatasi oleh tiga sisi, dansetiap sisi dibatasi oleh 3 wilayah, sehingga F = 2E3 dan rumusEuler untuk graf planar sederhana menjadi 2E = 6V 12,dan rata-rata sisi terhubung persimpul adalah 6 12vSelanjutnya untuk semua graf, jumlah rata-rata sisi terhubungpersimpul kurang dari 6. Hal ini memberi arti berdasarkanrumus Euler, tidak ada graf yang membutuhkan lebih darienam warna

lanjutan

Dengan pembuktian lanjutan, akan dapat ditemui bahwatidak ada graf yang memiliki bilangan kromatik lebih dari 5(jika ada, maka graf tersebut pasti memiliki lebih dari 5 titik)

perhatikan graf yang mengandung sebuah simpul dengan limasimpul tetangga dengan lima warna yang berbeda, sepertiilustrasi dibawah

lanjutan

Dengan pembuktian lanjutan, akan dapat ditemui bahwatidak ada graf yang memiliki bilangan kromatik lebih dari 5(jika ada, maka graf tersebut pasti memiliki lebih dari 5 titik)

perhatikan graf yang mengandung sebuah simpul dengan limasimpul tetangga dengan lima warna yang berbeda, sepertiilustrasi dibawah

lnajutan

Karena simpul tengah tak berwarna memiliki lima tetanggadengan warna yang berbeda, maka sepertinya kitamembutuhkan warna ke enam. Akan tetapi, kita bisamengubah urutan (transpose) warna biru dan hijau padacluster 2 biru/hijau pada sisi kiri atas pentagon, sehinggawarna biru menjadi hijau dan hijau menjadi biru.

Setelah melakukan ini, simpul tengah tak berwarna akanmemiliki tetangga dengan empat warna berbeda dan kitadapat memberinya warna biru

Jadi butuh 4 warna atau 5 warna? Perhatikan graf berikut.

lnajutan

Karena simpul tengah tak berwarna memiliki lima tetanggadengan warna yang berbeda, maka sepertinya kitamembutuhkan warna ke enam. Akan tetapi, kita bisamengubah urutan (transpose) warna biru dan hijau padacluster 2 biru/hijau pada sisi kiri atas pentagon, sehinggawarna biru menjadi hijau dan hijau menjadi biru.

Setelah melakukan ini, simpul tengah tak berwarna akanmemiliki tetangga dengan empat warna berbeda dan kitadapat memberinya warna biru

Jadi butuh 4 warna atau 5 warna? Perhatikan graf berikut.

Figure: Graf mengandung simpul yang dikelilingi empat simpul tetanggadengan warna berbeda

Simpul tak berwarna yang berada di tengah memiliki empatsimpul tetangga dengan empat warna yang berbeda. Inimemperlihatkan bahwa dibutuhkan warna ke lima. Tetapi,dengan mengubah susunan warna biru dan kuning padacluster-2 diatas simpul tengah (ditunjukkan dengan garisoutline merah), kita akan mendapatkan simpul-simpultetangga hanya memiliki tiga warna berbeda (merah, hijau,biru)

lanjutan

Simpul tak berwarna dapat diberi warna kuning ( = 4). Kitasudah melihat bahwa tidak ada graf yang membutuhkan lebihdari lima warna berbeda, menurut rumus Euler. Denganmenambah sisi, kita juga dapat membuat planar semua grafpada simpul V sehingga seluruh wilayahnya bersegitiga danmemiliki jumlah sisi terhubung tepat sebanyak 6V 12

Graf ini pastinya masih merupakan graf minimal lima warnakarena kita belum menaikkan jumlah simpulnya, danmenambah sisi tidak dapat mengurangi jumlah warna yangdibutuhkan, mengingat tidak ada graf yang membutuhkanlebih dari lima warna.

lanjutan

Simpul tak berwarna dapat diberi warna kuning ( = 4). Kitasudah melihat bahwa tidak ada graf yang membutuhkan lebihdari lima warna berbeda, menurut rumus Euler. Denganmenambah sisi, kita juga dapat membuat planar semua grafpada simpul V sehingga seluruh wilayahnya bersegitiga danmemiliki jumlah sisi terhubung tepat sebanyak 6V 12Graf ini pastinya masih merupakan graf minimal lima warnakarena kita belum menaikkan jumlah simpulnya, danmenambah sisi tidak dapat mengurangi jumlah warna yangdibutuhkan, mengingat tidak ada graf yang membutuhkanlebih dari lima warna.

lanjutan

Karena itu, misalkan a5, a6, a7, ... menunjuk jumlah simpuldengan 5, 6, 7 ,sisi terhubung berturut-turut, kita memilikisebuah graf minimal lima warna sedemikian rupa sehingga6V 12 = 5a5 + 6a6 + 7a7 + 8a8 + 9a9...(1) denganV = a5 + a6 + a7 + a8 + a9 Substitusi ekspresi ini ke dalampersamaan (1) diatas dan meyusunnya kembali, kitamendapatkan 12 = a5 a7 2a8 3a9...(2)Ini menetapkan batasan yang cukup sulit terhadap berbagaigraf minimal lima warna

lanjutan

Sebagai contoh, bila kita memperhatikan sebuah gaf serupayang tidak memiliki lebih dari enam sisi terhubung pada setiapsimpulnya, maka persamaan (2) menyatakan secara tidaklangsung bahwa a5 = 12. Dengan kata lain, sebuah grafplanar minimal lima warna dengan tidak lebih dari enam sisiterhubung per simpul, dipastikan memiliki tepat 12 simpuldengan lima buah sisi terhubung pada setiap simpulnya

Ini mengindikasikan bahwa 12 simpul ini disusun secara globaldalam bentuk sebuah icosahedron, dan sisa simpul lainnyayang memiliki enam sisi terhubung per simpul tersusun dalambentuk segienam beraturan, mengisi wilayah dari icosahedron

Graf yang fundamental untuk tipe seperti ini, dengan a6 = 0,ditunjukkan oleh gambar berikut.

Figure: Graf icosahedron dengan a6 = 0

Kita dapat melakukan secara eksplisit, empat pewarnaan padasetiap pola serupa, sehingga juga dapat ditunjukkan denganjelas bahwa graf serupa tidak memerlukan lebih dari empatwarna berbeda. Hal ini membuktikan kebenaran dari TeoremaEmpat Warna.

Pewarnaan Titik(simpul)2. Algotitma Welch-PowellPermasalahan 4 warna

pewarnaan graf

Science

PEWARNAAN MIKROBA

Kode MK/ Nama MK · Matematika Diskrit 1 8/29/2014 2 8/29/2014 . 8/29/2014 2 Himpunan, Relasi dan fungsi Kombinatorial Teori graf Pohon (Tree) dan pewarnaan graf 3 8/29/2014 Cakupan

DIMENSI PARTISI GRAF HASIL OPERASI COMB GRAF …

APLIKASI PEWARNAAN GRAF PADA PENGATURAN ...informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2017...penggunaan teori graf dalam pengaturan waktu efektif dalam siklus nyala lampu pada

laporan pewarnaan

pewarnaan (2)

Aplikasi Pewarnaan Graf dalam Pencarian Solusi Permainan ...informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2010-2011/Makalah... · Jadi sebuah soal Sudoku terdiri dari 81 sel, atau

Kode MK/ Nama MK - adiwijaya.staff.telkomuniversity.ac.id · Pewarnaan Graf (G) Contoh : Bilangan kromatik suatu graf lengkap-n (Kn) adalah n. Hal ini disebabkan karena setiap simpul

Pewarnaan Total Pada Graf Outerplanar - Total Coloring of ...digilib.its.ac.id/public/ITS-paper-29439-1209100053-Presentation.pdfmembuktikan bahwa berlaku untuk semua graf outerplanar,

KLASIFIKASI GRAF PETERSEN BERBILANGAN KROMATIK LOKASI ...digilib.unila.ac.id/25117/10/3. TESIS FULL TANPA BAB PEMBAHASAN.pdf · pengembangan dua konsep dalam graf yaitu pewarnaan

IMPLEMENTASI METODE PEWARNAAN GRAF …repository.its.ac.id/47467/7/1213100110-Undergraduate-Theses.pdf · Contoh Graf Berbobot dan Terhubung ... Gambar 4. 2 Usecase Diagram ... Gambar

Graf - dinus.ac.id · contoh graf sederhana 2. Graf tak-sederhana (unsimple-graph ). Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph ). G

PENGEMBANGAN ALGORITMA BARIS UNTUK PEWARNAAN …pasca.unhas.ac.id/jurnal/files/256bc5ac80b2296a34330403e07c8c4d.pdfSalah satu algoritma yang dapat digunakan untuk pewarnaan graf adalah

Daftar lsi - adiwijaya.staff.telkomuniversity.ac.id · algoritma pewarnaan- pada graf tersebut tidak dapat ditentukan secara deterministik dalam sebanyak polinomial langkah. Misalkan

Makalah Teori Graf(Graf Berarah)

APLIKASI PEWARNAAN GRAF FUZZY DAN FIS UNTUK …lib.unnes.ac.id/37492/1/4111414024.pdf · 2020. 7. 23. · Aplikasi Pewarnaan Graf Fuzzy dan FIS untuk Menentukan Fase dan Durasi Lampu

Aplikasi Pewarnaan Graf dalam Penyelesaian Nurse Rostering ...informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2018-2019/Makalah... · Makalah IF2120 Matematika Diskrit – Sem. I

Kode MK/ Matematika Diskrit...2014/02/04 · 8/29/2014 1 Kode MK/ Matematika Diskrit TEORI GRAF 1 8/29/2014 Himpunan, Relasi dan fungsi Kombinatorial Teori graf Pohon (Tree) dan pewarnaan

pewarnaan bakteri

TEORI GRAF - ilhamsaifudin12.files.wordpress.com · 4 Contoh Aplikasi Graf Terminologi Graf 5 6 Graf-graf Khusus Representasi Graf 7 8 Graf Isomorfik . OUTLINE 1. PENDAHULUAN 1. PENDAHULUAN

Kode MK/ Nama MK...2014/02/02 · 8/29/2014 1 Kode MK/ Nama MK Matematika Diskrit 1 8/29/2014 Himpunan, Relasi dan fungsi Kombinatorial Teori graf Pohon (Tree) dan pewarnaan graf

Pengembangan Aplikasi Pewarnaan Graf Berbasis …

Modul 6. Pewarnaan Graf (2x Pert)

PLAGIAT MERUPAKAN TINDAKAN TIDAK … Graf .....7 2.1.1 Definisi Graf .....7 2.1.2 Definisi Walk, Trail, Path dan 2.1.3 Graf Eulerian dan Graf Hamiltonian.....9 2.1.4 Macam-macam Graf

PENERAPAN PEWARNAAN GRAF UNTUK MENENTUKAN …dengan menggunakan Algoritma Pewarnaan Barisan Sederhana pada titik. Diharapkan dengan menggunakan Algoritma Pewarnaan Barisan ... Ayam

Pewarnaan Tahan Asam Dan Pewarnaan Spora_popy Sarah C_260110130136

Aplikasi Pewarnaan Graf dalam Penyelesaian Nurse Rostering ...informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/... · menggunakan graf. Dan pada makalah ini, akan kita bahas salah

Paper Title (use style: paper title) · permasalahan pewarnaan-sisi-kuat pada graf pertamakali dipelajari oleh Fouquoet dan Jolivet pada tahun 1983 untuk graf kubus planar (Gerard

perbandingan 2 metode pewarnaan backbonerepositori.uin-alauddin.ac.id/12406/1/Skripsi Rahma...perbandingan 2 metode pewarnaan backbone dalam menentukan bilangan pewarnaan pada graf

PENGELOLAAN JADWAL PENGGUNAAN LABORATORIUM … · graf yang paling sederhana yaitu pewarnaan simpul graf. a. Pewarnaan Simpul Graf Pewarnaan simpul adalah memberi warna pada simpul-simpul

Pewarnaan Dan Cara-cara Pewarnaan

pewarnaan gram

PEMBERIAN NOMOR VERTEX PADA TOPOLOGI JARINGAN GRAF … filejaringan graf yang berbentuk graf wheel , graf helm dan graf lollipop . Didapatkan hasil penelitian berupa penomoran vertex

STUDI DAN IMPLEMENTASI COLOURING GRAF DENGAN …informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2006-2007/Makalah/... · Pemecahan masalah pewarnaan pada peta ini tidak terjadi secara

IMPLEMENTASI PEWARNAAN GRAF …repository.its.ac.id/42694/1/1213100046-Undergraduate...i TUGAS AKHIR – SM 141501 IMPLEMENTASI PEWARNAAN GRAF MENGGUNAKAN ALGORITMA WELCH POWELL UNTUK