Oppgave 10 i kont 2015 sier: Hvis vi øker kapasiteten til hver enkelt kant i et flytnettverk med \(k\), vil verdien til den maksimale flyten alltid øke med et multiplum av \(k\)? Begrunn svaret kort.

Hva kan være et eksempel på at dette ikke vil gå?

Basert på et Piazza-spørsmål fra 2015

Slike oppgaver er det ofte svært nyttig å prøve litt på selv! Men: Det enkleste eksemplet er kanskje…

Hvis vi øker kapasiteten på alle kantene (dvs., ingen kanter), så er flyten fortsatt \(0\). Men om vi krever at det skal gå an å nå \(t\) fra \(s\), så kan vi f.eks. sette opp en flaskehals, slik:

Om vi øker alle kapasitetene med \(2\) så øker flyten med \(3\):