Tämän viikon aiheena on virtauslaskenta, josta on tietoa KKKK:n luvussa 36.

Huom! Luku 36 ilmestyi KKKK:hon vasta äskettäin, eli saatat joutua lataamaan kirjan uudestaan. Linkki on http://tktl.fi/kkkk, kuten ennenkin.

Vinkit

Lentoasema

[hint]Muuta tarkastuspisteiden verkkoa siten, että jokainen solmu muutetaan kahdeksi kaarella yhdistetyksi solmuksi siten, että kaaren kapasiteetti on tarkastuspisteen kapasiteetti. Käytä maksimivirtausta.[/hint]

Sukukokous

[hint]Binäärihae matkaan kuluva aika. Selvittääksesi, ehtivätkö kaikki perille ajassa t, luo verkko, jossa jokaiselle aseman ja ajanhetken (välillä 0\ldots t) yhdistelmälle on oma solmunsa, eli siis solmuja on yhteensä (t+1)n. Käytä maksimivirtausta.[/hint]

Istumapaikat

[hint]Huomaa, että ongelma on melkein kuin kaksijakoinen maksimiparitus. Ainoana erona on, että jokaiselle solmulle halutaan kaksi paria.[/hint]