Referanseside · Kapittel 25

Begreper & formler

Alle nøkkelbegrepene og formlene fra Maksimum flyt, 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.

01Flyt

Mengde som sendes gjennom grafens kanter uten å overskride kapasitet.

02Kapasitetsbegrensning

Hver kant har en maksimal flytverdi $c (u, v)$ .

03Flytbevaringslov

Summen inn til en node (bortsett fra kilde/sluk) = summen ut.

04Residualgraf

Graf som viser hvor mye kapasitet som gjenstår for hver kant.

05Augmenterende sti

En vei fra kilde til sluk med ledig kapasitet.

Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.

\forall v \in V - {s, t} : u \sum f (u, v) = u \sum f (v, u)

f^{*} = c (S, T)

O (E ∣ f^{*} ∣)