Penggunaan Teori Graf pada Pengaturan Lampu Lalu Lintas di Persimpangan Arion
1.1.1
Teori Graf
Secara umum
pengertian graf adalah himpunan tidak kosong simpul-simpul (vertex/node) yang
dinotasikan dengan simbol V dan himpunan sisi (edge) yang dinotasikan dengan E, pengertian sisi adalah
sebuah garis yang menghubungkan dua buah simpul. Sedangkan untuk penulisan graf, graf G dapat dinyatakan dengan G=(V,E) dimana
V adalah himpunan simpul dan E adalah himpunan sisi yang merupakan himpunan
bagian dari VxV. Untuk memudahkan pengertian graf biasanya digunakan gambaran
geometri dari graf dengan cara seperti berikut:
Setiap simpul
digambarkan sebagai suatu titik dibidang datar, sedangkan setiap sisi
digambarkan sebagai sebuah garis yang menghubungkan dua buah simpul dalam graf
tersebut.
Gambar 1 Contoh Graf
Pada
gambar diatas, sisi e3 = (1,3) dan sisi e4 =
(1,3) dinamakan sisi-ganda (multiple edges atau parallel edges) karena kedua
sisi tersebut menghubungkan dua simpul yang sama, yaitu simpul 1 dan simpul 3.
Sedangkan sisi e8 = (3,3) dinamakan sisi gelang atau kalang (loop) karena ia
berawal dan berakhir pada simpul yang sama.
Berdasarkan ada
tidaknya gelang atau sisi ganda pada suatu graf, maka graf dapat digolongkan
menjadi dua jenis, yaitu graf sederhana dan graf tak-sederhana.
Graf
sederhana adalah graf yang tidak mengandung gelang
maupun sisi-ganda.
Gambar
2 Contoh Graf Sederhana
Sedangkan
graf tak-sederhana adalah graf yang mengandung sisi ganda atau gelang. Ada dua
jenis graf-tak-sederhana, yaitu graf ganda (multigraph) dan graf semu
(pseudograph). Graf ganda adalah graf yang mengandung sisi ganda. Graf semu
adalah graf yang mengandung gelang termasuk jika mempunyai sisi ganda pada graf
tersebut. Graf pada Gambar 1 merupakan salah satu contoh graf semu. Gambar di
bawah ini adalah graf ganda.
gambar 3
Berikut ini beberapa terminologi dasar yang menyangkut tentang
graf :
1.
Bertetangga
Dua buah simpul pada graf tak berarah G dikatakan bertetangga bila
keduanya terhubung langsung dengan sebuah sisi pada graf G.
2.
Bersisian
Untuk sembarang sisi e = (vj,vk), sisi e dikatakan bersisian
dengan simpul vj dan simpul vk.
3.
Simpul
Terpencil
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian
dengannya. Atau, dapat juga simpul terpencil adalah simpul yang tidak satupun
bertetangga dengan simpul-simpul lainnya.
4.
Graf Kosong
Graf kosong adalah graf yang himpunan sisinya merupakan himpunan
kosong. Dan ditulis sebagai Nn, yang dalam hal ini n adalah jumlah simpul.
5.
Derajat
Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang
bersisian dengan simpul tersebut.
6.
Lintasan
Lintasan yang panjangnya n dan simpul awal v0 ke simpul tujuan vn
di dalam graf G ialah barisan selang-seling simpul-simpul dan sisi-sisi yang
berbentuk v0, e1, v1, e2, v2, … , vn-1, en, vn sedemikian sehingga i1 =
(v0,v1), e2 = (v1,v2), … , en = (vn-1,vn), adalah sisi – sisi dari graf G.
7.
Siklus atau
Sirkuit
Lintasan yang berawal dan berakhir pada simpul yang sama disebut
siklus atau sirkuit.
8.
Terhubung
Graf tak berarah G disebut graf terhubung jika untuk setiap pasang
simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v.
Tabel 1 Lampu Lalu Lintas Kondisi 1
Tabel 2 Lampu Lalu Lintas Kondisi 2
Tabel 3 Lampu Lalu Lintas Kondisi 3
Tabel 4 Lampu Lalu Lintas Kondisi 4
Tabel 5 Lampu Lalu Lintas Kondisi 1
Tabel 6 Lampu Lalu Lintas Kondisi 2
Tabel 7 Lampu Lalu Lintas Kondisi 3
Tabel 8 Lampu Lalu Lintas Kondisi 4
Tabel 9 Lampu Lalu Lintas Kondisi 5
Pewarnaan Graf
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 member warna pada
simpul-simpul suatu graf sedemikian sehingga tidak ada dua simpul bertetangga
mempunyai warna yang sama.
2.
Pewarnaan
sisi
Pewarnaan sisi (edge
coloring) adalah memberi warnaberbeda pada sisi yang bertetangga sehingga tidak
ada dua sisi yang bertetangga mempunyai warna yang sama.
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 4 Model Perempatan Jalan Arion
Pembahasan
1.1.1
Model Perempatan Jalan
Model perempatan jalan yang dibahas adalah perempatan
jalan Arion, Rawamangun, Jakarta Timur.
Dari
gambar diatas bisa kita lihat bahwa jalur B, F, H, dan L masing masing
mempunyai dua buah lampu lalu lintas. Lampu lalu lintas yang pertama adalah
untuk jalur mobil bergerak lurus, sedangkan lampu lalu lintas kedua untuk jalur
mobil yang berbelok. Jalur D, E, J, K
adalah jalur TransJakarta atau busway.
Dalam perempatan jalan tersebut diketahui
bahwa jalur langsung belok kanan dan kiri diperbolehkan. Lampu B1B2,
H1H2, dan L1L2 akan menyala
bersama, lampu L2 akan menyala merah lebih cepat dibandingkan L1,
demikian juga dengan lampu F2 akan menyala merah lebih cepat
dibandingkan F1. Mobil di
jalur J ke E dan K ke D (jalur TransJakarta) akan diperbolehkan jalan jika
lampu di F2 dan L2 berwarna merah.
1.1.2
Langkah – Langkah
Pewarnaan Graf
a.
Langkah pertama yang harus
dilakukan adalah pembuatan simpul- simpul sebagai tanda dari semua jalur yang
bia dilewati dalam perempatan jalan Arion tersebut. Peletekan simpul-simpul
tersebut bebas, karena tidak akan terlalu berpengaruh terhadap apapun.
b.
Langkah kedua adalah
menentukan sisi untuk menghubungkan 2 simpul yang saling melintas atau
berseberangan. Untuk mempermudah, carilah simpul-simpul yang menunjukkan jalur
mana saja yang akan mengalami tabrakan jika semua lampu berwarna hijau.
c.
Setelah menentukan sisi,
langkah selanjutnya adalah member warna pada masing-masing simpul dengan
ketentuan pemberian warna sebagai berikut :
·
Menggunakan warna
sesedikit mungkin.
·
Simpul yang terhubung
dengan sisi tidak boleh berwarna sama.
·
Memberi warna yang sama
pada simpul yang tidak terhubung langsung.
·
Simpul yang terhubung
dengan sisi, maka jalur tersebut berlaku lampu lalu lintas berwarna hijau
terus.
·
Warna yang digunakan
bebas.
d.
Setelah ketiga langkah
diatas telah diselesaikan, maka langkah terakhir yang harus dikerjakan adalah
mengelompokkan simpul-simpul berdasarkan kesamaan warna. Dan membuat tabel
untuk menentukan mana saja jalur yang lampu lalu lintasnya berwarna merah atau
hijau.
1.2
Hasil
dan Pembahasan
Jadi, berdasarkam langkah-langkah penelitian
diatas, didapatkan dua buah
pewarnaan graf seperti dibawah ini :
a.
Pewarnaan Graf Model
I
Pewarnaan graf untuk jalur busway dipisahkan agar
memudahkan memahami gambar.
Dari model pewarnaan graf diatas, kita mendapatkan 4
kondisi nyala lampu pada perempatan Arion sebagai berikut :
Lampu Merah
|
L2G, H2C, B1G,F2A, B2I, H1A
|
Lampu Hijau
|
F1I, L1C, KD, EJ, BC,
HI, FG, LA
|
Tabel 1 Lampu Lalu Lintas Kondisi 1
Lampu Merah
|
L2G, H2C, F2A, B2I,
F1I,
L1C,
KD, EJ
|
Lampu Hijau
|
H1A,
B1G, BC, HI, FG, LA
|
Tabel 2 Lampu Lalu Lintas Kondisi 2
Lampu Merah
|
L2G, H1A,
F2A,
B1G,
F1I,
L1C,
KD, EJ
|
Lampu Hijau
|
H2C,
B2I, BC, HI, FG, LA
|
Tabel 3 Lampu Lalu Lintas Kondisi 3
Lampu Merah
|
H2C,
H1A, B2I, B1G,
F1I,
L1C,
KD, EJ
|
Lampu Hijau
|
L2G,
F2A, BC, HI, FG, LA
|
Tabel 4 Lampu Lalu Lintas Kondisi 4
Dari 4 kondisi Lampu lalu lintas
diatas, saat lampu merah berubah menjadi lampu hijau kita tinggal menukar
posisi jalur, sehingga jalur yang sebelumnya berlampu merah kita tukar posisi
menjadi jalur berlampu hijau.
b.
Pewarnaan Graf Model
II
Seperti pada Model I, pada Model II pun pewarnaan graf
untuk jalur busway dipisahkan.
Dari model pewarnaan graf diatas, kita mendapatkan 5
kondisi nyala lampu pada perempatan Arion sebagai berikut:
Lampu Merah
|
H2C,
H1A, B2I, B1G,
F1I,
F2A, KD, EJ
|
Lampu Hijau
|
L2G,
L1C, BC, HI, FG, LA
|
Tabel 5 Lampu Lalu Lintas Kondisi 1
Lampu Merah
|
L1C,
L2G, B2I, B1G,
F1I,
F2A, KD, EJ
|
Lampu Hijau
|
H2C,
H1A, BC, HI, FG, LA
|
Tabel 6 Lampu Lalu Lintas Kondisi 2
Lampu Merah
|
H2C,
H1A, B2I, B1G,
L2G, L1C,
KD, EJ
|
Lampu Hijau
|
F1I,
F2A, BC, HI, FG, LA
|
Tabel 7 Lampu Lalu Lintas Kondisi 3
Lampu Merah
|
H2C,
H1A, L1C, L2G,
F1I,
F2A, KD, EJ
|
Lampu Hijau
|
B2I,
B1G, BC, HI, FG, LA
|
Tabel 8 Lampu Lalu Lintas Kondisi 4
Lampu Merah
|
H2C,
H1A, B2I, B1G,
F1I,
L1C,
F2A, L2G
|
Lampu Hijau
|
KD,
EJ, BC, HI, FG, LA
|
Tabel 9 Lampu Lalu Lintas Kondisi 5
Dari 5 kondisi Lampu lalu lintas diatas, saat lampu merah
berubah menjadi lampu hijau kita tinggal menukar posisi jalur, sehingga jalur
yang sebelumnya berlampu merah kita tukar posisi menjadi jalur berlampu hijau.
Model Pewarnaan graf yang kedua ini adalah model nyata yang dipakai di
perempatan Arion.
Kesimpulan
Teori
graf merupakan pokok bahasan yang sudah lama, tapi sampai sekarang masih
memiliki terapan di berbagai persoalan dalam kehidupan sehari-hari. Salah satu
ontohnya adalah penggunaan pewarnaan graf pada pengaturan lampu lalu lintas di
persimpangan jalan.
Masalah pembuatan
lampu lalu lintas dapat dimodelkan dalam bentuk graf. Untuk mencari solusi dari
permasalahan pengaturan warna lampu lalu lintas dapat di gunakan teknik
pewarnaan simpul pada graf.
Untuk penyelesaian
dari pengaturan warna pada lampu lalu lintas di persimpangan Arion dapat
menghasilkan dua alternatif. Salah satu alternatif tersebut sudah digunakan
pada persimpangan Arion secara nyata
- repost from = http://www.slideshare.net/nidashafiyanti/penggunaan-teori-graf-pada-pengaturan-lampu-lalu-lintas
Tidak ada komentar:
Posting Komentar