TEORI
GRAF DALAM PENGATURAN
WARNA PADA LAMPU LALU LINTAS
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 diperbolehkan.
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 member 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 langkahlangkah 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
1. 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.
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
simpulsimpul 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
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.
terima kasih...
semoga bermanfaat....
sumber : http://rahadikusuma.blogspot.com/2013/12/matematika-diskrit-pewarnaan-graf_30.html
