Pewarnaan (Coloring) – Pengaturan Warna Pada Lampu Lalu Lintas

Sumber: http://bloglogika.blogspot.com/2011/02/pengaturan-warna-pada-lampu-lalu-lintas.html

Pewarnaan (Coloring)

Pewarnaan yang kita bahas kali ini adalah sebuah cara yang digunakan untuk menyelesaiakan proses panjadwalan. Dimana dalam pewarnaan ini akan digambarkan dengan graph yang terdiri atas simpul, dan ruas

Dalam kehidupan sehari-hari sering kali kita dipusingkan oleh rumitnya penjadwalan, misalnya jika kita harus membuat jadwal ujian dimana ada beberapa mahasiswa yang mengikuti beberapa mata kuliah, tentunya agar mahasiswa tersebut dapat mengikuti  semua ujian, maka mata kuliah yang diambil secara bersamaan oleh satu siswa tersebut tidak boleh dijadwalkan pada hari dan jam yang sama. Atau misalnya kita mendapatkan proyek untuk membuat  lampu lalulintas di sebuah perlimaan, maka kita harus mengatur nyala lampu merah dan hijau agar tidak terjadi tabrakan. Saat ini kita akan belajar bersama salah satu metode untuk mengatasi permasalahan tersebut dengan metode pewarnaan (Coloring).

 

Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek. Representasi visual dari graf adalah dengan menyatakan objek dengan simpul, noktah, bulatan, titik, atau vertex, sedangkan hubungan antara objek dinyatakan dengan garis , edge atau ruas.

Pewarnaan graf adalah proses pelabelan setiap simpul dalam graf dengan label tertentu (warna) sehingga tidak ada dua simpul bertetangga yang memiliki warna sama. Warna yang kita gunakan untuk mewarnai objek diusahakan seminimal mungkin. Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik

.
beberapa contoh permasalahan yang bisa diselesaikan dengan pewarnaan adalah

Pengaturan Warna Pada Lampu Lalu Lintas

Pada tulisan kali ini, kita akan mencoba menyelesaikan permasalahan pada pembuatan lampu lalu lintas pada sebuah jalan simpang 5, kita akan mencoba menentukan jalur mana yg bisa berjalan dengan memberi lampu hijau, dan memberi lampu merah agar kendaraan pada lintasan yg lain berhenti, tujuannya adalah agar tidak terjadi tabrakan
mari kita lihat contoh gambarberikut

Gambar 1

Dari gambar diatas dapat kita peroleh informasi, bahwa jalur yang boleh melintas adalah dari A ke B, A ke C, A ke D, B ke C, B ke D, E ke B, E ke C, dan E ke D.

Setelah kita tahu jalur yang boleh dilewati kita akan menempuh langkah sebagai berikut

1. Membuat simpul sebagai simbol dari semua jalur yag diperboleh. letak masing-masing simpul bebas. lihat gambar berikut:

Gambar 2


2. Menentukan ruas untuk menghubungkan 2 simpul yang saling melintas atau bersebrangan, pada gambar 1 diatas terlihat bahwa jalur AB, dan  BD, saling berseberangan, maka kita hubungkan simpul AB dam BD dengan garis yang disebut ruas, dan kita akan memberikan ruas pada semua jalur yang bersebrangan, mari kita lihat gambar 3 berikut

Gambar 3

3. pada gambar 3 kita telah menghubungkan semua jalur yang saling melintas, langkah berikutnya adalah memberikan warna pada masing-masing simpul yang terhubung dengan ruas atau garis, ketentuan pemberian warnanya adalah

  • Gunakan Warna seminimal mungkin
  • Simpul yang berdampingan atau /Terhubung langsung dengan ruas, tidak boleh berwarna sama
  • Berikan warna yang sama pada simpul yang tidak terhubung secara langsung
  • Simpul yang tidak terhubung dengan ruas atau simpul bebas, berarti lintasan tersebut boleh berlaku lampu hijau terus.
  • Awal pewarnaan Bebas
Gambar 4

Dari Gambar 4 diatas, semua simpul telah diwarnai, dari gambar ersebut simpul EC berwarna kuning sendiri, hal ini dikarenakan simpul EC terhubung secara langsung dengan simpul AD yang berwarna merah, dan terhubung dengan simpul BD yang berwarna coklat, jadi kita harus memberi warna selain coklat dan merah, dalam hal ini kita pilih warna kuning,  sementara simpul ED, AB, BC , jadi ke 3 simpul tersebut kita beri warna yang sama, selain merah, coklat dan kuning tentunya, pada contoh diatas kita beri warna hijau. Simpul ED, AB, BC adalah simpul bebas (simpul yang tidak terhubung dengan simpul lain) yang berarti jalur tersebut tidak ada jalur yang saling melintas artinya ketiga ruas bebas itu bisa berlaku lampu hijau terus.

4. langkah berikutnya adalah mengelompokan simpul berdasarkan warna
Merah => AC, AD
Coklat => BD, EB
Kuning => EC
Hijau    => ED, AB, BC

Dari langkah-langkah diatas kita bisa mendapatkan 3 fase pola lampu lalu lintas sebagai berikut

Hijau AC, AD, ED, AB, BC
Merah BD, EB, EC
Hijau BD, EB, ED, AB, BC
Merah AC,AD, EC
Hijau EC, ED, AB, BC
Merah AC,AD, BD, EB

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s