Virtaukset ja niiden sovelluksia

Abstract

Tässä tutkielmassa perehdytään verkostoihin ja niihin määriteltyihin virtauksiin. Virtaus on funktio, joka liittää jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon ja toteuttaa tietyt ehdot. Ensinnäkin, jokaiselle suunnatulle sivulle tulee päteä, että vastakkaiselle suunnatulle sivulle virtauksen arvo on yhtä suuri mutta eri merkkinen. Toiseksi jokaisesta kärjestä lähde ja nielu poislukien on lähdettävä virtausta yhtä paljon kuin siihen on saapunut. Lähde on se kärki, josta virtaus lähtee liikkeelle, ja nielu on kärki, johon virtaus lopulta päätyy. Kolmanneksi virtauksen arvon on oltava jokaisessa suunnatussa sivussa korkeintaan yhtä suuri kuin vastaava kapasiteettifunktion arvo. Kapasiteettifunktio liittää jokaiseen verkoston suunnattuun sivuun kokonaislukuarvon, joka kuvaa kunkin suunnatun sivun suurinta mahdollista virtauksen arvoa. Tutkielmassa osoitetaan lause, joka kertoo, että verkoston läpi kulkevan suurimman mahdollisen virtauksen arvo on sama kuin pienimmän leikkauksen kapasiteetin arvo. Tätä Fordin ja Fulkersonin kehittämää lausetta kutsutaan suurin virtaus - pienin leikkaus -lauseeksi. Tätä lausetta hyödynnetään läpi koko tutkielman, ja sen avulla osoitetaan keskeisiä verkkoteorian tuloksia, kuten Königin lause, Hallin lause ja Mengerin lause. Königin lauseen mukaan verkon maksimaalisen sovituksen suuruus on sama kuin pienimmän peitteen suuruus. Hallin lause antaa välttämättömän ja toisaalta riittävän ehdon sille, että kaksiosaiselle verkolle löytyy täydellinen sovitus. Mengerin lause puolestaan antaa verkoston suurimman mahdollisen lukumäärän erillisiä polkuja. Nämä tulokset saadaan osoitettua konstruoimalla verkosta verkosto ja lähettämällä virtausta lähteestä verkoston läpi. Näin voidaan hyödyntää virtauksille ja verkostoille osoitettuja tuloksia.