© h.hofstede (h.hofstede@hogeland.nl)

De stelling van Menger.
       
Of eigenlijk moet deze les heten de "Stellingen van Menger". Menger bewees namelijk een aantal nuttige stellingen door handig gebruik te maken van de "max-flow min-cut" stelling van de vorige les.

Stelling 1.

Neem een netwerk waarin alle lijnen capaciteit 1 hebben. Dan geldt:
1. De maximale stroomwaarde  is het maximale aantal  lijn-disjuncte paden van B naar P
2. De minimale snede is het minimale aantal verbindingslijnen dat je kunt verwijderen zodat er geen pad van B naar P meer is.
       
       
       
       

© h.hofstede (h.hofstede@hogeland.nl)