Viikon 11 aiheena on virtauslaskenta. KKKK luku 20.

Vinkkejä tehtäviin:

Nettiyhteys

[hint]Tehtävässä pitää koodata maksimivirtauksen laskeminen[/hint]

Seuranhaku

[hint]Tehtävässä pitää koodata maksimiparituksen laskeminen[/hint]

Pakomatka

[hint]Tehtävässä pitää laskea minimileikkaus. Minimileikkauksen saa kun tekee maksimivirtauksen Ford-Fulkersonilla ja jakaa verkon kahteen osaan - solmuihin joihin on reitti lähteestä residual verkossa ja solmuihin joihin ei ole reittiä lähteestä residual verkossa. Tämä selitys on myös KKKK:ssa[/hint]

Lentoasema

[hint]Maksimivirtauksen jossa solmuilla on kapasiteettirajoite saa tehtyä jakamalla jokaisen solmun kahteen solmuun: solmuun johon menee tähän tulevat kaaret ja solmuun josta lähtee tästä lähtevät kaaret.[/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]