Penerapan pewarnaan simpul graph dengan metode Greedy pada pengaturan pola lampu lalu lintas di persimpangan jalan / Christian Yacobus Wanne
| Main Author: | Wanne, Christian Yacobus |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2011
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17029/ |
Daftar Isi:
- KatakuncipewarnaansimpulbilangankromatikalgoritmagreedypengaturanpolalampulalulintasDalamTeoriGraphmasalahpewarnaangraphterdiridaritigamacamyaitupewarnaansimpulpewarnaansisidanpewarnaanpeta.Teknikpewarnaansimpulmerupakansalahsatusubyekyangmenarikdalambidanggraph.Pewarnaansimpuladalahmewarnaisemuasimpulsuatugraphsehinggasetiappasangsimpulyangterhubunglangsungdiberiwarnayangberbeda.SedangkanjumlahwarnaminimumyangdiperlukandisebutbilangankromatikTerdapatbeberapaalgoritmayangdigunakanuntukmenemukanbilangankromatiksuatugraph.SalahsatualgoritmayangdapatdigunakanadalahAlgoritmaGreedy.Aplikasidariteknikinitelahbanyakditerapkandiberbagaibidang.Salahsatupermasalahanyangdapatdiselesaikandenganmenggunakanpewarnaansimpulgraphadalahpengaturanpolalampulalulintasdipersimpanganjalan.LangkahawalpewarnaansimpulgraphdenganAlgoritmaGreedyyaitumengurutkansimpuldariderajattertinggisampaiyangterendah.Simpuldenganderajattertinggidiwarnaiterlebihdahulukemudiandiperiksasimpulyangtidakterhubungdengansimpulpertamauntukdiberiwarnayangsama.Jikatidakadadipilihsimpuldenganderajattertinggiyangbelumdiwarnauntukdiberiwarnayangbarukemudiandiperiksakembalisimpulyangtidakterhubunguntukdiberiwarnayangsama.Langkahtersebutdilanjutkanhinggasemuasimpultelahdiwarnai.PenerapanalgoritmaGreedypadapengaturanpolalampulalulintasdimulaidenganmerepresentasikanpersimpanganjalankedalambentukgraph.Setiaparuskendaraanpadapersimpanganjalandirepresentasikansebagaisimpul.Untuksetiaparuskendaraanyangtidakkompatibelmakasimpulyangmerepresentasikanaruskendaraantersebutdihubungkandengansuatusisi.DenganbentukgraphtersebutmakapengaturanpolalampulalulintasdapatlebihmudahdiselesaikandenganpewarnaansimpulgraphdenganmetodeGreedy.Outputdaripewarnaansimpulgraphadalahbanyaknyawarnayangdigunakanuntukmewarnaisimpulgraph.Padapengaturanpolalampulalulintasbanyaknyawarnayangdiperlukanuntukmewarnaisimpulgraphdigunakanuntukmenentukanbanyakanyafaseyangdiperlukandalamsatusiklus.Simpulyangtidakterhubungdengansimpulyanglainadalaharusyangkompatibeldengansemuaarussehinggaselalubergerakdalamtiapfasesedangkansimpul-simpuldenganwarnayangsamamerupakanalihgerakkendaraanyangdapatbergerakbersamadalamsatufase.Dengandemikiantidakadaalihgerakyangtidakkompatibelyangbergerakpadafaseyangsamasehinggatidakterjadipenumpukankendaraanditengahpersimpangan.SelaindenganperhitunganmanualpadapenelitianinidibuatimplementasiprogramdengansoftwareDelphi7.Dariperhitungansecaramanualdanperhitungandenganprogramuntukcontohgraphdengan8simpuldiperolehhasilyangsama.Demikianpulapadapenerapanpengaturanpolalampulalulintaspadapertigaandanperempatandiperolehhasilyangsama.