Penyelesaian masalah pewarnaan simpul pada graph dengan algoritma gabungan dan implementasinya / Nia Prastuti Ardhian
| Main Author: | Ardhian, Nia Prastuti |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2010
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/16903/ |
Daftar Isi:
- ABSTRAKArdhianNiaPrastuti.2010.PenyelesaianMasalahPewarnaanSimpulpadaGraphdenganAlgoritmaGabungandanImplementasinya.SkripsiJurusanMatematikaFMIPAUniversitasNegeriMalang.Pembimbing(I)Dra.SaptiWahyuningsihM.Si(II)DarmawanSatyanandaS.TM.TKatakuncipewarnaansimpulbilangankromatikalgoritmagabunganpenjadwalanujianDalamTeoriGraphmasalahpewarnaangraphterdiridaritigamacamyaitupewarnaansimpulpewarnaansisidanpewarnaanwilayah.Teknikpewarnaansimpulmerupakansalahsatusubyekyangmenarikdalambidanggraph.Pewarnaansimpuladalahmewarnaisemuasimpuldisehinggasetiappasangsimpulyangterhubunglangsungdiberiwarnayangberbeda.JumlahwarnaminimumyangdiperlukandisebutbilangankromatikTerdapatbeberapaalgoritmaheuristikyangdigunakanuntukmenemukanbilangankromatiksuatugraph.DiantaranyaadalahAlgoritmaFirstFit(FF)LargestDegreeOrdering(LDO)SaturatedDegreeOrdering(SDO)danIncidentDegreeOrdering(IDO).Teknikinimemusatkanbagaimanacarapengambilansimpulyangakandiwarnaiberikutnyasecarahati-hati.Aplikasidariteknikpewarnaansimpultelahbanyakditerapkandiberbagaibidangyangmemilikikarakteristikyanganalogdenganmasalahpewarnaansimpul.Salahsatunyaadalahpenentuanjadwalujian.Diperlukansuatumetodeyanglebihbaikdarialgoritmaheuristikuntukmenemukanbilangankromatiksuatugraph.SalahsatunyaadalahAlgoritmaGabungan.LangkahpertamapadaAlgoritmaGabunganadalahmembangunspanningtree.Padaakhirlangkahinispanningtreedapatdiwarnaidenganduawarna.Langkahberikutnyaadalahmemeriksasisi-sisiyangbermasalahyaitusisiyangtidaktermasukkedalamspanningtree.Bilawarnakeduasimpulsamamakawarnasalahsatusimpulharusdiubah.UntukmengubahwarnasimpuldigunakanalgoritmamodifikasidariAlgoritmaLargestDegreeOrdering(LDO)danSaturatedDegreeOrdering(SDO).KelebihanmenggunakanAlgoritmaGabunganbiladibandingkandenganmenggunakanpolinomkromatikadalahselainmengetahuibilangankromatikjugadapatdiketahuiwarnayangdiberikanpadasetiapsimpulsehinggakitadapatmenyusunjadwalujiansehinggatidakadajadwalyangbertabrakanyaitutidakadamahasiswayangharusmenempuhduaujiandalamwaktuyangbersamaan.Sekilasterlihatbahwaalgoritmagabunganinimenjadilebihrumittetapiberdasarkanpenelitianyangpernahdilakukanalgoritma-algoritmayangdigabungakanmemilikiefisiensiyanglebihtinggidibandingkandenganmasing-masingalgoritmaheuristikyangberdirisendiri.UntukmenyelesaikanmasalahpenjadwalanujiandibuatprogramyangmenggunakansoftwareDelphi7.BerdasarkanperhitungandenganmenggunakanAlgoritmaGabunganyangdilakukansecaramanualmaupunmenggunakanimplementasiprogramdiperolehhasilyangsama.