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]