pewarnaan graf
Embed Size (px)
TRANSCRIPT

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 Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Pewarnaan Graf
1 Pewarnaan Titik(simpul)
2 2. Algotitma Welch-Powell
3 Permasalahan 4 warna
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 2
Figure: Bilangan kromatik graf G di atas χ(G ) = 3
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 3
Figure: Bilangan kromatik graf G , χ(G ) = 3 < 7 = k
Contoh 4
Figure: Bilangan kromatik graf G , χ(G ) = k = 3
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 3
Figure: Bilangan kromatik graf G , χ(G ) = 3 < 7 = k
Contoh 4
Figure: Bilangan kromatik graf G , χ(G ) = k = 3
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 3
Figure: Bilangan kromatik graf G , χ(G ) = 3 < 7 = k
Contoh 4
Figure: Bilangan kromatik graf G , χ(G ) = k = 3Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 6
Figure: Graf H adalah graf bagian dari graf G dengan χ(H) = χ(G ) = 2
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 ) = t
Dengan mengingat bahwa χ(G ) ≤ t, maka χ(G ) = t
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 ) = t
Dengan mengingat bahwa χ(G ) ≤ t, maka χ(G ) = t
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 ) = t
Dengan mengingat bahwa χ(G ) ≤ t, maka χ(G ) = t
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 ) = t
Dengan mengingat bahwa χ(G ) ≤ t, maka χ(G ) = t
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 ) = t
Dengan mengingat bahwa χ(G ) ≤ t, maka χ(G ) = t
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 7
Figure: Graf G dengan komponen-komponennya G1,G2 dan G3
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 10
Figure: Graf bipartisi G memiliki bilangan kromatik χ(G ) = 2
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 11
Figure: Suatu graf dengan bilangan kromatik χ(G ) = 2 dan graf tersebutbipartisi
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≥ 3
misalkan titik-titik dari graf Cn dituliskan sebagai v1, v2, ..., vn
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≥ 3
misalkan titik-titik dari graf Cn dituliskan sebagai v1, v2, ..., vn
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≥ 3
misalkan titik-titik dari graf Cn dituliskan sebagai v1, v2, ..., vn
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≥ 3
misalkan titik-titik dari graf Cn dituliskan sebagai v1, v2, ..., vn
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≥ 3
misalkan titik-titik dari graf Cn dituliskan sebagai v1, v2, ..., vn
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≤ 3
Karena χ(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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≤ 3
Karena χ(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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≤ 3
Karena χ(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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≤ 3
Karena χ(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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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) ≤ 3
Karena χ(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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 12
Figure: graf C6 memiliki χ(C6) = 2 dan graf C5 memiliki χ(C5) = 3
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 )| = 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
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 )| = 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
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 )| = 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
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 )| = 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
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 )| = 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
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 − 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 .
Dari kasus 1 dan kasus 2 , maka diperoleh χ(G − v) ≤ ∆(G ) + 1
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 − 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 .
Dari kasus 1 dan kasus 2 , maka diperoleh χ(G − v) ≤ ∆(G ) + 1
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 − 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 .
Dari kasus 1 dan kasus 2 , maka diperoleh χ(G − v) ≤ ∆(G ) + 1
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 − 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 .
Dari kasus 1 dan kasus 2 , maka diperoleh χ(G − v) ≤ ∆(G ) + 1
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 13Berikan warna seminimal mungkin pada graf dibawah inisedemikian hingga setiap dua titik yang bertetangga berbeda warna
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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 .
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
lanjutanDengan demikian, hasil pewarnaan graf G dalam contoh ini adalahsebagai berikut:
Figure: Graf G dalam contoh ini terwarnai dalam 4 warna
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Contoh 14Diberikan graf sederhana G di bawah ini
Figure: Graf G dalam contoh ini terwarnai dalam 3 warna
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
lanjutanPewarnaan graf sederhana G pada contoh 14 adalah sbb
Figure: Bilangan Kromatik dari Graf G dalam contoh ini adalah χ(G ) = 3
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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)
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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)
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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)
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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 = 2
Setiap wilayah pada graf planar dibatasi oleh tiga sisi, dansetiap sisi dibatasi oleh 3 wilayah, sehingga F = 2E
3 dan rumusEuler untuk graf planar sederhana menjadi 2E = 6V − 12,dan rata-rata sisi terhubung persimpul adalah 6− 12
v
Selanjutnya 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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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 = 2
Setiap wilayah pada graf planar dibatasi oleh tiga sisi, dansetiap sisi dibatasi oleh 3 wilayah, sehingga F = 2E
3 dan rumusEuler untuk graf planar sederhana menjadi 2E = 6V − 12,dan rata-rata sisi terhubung persimpul adalah 6− 12
v
Selanjutnya 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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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)
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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 − 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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 − 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF

Pewarnaan Titik(simpul)2. Algotitma Welch-Powell
Permasalahan 4 warna
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.
Rukmono Budi Utomo30115301 TEORI GRAFPEWARNAAN GRAF