Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Maksimal flyt, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En rettet graf med kapasiteter på kantene, en kilde s og et sluk t.
En tilordning av verdier til kantene som respekterer kapasitetene og bevarer flyt i hver indre node.
En hjelpegraf som viser hvor mye mer flyt hver kant tåler, inkludert bakoverkanter for å angre flyt.
En sti fra kilde til sluk i restnettet der vi kan øke flyten. Ford-Fulkerson finner slike til ingen finnes.
En oppdeling av nodene i en kilde-side S og en sluk-side T; kapasiteten er summen av kantene fra S til T.
Teoremet som sier at den maksimale flyten er lik kapasiteten til det minste snittet.
Metoden som gjentatt finner en forøkende sti og øker flyten langs den til ingen flere finnes.
Å parre noder fra to disjunkte mengder; løses ved å modellere det som et flytnett.
Ford-Fulkerson der hver forøkende sti velges som korteste sti i restnettet (funnet med BFS). Det gir et polynomielt antall iterasjoner, O(V·E^2), uavhengig av kapasitetene.
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Kapasitetsbegrensning
Flyten på en kant kan ikke overstige kapasiteten, og er ikke-negativ. En av de definerende betingelsene for en gyldig flyt.
Flytbevaring
For hver node utenom kilde og sluk er innflyt lik utflyt — ingenting lekker ut eller oppstår underveis.
Restkapasitet
Hvor mye mer flyt en kant tåler i restnettet. Brukte kanter får i tillegg en bakoverkant med kapasitet lik nåværende flyt.
Maks-flyt/min-snitt
Den maksimale flyten gjennom nettet er nøyaktig lik kapasiteten til det minste snittet som skiller kilde fra sluk.
Edmonds-Karp
Ford-Fulkerson der hver forøkende sti velges som korteste vei i restnettet (BFS). Gir et polynomielt antall iterasjoner uavhengig av kapasitetene.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Definere et flytnett og en gyldig flyt med kapasitetsbegrensning og flytbevaring, og regne ut flytverdien
- 02Forklare restnettet og bakoverkanter, og hvordan en forøkende sti lar Ford-Fulkerson angre tidligere flyt
- 03Begrunne maks-flyt/min-snitt-teoremet ut fra at en stoppet Ford-Fulkerson etterlater et mettet minste snitt
- 04Modellere bipartitt matching som et flytnett, og forklare hvorfor Edmonds-Karp gir polynomiell kjøretid O(V·E^2)