Penyelesaian masalah aliran maksimum menggunakan Edmons Karp Algorithm / Fathimatuzzahro
| Main Author: | Fathimatuzzahro |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2013
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17201/ |
Daftar Isi:
- Fathimatuzzahro.2013.PenyelesaianMasalahAliranMaksimumMenggunakanEdmonsKarpAlgorithm.Skripsi.JurusanMatematikaFakultasMatematikadanIlmuPengetahuanAlamUniversitasNegeriMalang.Pembimbing(I)Dra.SaptiWahyuningsihM.Si(II)DarmawanSatyanandaS.TM.TKataKuncialiranmaksimumedmonskarpedmonskarpalgorithmMaximumflowproblemdideskripsikansebagaimasalahpencarianarusmaksimum(flowmaximum)yangdapatmengalirpadasebuahnetworkyanghanyamemilikisatusumber(source)dansatutujuan(sink).TerdapatbeberapaalgoritmayangdapatdigunakanpadapenyelesaianmaximumflowproblemsalahsatualgoritmayangmasihjarangdigunakanadalahalgoritmaEdmonsKarp.AlgoritmaEdmonsKarpmerupakanpenyempurnaandarialgoritmaFordFulkersonyaknipembatasandalampencarianlintasanresidualnya.DalamalgoritmaEdmonsKarplintasanyangdipilihmerupakanlintasanyangterpendek.UntukmemilihlintasanpenambahterpendekyangdimaksuddigunakanalgoritmaBreadthFirstSearch(BFS).AlgoritmaEdmonsKarpinidimulaidenganinisialisasisemuaalirandengannol.DilanjutkandenganpencarianlintasanpenambahterpendekdarisketdenganmenggunakanalgoritmaBFS.Jikadiperolehlintasanpenambahterpendekdilanjutkandenganpencariankapasitasresidupadalintasantersebutyangdinotasikandengan916.Setelahdidapatkan916tambahkanpadaaliransepanjanglintasantersebutsebesar916.Jikatidakditemukanlintasanpenambahterpendeklagimakaalgoritmaberhenti.Dari3contohyangdibahasdalambabIIIdapatdisimpulkanbahwacaradalammenambahkanalirankedalamlintasanpenambahdansolusiyangdiperolehhasilnyasamasedangkanperbedaanalgoritmaFordFulkersondanalgoritmaEdmonsKarphanyaterletakpadalangkahke-3yaitudalampemilihanlintasanpenambah.PadaalgoritmaEdmonsKarpdigunakanalgoritmaBFSuntukpemilihanlintasanpenambahterpendeknamunpadaalgoritmaFordFulkersontidakmenggunakanstandarkhususdalampemilihanlintasanpenambahnya.ImplementasiprogramdarialgoritmaEdmonsKarpiniadalahprogramDelphidenganinputnyaberupainputtitikkapasitastitiksumberdantitiktujuan.Hasilyangdiperolehberuparesidualnetworkbesertaflowmaksimumdalamnetworktersebut.Berdasarkanujicobayangtelahdilakukanpadabeberapanetworkdenganmenggunakan5617dan41titikprogramyangtelahdibuatsangatmembantudalammenyelesaikanpermasalahanmaximumflowkhususnyadenganbanyaktitik.