Definisi Pewarnaan Graf (Coloring Graph)
Masalah pewarnaan graf adalah memberikan warna pada elemen-elemen tertentu dari graf yang tunduk pada batasan-batasan tertentu. Pewarnaan titik adalah masalah pewarnaan graf yang paling umum. Soalnya, diberikan m warna, temukan cara mewarnai simpul dari suatu graf sedemikian rupa sehingga tidak ada dua simpul bertetangga yang diwarnai menggunakan warna yang sama.
Bilangan Kromatik
Bilangan Kromatik adalah banyaknya warna minimum yang diperlukan untuk mewarnai simpul-simpul suatu graf G sedemikian rupa sehingga tidak ada dua simpul bertetangga yang memiliki warna yang sama dilambangkan dengan x(G).
Teorema Bilangan Kromatik pada Subgraf bagian : Jika H adalah subgraf dari G,χ(H)≤χ(G).
Bukti: Setiap pewarnaan G memberikan pewarnaan yang tepat untuk H, hanya dengan memberikan warna yang sama pada simpul-simpul H yang mereka miliki di G. Ini berarti bahwa H dapat diwarnai dengan warna (G), bahkan mungkin lebih sedikit.
Teorema Pewarnaan Graf Komplit (Complete Graph): Jika G adalah graf lengkap dengan n titik (Kn) maka χ(n)=n.
Bukti: Karena G merupakan graf lengkap maka tiap titiknya berderajat n-1. Pilih sembarang titik v untuk diwarnai maka untuk mewarnai titik lain yang bertetangga memerlukan n-1 warna. Sehingga banyak warna n-1+1=n warna.
Teorema Graf Nol (Null Graph) : Jika G adalah graf nol maka χ(G)=1.
Bukti: Karena G graf nol maka tidak akan ada titik yang bertetangga sehingga hanya butuh satu warna untuk semua titik di G.
Teorema Graf Bipartisi : G graf bipartisi jika dan hanya jika χ(G).
Bukti: Himpunan titik V(G) dibagi menjadi dua himpunan bagian V1 dan V2. Pilih salah satu himpunan bagian V1, karena setiap titik pada himpunan bagian V1 tersebut tidak bertetangga maka hanya perlu menggunakan 1 warna begitu juga dengan V2. Kemudian tiap titik di V1 bertetangga di V2 sehingga V1 dan V2 memiliki warna yang berbeda sehingga χ(G)=2.
Teorema Graf Sikel: Jika G graf sikel Cn maka χ(G)=2 untuk n genap dan 3 untuk n ganjil.
Bukti: Untuk sikel genap, titik titik pada G dapat diwarnai selang seling sehingga hanya dibutuhkan 2 warna. Selanjutnya untuk sikel ganjil n, n-1 genap sehingga dapat selang seling, tetapi ada titik ke n yang terhubung dengan titik 1 dan n-1 yang memiliki 2 warna berbeda sehingga pada titik n memerlukan warna ke 3.
Teorema Derajat Terbesar: Misalakn G graf sederhana dengan derajat terbesar Δ(G), maka χ(G)≤ Δ(G)+1.
Teorema Graf Planar : Pada Graf Planar G dapat diwarnai oleh 4 warna.
Algoritma Welsh Powell
Dalam teori graf, pewarnaan simpul adalah cara memberi label pada setiap simpul individu sedemikian rupa sehingga tidak ada dua simpul bertetangga yang memiliki warna yang sama. Tapi kita perlu mencari tahu jumlah warna yang kita butuhkan untuk memenuhi kondisi yang diberikan. Tidak diinginkan untuk memiliki banyak variasi warna atau label. Jadi, Kami memiliki algoritma yang disebut algoritma welsh Powell yang memberikan warna minimum yang kami butuhkan. Algoritma ini juga digunakan untuk mencari bilangan kromatik suatu graf. Ini adalah pendekatan serakah berulang.
Algoritma Welsh Powell terdiri dari Langkah-langkah berikut:
- Tentukan derajat setiap simpul
- Daftar simpul dalam urutan derajat menurun.
- Warnai simpul pertama dengan derajat terbesar dengan warna 1.
- Pindah ke bawah daftar dan warnai semua simpul yang tidak terhubung ke simpul berwarna, dengan warna yang sama.
Ulangi langkah 4 pada semua simpul yang tidak diwarnai dengan warna baru, dalam urutan derajat yang menurun hingga semua simpul diwarnai.
Dengan memulai dengan derajat terbesar, kami memastikan bahwa simpul dengan jumlah konflik tertinggi dapat ditangani sedini mungkin.
0 komentar:
Post a Comment