Referanseside · Kapittel 27
Begreper & formler
Alle nøkkelbegrepene og formlene fra Maksimal bipartitt matching, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Øv med flashcards8 kort fra dette kapittelet
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
01Bipartitt graf
Nodene kan deles i to disjunkte mengder og der alle kanter går mellom mengdene.
03Augmenterende sti
Sti som starter og slutter i frie (u-parrede) noder og som veksler mellom kanter utenfor/innenfor matchingen.
04Maksimal vs. maksimum
Maksimal: kan ikke utvides lokalt; maksimum: størst mulig kardinalitet.
05Hopcroft–Karp
Algoritme som finner maksimum matching i ved å søke flere disjunkte augmenterende stier per fase.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.