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