Penentuan matching maksimal dan matching maksimum pada graph sederhana / Irawati Dwi Anggraeni
| Main Author: | Anggraeni, Irawati Dwi |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2010
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/17744/ |
Daftar Isi:
- ABSTRAKAnggraeniIrawatiDwi.2009.PenentuanMatchingMaksimaldanMatchingMaksimumpadaGraphSederhana.SkripsiJurusanMatematikaFMIPAUniversitasNegeriMalang.Pembimbing(I)Prof.Drs.PurwantoPh.D(II)Dr.SubanjiS.PdM.Si.KataKunciMatchingMatchingMaksimalMatchingMaksimumTeorigraphmerupakansalahsatucabangmatematikayangmenarikuntukdibahas.Penggunaanteorigraphdalamkehidupannyatasudahcukupbanyakdilakukandimasyarakat.Salahsatucontohpenerapannnyaadalahuntukmasalahpenugasan(assignmentproblem).Pokokbahasandalamteorigraphyangdigunakanuntukmenyelesaikanmasalahpenugasaniniadalahmatching.Matchingdalamgraphadalahhimpunansisi-sisiyangnonadjacentdimanatidakadaduasisiyangmempunyaititikakhirsama.Matchingmaksimaldalamgraphadalahmatchingyangukurannyatidakdapatdiperbesar.UntukmenentukanmatchingmaksimalpadasuatugraphdapatdigunakansebuahalgoritmasebagaialatbantuyaitualgoritmaGreedy.Matchingmaksimumdalamgraphadalahmatchingdenganukuranpalingmaksimum(palingbanyak).UntukmenentukanmatchingmaksimumpadasuatugraphdapatdigunakansebuahalgoritmasebagaialatbantuyaitualgoritmaEdmonds.Setiapmatchingmaksimumpastimaksimaltetapitidaksemuamatchingmaksimalpastimaksimum.AlgoritmaGreedypadapencarianmatchingmaksimaldanalgoritmaEdmondspadapencarianmatchingmaksimumdapatdigunakanuntukmemcahkanmasalahdalamkehidupansehari-harimisalkanpadapenentuanpasanganpegawaiyangdapatbekerjasamadalamsuatukantoruntukmenentukanpasanganpekerjayangdapatberkolaborasidalammenyelesaikansebuahproyekdanjugauntukmenentukandaerahyangdapatdikunjungisalesagarpengirimanbaranglebihoptimal.