Penyelesaian masalah maksimum flow dengan menggunakan algoritma preflow push / Amalia Ika Prativi
| Main Author: | Amalia Ika Prativi |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2009
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/16755/ |
Daftar Isi:
- Teorigraphmerupakansalahsatucabangmatematikayangpentingdanbanyakmodelteorigraphyangdapatditerapkanadalahmasalahmaksimumflowyaitumasalahbagaimanacaramenentukanbesarnyapenugasanflowpadasuatujaringankerjasehinggaflowyangsampaiketujuanmaksimal.Penyelesaianmasalahmaksimumflowdapatlebihmudahdanefisienjikamenggunakanalgoritma.DuaalgoritmayangsudahadadanseringdigunakanyaitualgoritmaLintasanPenambahdanalgoritmaPelabelanAka.Operasidasarkeduaalgoritmatersebutadalahsamayaituberulang-ulangmencarisuatulintasandarititiksumberketitiktujuandanmenghitungnilaikapasitassisaannyayangdigunakanuntukmengembangkanflowpadalintasanyangterpilihtersebut.Perulanganberhentijikatidakadalagilintasandarititiksumberketitiktujuan.PadaskripsiinidisampaikansuatualternatifalgoritmayaitualgoritmayangoperasidasarnyaberbedadenganduaalgoritmatersebutyaitualgoritmaPreflowPush.Operasidasarnyayaituselalumemeriksasetiaptitikdenganexcesspositifdantitikdenganlabeljarakterbesartanpamenentukanlintasandarititiksumberketitiktujuan.Prosesnyadiawalidenganpelabelanjaraksemuatitikpenyerapansisisjolehtitiksumberdenganmemindahkankapasitassisisjkeexcesstitikyangdekatdengantitiksumberdanpelabelanjarakbaruuntuktitiksumber.Kemudianberulang-ulangmemilihtitikaktifidanmenentukansisiadmissibleij.Jikasisiadmissibleijtidakadamakadilakukanpelabelanjarakbarutitiki.LalumencarinilaikapasitassisaanPreflowPushuntukmengembangkanflowdisepanjangsisiadmissibleijexcesstitikidantitikjpadajaringankerja.Perulanganberhentijikatidakadalagititikaktifpadajaringankerjatersebut.UntukmempermudahpenyelesaianmasalahmaksimumflowdenganalgoritmaPreflowPushLintasanPenambahdanalgoritmaPelabelanAkadigunakankomputerdenganprogramGIDENyanghasilnyadisertakanpadaLampiran.DalammenyelesaikanmasalahmaksimumflowalgoritmaPreflowPushmemerlukanprosesyanglebihlamadibandingkanalgoritmaLintasanPenambahdanalgoritmaPelabelanAka.TapialgoritmaPreflowPushdapatlebihspesifikdantelitikarenaselalumemeriksatitikpadajaringankerjayangmempunyaiexcesspositifdantitikyangmempunyailabeljarakterbesar.