Pengembangan Perangkat Lunak untuk Mengkonstruksi Pewarnaan Titik pada Graf Fuzzy dan Aplikasinya pada Pengaturan Lampu Lalu Lintas
TUGAS AKHIR
Diajukan untuk memenuhi persyaratan Sidang Sarjana Matematika
Disusun Oleh : Angga Dinan A NIM : 10102066
Dosen Pembimbing : Dr. M. Salman A.N.
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2007
Abstract
Abstract Let G = (V , E μ ) be a fuzzy graph, V is the set of vertex, the fuzzy edge set
E μ
is characterized by the matrix
μ = ( μij )i , j∈V
where
μij = μ E ({i, j}) ,
∀i, j ∈ V , i ≠ j. A vertex coloring technique is assigned to the fuzzy graph G . A
model and an algorithm are also created to construct a vertex coloring on fuzzy graphs and its application on the traffic lights problem. The model and algorithm created supposedly give a contribution for a better traffic lights management.
Keywords : fuzzy set, fuzzy graph, vertex coloring, backtracking.
i Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas
Abstrak
Abstrak Graf kabur G = (V , E μ ) terdiri dari himpunan tidak kosong V, disebut himpunan titik, dan himpunan E μ , disebut himpunan sisi kabur, yang dapat dikarakteristikkan
oleh
matriks
μ = ( μij )i , j∈V
dengan
μij = μ E ({i, j}) ,
∀i, j ∈ V , i ≠ j. Dalam tugas akhir ini diperkenalkan suatu teknik pewarnaan titik
pada graf kabur G . Selain itu, disusun pula suatu model dan algoritma untuk mengkonstruksi suatu pewarnaan titik pada graf kabur tersebut dan aplikasinya pada pengaturan lampu lalu lintas. Model dan algoritma yang dihasilkan diharapkan memberikan suatu kontribusi dalam pengaturan lampu lalu lintas yang lebih baik lagi dari pengaturan lampu lalu lintas yang berjalan saat ini. Kata kunci : himpunan kabur, graf kabur, pewarnaan titik, backtracking.
ii Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas
Prakata
Prakata Alhamdulillah, puji dan syukur kehadirat Allah SWT, yang telah memberikan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan tugas akhir ini tepat pada waktunya. Tugas akhir ini disusun untuk memenuhi salah satu syarat kelulusan pada Program Studi Matematika, Institut Teknologi Bandung. Tugas Akhir ini berjudul ”Pengembangan Perangkat Lunak untuk Mengkonstruksi Pewarnaan Titik pada Graf Fuzzy dan Aplikasinya pada Pengaturan Lampu Lalu Lintas”. Dalam tugas akhir ini dibahas mengenai bagaimana memodelkan pengaturan lampu lalu lintas menggunakan coloring fuzzy graph sebagai solusi serta penyusunan suatu algoritma untuk mengkonstruksi pewarnaan titik pada graf fuzzy dan aplikasinya pada pengaturan lampu lalu lintas. Banyak pihak yang telah memberikan bantuan kepada penulis dalam pengerjaan tugas akhir ini baik secara langsung maupun tidak langsung. Oleh karena itu, pada kesempatan ini penulis ingin mengucapkan terimakasih kepada: 1. Kedua orang tua tercinta untuk kasih sayang, do’a serta pendidikan akan arti hidup yang diberikan pada penulis tanpa bosan dan tanpa hentinya. 2. Dr. M. Salman A.N. selaku dosen pembimbing yang memberikan bimbingan dan arahan dalam mengerjakan tugas akhir ini. 3. Dr. Rinovia S. dan Dr. Djoko S. selaku dosen penguji yang memberikan banyak masukan terhadap tugas akhir ini. 4. Dr. Ahmad Muchlis selaku dosen wali penulis yang sangat memperhatikan perkembangan mahasiswa walinya. 5. Semua dosen yang telah mengajarkan ilmunya kepada penulis baik akademis ataupun masalah kehidupan.
iii Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas
Prakata
6. Teteh dan keluarga besar penulis untuk doa dan harapan-harapannya. 7. Arya Adriansyah selaku teman, sahabat sekaligus saudara seperjuangan penulis yang paling berharga. 8. Ibu Diah selaku orang tua di lingkungan kampus yang tak pernah bosan membantu masalah akademis yang dihadapi oleh penulis. 9. Teman-teman satu bimbingan: Indra, Mega, Cima, Syarif dan Samuel. Sukses buat kalian juga. 10. Para tutor delphi: Haris, Fizan dan Erdi. Program penulis tak ada artinya tanpa arahan dari kalian. 11. Adik-adik penulis dengan keanekaragaman kelucuannya: Abel, Dd Lina, Dira, Titin, Napit dan Prima. 12. Wulan, Nadia, Randut, Yudha, Sulun, Prames, Iqs, Amru, Na-One, Aim, Erda, Adines, Kang Memen, SOE, Rian, Ludia, Moniq, Citra, Merlin, Niken, Sangga, Pandu, Birrie, Uthie, Fiska, Tape, Ghozi, Nta, Agus FO, Chi-q, Fajar O, Hadi, Echa, Eka, Lido, Kun, Hendrik, Cica, Bowo, Anggun, Adit, Riswan, Jo, Maliki, Febri, Novi, Opik, Onta, Imam atas pelajaran hidup dari kalian semua. 13. Ma’02: Sean, Tutur, Galih, Aji, Julius, Dengara, Allan, Fajar S, Febri, Rahmat, Wiena, Fifi, Irwin, Marses, Dapit, Mardianto, Zaki, Hendra dan teman-teman lain yang tidak bisa penulis tuliskan satu per satu. Terima kasih atas kerjasamanya selama ini. 14. Anak-anak Math: Ma’03, Ma’04, Ma’05. Maaf jika penulis tidak bisa menuliskan nama kalian satu per satu. 15. Kang Dedi, Kang Yana, Bu Nely dan staf serta karyawan TU lainnya.
iv Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas
Prakata
Karena keterbatasan kemampuan dari penulis, tentunya dalam tugas akhir ini masih banyak terdapat kekurangan. Oleh karena itu, penulis mengharapkan segala kritik dan saran dari pembaca sehingga dapat menjadi masukan yang berharga. Akhir kata, harapan penulis semoga tugas akhir ini dapat bermanfaat untuk menambah wawasan dan pengetahuan.
Bandung, September 2007
Penulis
v Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas
Daftar Isi
Daftar Isi Abstract ......................................................................................................................i Abstrak.......................................................................................................................ii Prakata........................................................................................................................iii Daftar Isi ....................................................................................................................vi 1. Pendahuluan.........................................................................................................1 1.1. Latar Belakang .... .........................................................................................1 1.2. Rumusan Masalah.........................................................................................3 1.3. Batasan Masalah ...........................................................................................3 1.4. Tujuan dan Manfaat ......................................................................................3 1.5. Metode dan Teknik Penelitian ......................................................................4 1.6. Sistematika Penulisan ...................................................................................4 2. Konsep Dasar .......................................................................................................5 2.1. Definisi Graf .................................................................................................5 2.2. Himpunan Kabur (Fuzzy Set)........................................................................7 2.2.1. Operasi Himpunan Kabur ....................................................................8 2.2.2. Fungsi Keanggotaan.............................................................................9 2.2.3. Variabel Linguistik ..............................................................................13 2.3. Graf Kabur (Fuzzy Graph)............................................................................15 2.4. Pewarnaan Titik ............................................................................................18 2.5. Pewarnaan Titik Graf Fuzzy .........................................................................19 2.6. Algoritma Pewarnaan Titik...........................................................................23 3. Model Matematika ..............................................................................................34 3.1. Model Matematika Lampu Lalu Lintas ........................................................34 3.2. Model Matematika Lampu Lalu Lintas Daerah Pertigaan Sukajadi.............41 3.3. Model Matematika Lampu Lalu Lintas Daerah Perempatan Merdeka.........47 4. Penyusunan Algoritma.........................................................................................55 4.1. Penyusunan Algoritma..................................................................................55 4.2. Simulasi Program untuk Beberapa Kasus Permasalahan Lampu Lalu vi Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas
Daftar Isi
Lintas....................................................................................................................64 4.2.1. Implementasi Algoritma ......................................................................64 4.2.2. Simulasi Program untuk Permasalahan Sederhana Lampu Lalu Lintas..............................................................................................................66 4.2.3. Simulasi Program untuk Permasalahan Sederhana Lampu Lalu Lintas Daerah Pertigaan Sukajadi..................................................................68 4.2.4. Simulasi Program untuk Permasalahan Sederhana Lampu Lalu Lintas Daerah Perempatan Merdeka..............................................................70 5. Kesimpulan ..........................................................................................................73 Daftar Pustaka............................................................................................................74
vii Algoritma pewarnaan titik pada graf dengan sisi kabur untuk pengaturan lampu lalu lintas
