Nama : Rafli Nur
Haqim
Kelas : 4IA24
Npm : 55416958
Prinsip cara kerja lampu lalu lintas dengan menggunakan
algoritma Graph Coloring.
Gambar 0
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
yang diperboleh. letak masing-masing simpul bebas. lihat gambar berikut :
Gambar 1
2. Menentukan
ruas untuk menghubungkan 2 simpul yang saling melintas atau bersebrangan, pada
gambar 0 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 2 berikut :
Gambar 2
3.
Pada gambar 2 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 3
Dari Gambar 3 diatas, semua
simpul telah diwarnai, dari gambar tersebut 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
Komentar
Posting Komentar