Diskret Optimering.

8. kursusgang, tirsdag den 28. september 12.30-16.15

Forelæsning i G5-110 ved LKJ:

12.30-13.00: Repetition.

14.55-16.15:

Jeg vil afslutte afsnit 6.5 om Floyd-Warshalls algoritme.
Derefter fortsætter vi med strømning, men denne gang handler det ikke om at transportere mest muligt fra s til t. Det handler nu om at transportere en given mængde fra s til t så billigt som muligt. Afsnit 7.1, 7.2 og 7.3 gennemgås.

Opgaveregning:

Opgave A: Find ved hjælp af Ford-Fulkerson algoritmen en maksimum s-t strømning i netværket vist nedenfor. Find også et snit med minimum kapacitet.
Opgave B: Vis at hvis hver kant e har heltallig kapacitet b(e) så findes der en maksimum strømning f, så f(e) er et helt tal for enhver kant e.

Opgaver i Kapitel 6: 7, 8, 10.