Oppgave 10 i kont 2015 sier: Hvis vi øker kapasiteten til hver enkelt kant i et flytnettverk med , vil verdien til den maksimale flyten alltid øke med et multiplum av ? 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 . Men om vi krever at det skal gå an å nå fra , så kan vi f.eks. sette opp en flaskehals, slik:

Om vi øker alle kapasitetene med så øker flyten med :