Minimalt snitt og heltallsteoremet

Et snitt i graf teori er en vilkårlig partisjon av mengder bestående av noder.

---

Begreper

Nettoflyt Kapasitet Heltallsteoremet Fra dette følger

$$|f|\le c(S,T)$$

Hvor $|f|$ er flyt, og $c(S,T)$ er kapasiteten.

Deltemaer

Max-flow min-cut Teoremet Maksimum bipartitt matching