PEWARNAAN GRAF

A.  LATAR BELAKANG

Teori graf merupakan pokok bahasan yang sudah lama tapi sampai sekarang masih memiliki terapan di berbagai persoalan dalam kehidupan sehari-hari, salah satu contohnya adalah penggunaan pewarnaan graf pada pengaturan lampu lalu lintas di perempatan jalan dan pembuatan peta.

Masalah pembuatan lampu lalu lintas dapat dimodelkan dalam bentuk graf Apabila sebuah peta yg menggambarkan suatu daerah yg di dalamnya banyak terdapat objek-objek diskrit, dimana kita dapat menggambarkan dengan baik agar lebih mudah di pahami oleh pengguna peta dengan menggunakan metode graf , pewarnaan graf dalam pengaturan warna lampu lalu lintas di perempatan jalan sehingga mencegah terjadinya tabrakan di perempatan jalan tersebut, penyusunan jadwal matakuliah,jadwal shift kerja dan masih banyak persoalan-persoalan unik lain yg dapat kita selesaikan dengan metode graf.

B. TUJUAN

            Pewarnaan graf ini bertujuan untuk menyelesaikan permasalahaan terhadap pengaturan warna lampu lalu lintas pada sebuah perempatan jalan. Pada perempatan jalan tersebut terdapat 4 buah lampu lalu

lintas. Nyala lampu lalu lintas diatur sedemikian rupa sehingga tidak akan terjadi tabrakan antar kendaraan yang melintas di jalan tersebut. Untuk pengaturan warna lampu lalu lintas yang menyala dapat diselesaikan dengan teknik pewarnaan graf.

C. ALGORITMA WELCH-POWELL

Algoritma Powell-Welch adalah suatu langkah yang digunakan dalam pewarnaan graf. Algoritma ini terdiri dari beberapa langkah, yaitu :

1.    Mula-mula kita urutkan semua simpul berdasarkan derajatnya, dari derajat besar ke derajat kecil.

2.    Ambil warna pertama, dan warnai simpul pertama yang berderajat terbesar.

3.    Kemudian warnai simpul berikutnya yang tidak berdampingan, terus menerus, berdasarkan urutan derajatnya dari yang terbesar hingga yaang terkecil.

4.    Kemudian kita lanjutkan dengan warna kedua dan seterusnya, sampai semua simpul telah diberi warna.

D. PEMBAHASAN

Pewarnaan graf (graph coloring) adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu. Ada tiga macam pewarnaan graf :

1.      Pewarnaan simpul

Pewarnaan simpul (vertex coloring) adalah memberikan warna yang  pada simpul-simpul suatu graf sedemikian sehingga tidak ada dua simpul bertetangga mempunyai warna yang sama

Gambar 4. Contoh pewarnaan simpul

2.      Pewarnaan sisi

Pewarnaan sisi (edge coloring) adalah memberikan warna berbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga mempunyai warna yang sama

Gambar 5. Contoh pewarnaan sisi

3.      Pewarnaan bidang

Pewarnaan bidang adalah memberi warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama. Pewarnaan bidang hanya bisa dilakukan dengan membuat graf tersebut menjadi graf planar terlebih dahulu. Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong (bersilangan), seperti yang ditunjukkan gambar di bawah ini. 

Gambar 6. Contoh graf planar

Setelah terbentuk graf planar, lalu memberikan warna berbeda untuk setiap bidang yang berdekatan. Dan jumlah warna yang digunakan harus sedikit mungkin.

Gambar 7. Contoh pewarnaan bidang

Dalam pewarnaan graf, jumlah warna yang digunakan untuk mewarnai simpul, sisi, maupun bidang diusahakan sesedikit mungkin. Jumlah warna minimum yang dapat digunakan tersebut disebut bilangan kromatik graf G, disimbolkan dengan χ(G). Suatu graf G yang mempunyai bilangan kromatis k dilambangkan dengan χ(G) = k.

CONTOH :

PENGATURAN WARNA PADA LAMPU LALU LINTAS MENGGUNAKAN GRAF

Sudah disebutkan sebelumnya bahwa sampai saat ini, teori graf masih diterapkan di berbagai persoalan dalam kehidupan sehari-hari. Misalnya aplikasi pewarnaan graf dalam pengaturan warna lampu lalu lintas di perempatan jalan sehingga mencegah terjadinya tabrakan di perempatan jalan tersebut.

Gambar 8. Lampu lalu lintas perempatan jalan

Seperti yang ditunjukkan pada gambar diatas, sebuah perempatan jalan mempunyai 4 buah lampu lalu lintas. Lampu lalu lintas pada jalan B dan F menyala bersamaan. Lampu lalu lintas pada jalan D dan H juga menyala bersamaan.

Dalam perempatan jalan tersebut diketahui jika lampu di jalan B dan F menyala hijau maka jalur yang boleh digunakan adalah dari B ke E, F ke A. selain itu jalur langsung belok kiri juga diperbolehkan, yaitu dari B ke C, dan F ke G.

Jika di jalan D dan H lampu hijau menyala maka jalur yang boleh digunakan untuk melintas adalah jalur dari D ke E, D ke G, H ke A, dan H ke C. Dalam kondisi ini, jalur langsung belok,  kiri juga diperoblehkan.

Untuk menyelesaikan permasalahan pada pembuatan lampu lalu lintas pada sebuah perempatan jalan, maka hal yang harus dilakukan terlebih dahulu adalah menentukan jalur mana yang bisa berjalan dengan memberi lampu hijau di tempat tertentu dan member lampu merah agar kendaraan pada lintasan yang lain berhenti sehingga tidak terjadi tabrakan.

Gambar 9. Jalur di perempatan jalan

Diketahui bahwa jalur yang bisa digunakan untuk melintas adalah dari B ke C, B ke E, D ke E, D ke G, F ke G, F ke A, H ke A, dan H ke C. Setelah mengetahui jalur mana saja yang bisa dilewati, berikut langkah-langkah untuk mengatur lampu lalu lintas menggunakan graf.

1.      Membuat simpul-simpul sebagai tanda dari semua jalur yang bisa dilewati dalam perempatan jalan. Letak dari simpul-simpul tersebut bebas, tidak ada aturan tertentu untuk mengharuskan simpul harus diletakkan di posisi mana karena hal itu tidak terlalu berpengaruh.

Gambar 10. Simpul-simpul dari jalur jalan

2.      Menentukan sisi untuk menghubungkan 2 simpul yang saling melintas atau berseberangan. Untuk memudahkan hal ini, carilah simpul-simpul yang menunjukkan jalur mana saja yang akan bertabrakan jika semua lampu lalu lintas berwarna hijau. Pada Gambar 9 terlihat bahwa jalur BE dan DG, BE dan HC, FA dan DG, FA dan HC saling berseberangan. Karena BE dan DG berseberangan, maka kedua simpul tersebut dihubungkan dengan garis yang disebut sisi. Setelah itu, simpul-simpul lain yang saling berseberangan juga dihubungkan dengan sebuah sisi.

Gambar 11. Graf jalur jalan

3.      Setelah menghubungkan semua simpul (jalur) yang saling berseberangan, langkah selanjutnya

yang harus dilakukan adalah memberi warna pada masing-masing simpul dengan ketentuan pemberian warnanya sebagai berikut

·         Menggunakan jumlah warna sedikit mungkin

·         Simpul yang bertetanggaan (terhubung dengan sisi) tidak boleh berwarna sama

·         Memberi warna yang sama pada simpul yang tidak terhubung secara langsung

·         Simpul yang tidak terhubung dengan sisi (simpul terpencil), berarti jalur tersebut boleh berlaku lampu lalu lintas berwarna hijau terus.

·         Warna yang digunakan bebas.

Gambar 12. Pewarnaan pada simpul graf

Berdasarkan gambar diatas, semua simpul telah diwarnai sesuai ketentuan pewarnaan pada graf.

Graf diatas memiliki bilangan kromatis 3 (χ(G) = 3) karena jumlah minimum warna yang digunakan sebanyak 3 simpul FA dan BE berwarna sama yaitu hijau karena keduanya tidak terhubung/bertetanggaan. Tapi simpul DG dan HC terhubung dengan simpul FA dan BE sehingga harus diberi warna yang berbeda yaitu warna merah. Sementara simpul HA, BC, DE, FG diberi warna sama yaitu kuning karena simpul-simpul tersebut adalah simpul terpencil yang tidak terhubung dengan simpul lain dan itu berarti bahwa jalur-jalur dari simpul tersebut tidak ada yang saling melintas sehingga keempat jalur itu bisa berlaku lampu hijau terus.

4.      Langkah selanjutnya adalah mengelompokkan simpul-simpul tersebut berdasarkan kesamaan warna.

·         Merah = DG dan HC

·         Hijau = BE dan FA

·         Kuning = BC, DE, FG, dan HA

Dari pengelompokkan tersebut diperoleh 2 kondisi untuk lampu lalu lintas di perempatan jalan

Lampu Merah	DG, HC
Lampu Hijau	BE, FA, BC, DE, FG, HA

Tabel 1. Kondisi lampu lalu lintas 1

Lampu Merah	BE, FA
Lampu Hijau	DG, HC, BC, DE, FG, HA

Tabel 2. Kondisi lampu lalu lintas 2

Berdasarkan tabel-tabel diatas, lampu merah berarti bahwa jalur tidak boleh digunakan untuk melintas, sedangkan lampu hijau menunjukkan bahwa jalur bisa digunakan untuk melintas.

Pada Tabel 1, jika di jalan D dan H lampu merah menyala maka jalur DG dan HC tidak boleh digunakan. Disaat yang bersamaan di jalan B dan F lampu hijau menyala sehingga jalur BE dan FA boleh digunakan. Karena langsung belok kiri juga diperbolehkan, maka jalur BC, DE, FG, HA juga bisa digunakan untuk melintas.

Hal-hal tersebut juga berlaku untuk Tabel 2, ketika di jalan B dan F lampu merah menyala maka di jalan D dan H lampu hijau akan menyala. Sehingga jalur-jalur yang bisa digunakan antara lain DG, HC, BC, DE, FG, dan HA.

E.  KESIMPULAN

Teori graf merupakan pokok bahasan yang sudah lama tapi sampai sekarang masih memiliki terapan di berbagai persoalan dalam kehidupan sehari-hari, salah satu contohnya adalah penggunaan pewarnaan graf pada pengaturan lampu lalu lintas di perempatan jalan.

Masalah pembuatan lampu lalu lintas dapat dimodelkan dalam bentuk graf. Untuk mencari solusi dari permasalahan pengaturan warna lampu lintas dapat digunakan teknik pewarnaan simpul pada graf.

Untuk penyelesaian dari pengaturan warna pada lampu lalu lintas di perempatan jalan, jumlah minimum warna yang digunakan untuk pewarnaan simpul adalah 3.