penggunaan teori graf pada pengaturan.docx

8/10/2019 PENGGUNAAN TEORI GRAF PADA PENGATURAN.docx

http://slidepdf.com/reader/full/penggunaan-teori-graf-pada-pengaturandocx 1/10

PENGGUNAAN TEORI GRAF PADA PENGATURAN

LAMPU LALU LINTAS DI PERSIMPANGAN ARION

Ambar Mangesti, Nida Shafiyanti, dan Tedy Triyadi3125111212, 3125111218, 3125111202

Universitas Negeri Jakarta

[email protected], [email protected], [email protected]

ABSTRACT

At the crossroads, we need a way to manage traffic lights so that cars can not pass through

the intersection colliding. Traffic lights are arranged so that the car can go with regular. Thereare many solutions to manage the traffic lights at the intersection. In this paper, an example of

the intersection to be set is the intersection of Arion, Rawamangun, East Jakarta and the

solutions using graph theory. Graph theory is used graph coloring technique by coloring

vertices. The knot symbolizes the path used vehicles. Then connect multiple nodes with the

side. After that give a different color to each node the neighboring number of colors used as

little as possible

Keyword : Graph theory , Graph coloring, Intersection, Traffic light, Node

ABSTRAK

Pada persimpangan jalan, dibutuhkan suatu cara untuk mengatur lampu lalu lintas agar mobil

yang melewati persimpangan tersebut tidak mengalami tabrakan. Nyala lampu lalu lintas

diatur sedemikian rupa sehingga mobil bisa berjalan dengan teratur. Ada banyak solusi untuk

mengatur lampu lalu lintas di persimpangan jalan. Pada makalah ini, contoh persimpangan

yang akan diatur adalah persimpangan Arion, Rawamangun, Jakarta Timur dan dengan solusi

menggunakan teori graf. Teori graf yang dipakai adalah teknik pewarnaan graf dengan cara

pewarnaan simpul. Simpul yang dipakai melambangkan jalur yang dilewati kendaraan.

Kemudian menghubungkan beberapa simpul dengan sisi. Setelah itu memberi warna yang

berbeda pada setiap simpul yang bertetanggan dengan jumlah warna yang digunakan

sesedikit mungkin.

Kata kunci : Teori graf, Pewarnaan graf, Persimpangan, Lampu lalu lintas, Simpul

mailto:[email protected]













1. Pendahuluan

1.1 Latar Belakang Perkembangan ilmu pengetahuan dan teknologi terlebih lagi pada masalah transportasi

mengakibatkan produksi kendaraan massal yang yang semakin meningkat. Peningkatan

produksi mobil tersebut membuat kendaraan yang melintas di jalan semakin hari semakin

meningkat. Sehingga timbul banyak masalah seperti kemacetan dan kecelakaan.

Kemacetan atau kecelakaan sering terjadi karena banyak kendaraan yang berjalan tidak

teratur dan sering kali kendaraan berjalan tidak sesuai dengan jalurnya. Hal itu sudah menjadi

hal yang biasa di kota besar seperti Jakarta. Persimpangan jalan adalah salah satu jalur yang

sering mengalami hal-hal tersebut. Banyak kendaraan di persimpangan jalan yang berjalan

semaunya, terutama di jam-jam sibuk para pengemudi kendaraan terkadang akan berjalan

sesuai kemauan mereka tanpa berpikir resiko yang akan mereka dapat.

Oleh karena itu, perlu adanya hal yang mengatur agar hal-hal diatas tidak terjadi. Di

setiap jalan terutama di persimpangan jalan terdapat lampu lalu lintas untuk mengatur

jalannya kendaraan agar tidak terjadi kemacetan atau kecelakaan. Nyala lampu lalu lintas

diatur sedemikian rupa sehingga kendaraan bisa berjalan teratur tanpa terjadi tabrakan antar

kendaraan yang melintas di jalan tersebut.

Persimpangan Arion merupakan salah satu persimpangan yang banyak dilewati

kendaraan karena merupakan salah satu akses jalan untuk pergi ke sekolah, kampus, pasar,

atau bekerja. Pada setiap persimpangan terdapat satu buah lampu lalu lintas. Dan

persimpangan ini pun dilewati jalur busway yang memiliki lampu lalu lintas sendiri. Perlu

pengaturan lampu lalu lintas yang baik, karena di persimpangan Arion sering terjadi

kemacetan yang terkadang disebabkan kendaraan yang berjalan semaunya.

Banyak cara untuk mengatur lampu lalu lintas, salah satunya adalah teori graf. Di dalam

teori graf terdapat beberapa teknik penyelesaian masalah. Salah satu teknik yang bisa

dilakukan untuk memecahkan masalah diatas adalah teknik pewarnaan graf. Dari latar

belakang diatas, penulis mengangkat judul “Penggunaan Teori Graf pada Pengaturan

Lampu Lalu Lintas di Persimpangan Arion”.

1.2 Rumusan Masalah

Dari latar belakang diatas, dapat kita rumuskan masalah :

a.

Bagaimana cara mengatur lampu lalu lintas di persimpangan Arion?



b. Bagaimana aplikasi teknik pewarnaan graf pada pengaturan lampu lalu lintas di

persimpangan Arion?

1.3 Tujuan Penulisan

Tujuan penulisan ini adalah :

a.

Untuk mengetahui cara mengatur lampu lalu lintas di persimpangan Arion

b. Untuk mengetahui aplikasi teknik pewarnaan graf pada pengaturan lampu lalu lintas

di persimpangan Arion.

2. Pembahasan

2.1 Landasan Teori

2.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.

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

Gambar 3 Contoh Graf Ganda



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.

2.1.2

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.

2.2 Metode Penelitian

2.2.1 Model Perempatan Jalan

Model perempatan jalan yang dibahas adalah perempatan jalan Arion, Rawamangun,

Jakarta Timur.

Gambar 4 Model Perempatan Jalan Arion

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.

2.2.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.

2.3

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 :

Tabel 1 Lampu Lalu Lintas Kondisi 1




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

Lampu Merah L2G, H2C, B1G,F2A, B2I, H1A

Lampu Hijau F1I, L1C, KD, EJ, BC, HI, FG, LA

Lampu Merah L2G, H2C, F2A, B2I, F1I, L1C, KD, EJ

Lampu Hijau H1A, B1G, BC, HI, FG, LA

Lampu Merah L2G, H1A, F2A, B1G, F1I, L1C, KD, EJ

Lampu Hijau H2C, B2I, BC, HI, FG, LA

Lampu Merah H2C, H1A, B2I, B1G, F1I, L1C, KD, EJ

Lampu Hijau L2G, F2A, BC, HI, FG, LA

Gambar 5 Pewarnaan Graf Model 1

(kanan : pewarnaan graf jalur busway, kiri : pewarnaan graf jalur kendaraan bermotor lain)



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

Lampu Merah L1C, L2G, B2I, B1G, F1I, F2A, KD, EJ

Lampu Hijau H2C, H1A, BC, HI, FG, LA

Lampu Merah H2C, H1A, B2I, B1G, L2G, L1C, KD, EJ

Lampu Hijau F1I, F2A, BC, HI, FG, LA

Lampu Merah H2C, H1A, L1C, L2G, F1I, F2A, KD, EJ

Lampu Hijau B2I, B1G, BC, HI, FG, LA

Lampu Merah H2C, H1A, B2I, B1G, F1I, L1C, F2A, L2G

Lampu Hijau KD, EJ, BC, HI, FG, LA

Gambar 6 Pewarnaan Graf Model 2

(kanan : pewarnaan graf jalur busway, kiri : pewarnaan graf jalur kendaraan bermotor lain)



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.

3. 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.

Daftar Pustaka

Firouzian, Siamak dan Mostafa Nouri Jouybari. (2011). “Coloring Fuzzy Graphs and Traffic

Light Problem”, Journal of Mathematics and Computer Science, Vol II, No.3.

Imron, Chairul. (2010). “Studi Akibat Persimpangan Jalan”, Simposium III FSTPT.

Nugroho, Andreas Dwi. (2012). “Aplikasi Pewarnaan Graf pada Pengaturan Warna Lampu

Lalu Lintas”, Makalah IF2091 Struktur Diskrit.

penggunaan teori graf pada pengaturan.docx

Documents