Ford–Fulkerson-algoritmi : Virtaussysteemin maksimivirtauksen löytäminen

Abstract

Graafiteoriaa voidaan käyttää työkaluna lukuisten reaalimaailman ongelmien ja tilanteiden mallintamisessa, sillä sitä voidaan hyödyntää aina sosiaalisen median analysoinnista logistiikkaketjujen optimoimiseen. Jälkimmäisen kaltaisiin käyttötarkoituksiin sovelletaan graafiteorian virtaussysteemeitä. Tässä työssä tutustutaan graafiteorian virtaussysteemien maksimivirtauksen selvittämiseen Ford--Fulkerson-algoritmin avulla. Tätä algoritmia hyödyntämällä virtaussysteemeistä voidaan selvittää maksimivirtaus ja virtausta rajoittava "pullonkaula". Tämän tiedon avulla saadaan selvitettyä esimerkiksi olemassa olevan logistiikan infrastuktuurin maksimikapasiteetti ja kehitysalueet, joilla maksimikapasiteettia saadaan kasvatettua.

Tämä työ tarjoaa lukijalle kaikki tarvittavat graafiteorian työkalut Ford--Fulkerson-algoritmin ymmärtämistä ja käyttämistä varten. Työn alussa esitellään oleelliset graafiteorian perusteet, minkä jälkeen esitellään graafien erityistapaukset: puut ja niiden kasvatusalgoritmit.

Tässä työssä tarkasteltavat virtaussysteemit on yksinkertaistettu siten, että systeemeissä on vain ja ainoastaan yksi virtauksen lähdesolmu ja yksi nielusolmu. Kaikki systeemin virtaus alkaa lähteestä ja kulkee systeemin muita solmuja ja kaaria pitkin nieluun. Tätä lähteestä nieluun kulkevaa virtausta kutsutaan systeemin kokonaisvirtaukseksi. Systeemin suurinta mahdollista kokonaisvirtausta kutsutaan maksimivirtaukseksi, jota rajoittavat systeemin yksittäisten kaarien kapasiteettiehdot. Maksimivirtauksen löytämisessä kokonaisvirtausta kasvatetaan niin kauan, että systeemin virtaus kohtaa sitä kuljettavien kaarien kapasiteetit eikä kokonaisvirtausta enää voida kasvattaa.

Systeemin maksimivirtaus on siis suurin mahdollinen siinä kulkevan virtauksen määrä systeemin kaarien kapasiteettien sallimissa rajoissa. Kaarijoukkoa, joka erottaa lähteen ja nielun toisistaan, kutsutaan leikkaukseksi. Sitä lähteen ja nielun erottavaa leikkausta, jonka kaarien yhteenlaskettu kapasiteetti on pienin, kutsutaan virtaussysteemin minimileikkaukseksi. Mikäli systeemissä kulkee maksimivirtaus, minimileikkauksen kaarien koko virtauskapasiteetti on käytössä, eli ne ovat saturoituja. Minimileikkaus on systeemin virtauksen "pullonkaula", jota muuttamalla voidaan vaikuttaa systeemin maksimivirtaukseen.

Virtaussysteemien käsittelyn jälkeen käydään läpi perusteellisesti Ford--Fulkerson-algoritmin vaiheet ja kulku. Algoritmin kulkua havainnollistetaan esimerkin avulla. Algoritmin toimivuutta osoitetaan näyttämällä, että kun algoritmi päättyy, se päättyy aina maksimivirtaukseen.