Penggunaan Teori Graf pada Pengaturan Lampu Lalu Lintas di Persimpangan Arion

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.

        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 B₁B₂, H₁H₂, dan L₁L₂ akan menyala bersama, lampu L₂ akan menyala merah lebih cepat dibandingkan L₁, demikian juga dengan lampu F₂ akan menyala merah lebih cepat dibandingkan F₁.  Mobil di jalur J ke E dan K ke D (jalur TransJakarta) akan diperbolehkan jalan jika lampu di F₂ dan L₂ 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