Menentukan lintasan terpendek (shortest path) menggunakan algoritma perfect matching minimum / Elly Astutik
| Main Author: | Astutik, Elly |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2011
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17071/ |
Daftar Isi:
- KataKunciShortestPathPerfectMatchingMinimumLintasanterpendek(ShortestPath)merupakansalahsatucabangyangadadalamkonsepgraph.Permasalahanlintasanterpendekadalahpermasalahanmenentukanlintasanminimumdarisuatutitiksketitiktyangdigambarkandalambentukgraphbaikgraphberbobotmaupungraphtidakberbobot.Permasalahanlintasanterpendekdapatdiselesaikandenganalgoritmayangdigunakanuntukmenentukanperfectmatchingminimum.Dalamgraphmatchingdidefinisikansebagaihimpunansisi1198728838119864sedemikianhinggatidakada2sisiyangterkaitdengan1titikyangsamasedangkanperfectmatchingminimumadalahmatchingMdengansetiaptitikdi119881denganterkaittepatsatusisidiMdenganbobotminimum.MenyelesaikanpermasalahanlintasanterpendekpadagraphGmenggunakanalgoritmaperfectmatchingminimumdilakukandenganmentransformasigraphGmenjadigraphHyangmerupakangraphpenggantikemudianmenentukanperfectmatchingminimumpadagraphpenggantiH.TerdapatbeberapaalgoritmayangdigunakandalammenentukanperfectmatchingminimumsalahsatunyaadalahalgoritmaMulmuleyVazirani.AlgoritmaMulmuleyVaziranimerupakanalgoritmayangdikerjakandalambentukmatriksdanmatriksyangdigunakanadalahmatriksTutte.Algoritmainidapatditerapkanpadagraphbipartisimaupungraphnonbipartisi.Padadasarnyalangkahlangkahalgoritmainisamauntukgraphbipartisimaupungraphnonbipartisiperbedaannyaterletakpadaukuranmatriksyangdigunakan.Jikajumlahtitiksuatugraphadalahndangraphtersebutmerupakangraphbipartisimakaukuranmatriksyangdigunakanadalahn/2xn/2jikagraphtersebutmerupakangraphnonbipartisimakaukuranmatriksyangdigunakanadalahnxn.