Van itt ez a hálózat az élek kapacitásaival…

és egy hálózatban futó folyammal.

Ebből a folyamból kiindulva keressük meg az S-ből T-be vezető maximális folyamot.

A módszert, amit a maximális folyam megkeresésére fogunk használni, Ford-Fulkerson algoritmusnak hívják.

Az algoritmus lényege pedig az a javító gráf, amit az eredeti hálózat alapján készítünk el.

A javító gráf megmutatja nekünk, hogy milyen útvonalon tudjuk növelni a meglévő folyamot.

A szűk keresztmetszet pedig 2, vagyis maximum 2-vel tudunk növelni.

Ahol zöld élen mentünk a javító úton, ott hozzáadunk…

ahol piros élen, ott levonunk.

Most újra elkészítjük a javító gráfot, hátha még mindig lehet a folyamon javítani.

De, nem úgy néz ki.

Itt nem jutunk át…

Ezeknél a csúcsoknál ugyanis a javító út elakad.

A piros csúcsokból most már lehetetlen átjutni…

a sárga csúcsokba.

A problémát egy kicsit precízebben a Ford-Fulkerson tétel fogalmazza meg.

Ehhez be kell vezetnünk egy új fogalmat, amit vágásnak fogunk hívni.

Már jön is.

A hálózat csúcsainak halmazát V(G)-vel jelöljük.

Legyen X a V(G)-nek egy olyan részhalmaza, ami S-t tartalmazza.

A többi csúcs pedig, amik nincsenek benne az X-ben a V(G)\X halmazt alkotják.

Az X és a V(G)\X halmazok közötti éleket vágásnak nevezzük.

Vágás:

Legyen X a V(G)-nek egy olyan részhalmaza, ami S-t tartalmazza.

Ekkor az X-ből a V(G)\X-be vezető éleket (S,T) vágásnak nevezzük.

A vágás szemléletes jelentése ez…

elvág minden utat S és T között.

A vágás kapacitása pedig azt mondja meg, hogy hány sávot robbantottak föl a terroristák.

Most éppen egy 10 sávos utat és két 4 sávos utat robbantottak föl.

Tehát a vágás kapacitása 10+4+4=18.

Vágás kapacitása:

Egy (S,T) vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.

Vagy éppen ennek a másik vágásnak itt…

ennek a kapacitása 11+4+4=19.

És ennek pedig…

Hát, ennek még több: 4+16=20.

Maximális folyam, minimális vágás, Ford-Fulkerson algoritmus

Vagyis keressük meg azt a vágást, amihez a lehető legkevesebb sávot kell felrobbantani, de mégis teljesen megszűnik az összeköttetés S és T között.

Ezt a vágást minimális vágásnak nevezzük.

Lássuk, mekkora a kapacitása például ennek a vágásnak itt.

Na, ez éppen egy trükkös eset.

Az egyik él ugyanis visszafelé megy.

Amikor egy vágás kapacitását számoljuk, csak az X-ből V(G)\X-be vezető élek számítanak…

ha van olyan él, ami V(G)\X-ből X-be vezet, az nem.

Így aztán ennek a vágásnak a kapacitása 10+9+5=24.

Ami biztosan nem minimális, mert volt már az előbb olyan vágás is, aminek a kapacitása 18.

Ez volt az.

Kérdés: van-e még ennél is kisebb?

És itt kerül képbe a Ford-Fulkerson tétel.

Ha találunk egy tetszőleges folyamot a hálózatban, akkor a folyam értéke egészen biztosan kisebb bármely vágás kapacitásánál.

És fordítva, egy tetszőleges vágás kapacitása biztosan nagyobb, mint bármely folyam értéke.

A Ford-Fulkerson tétel azt mondja, hogy a maximális folyam mindig megegyezik a minimális vágással.

Lássuk, hogyan használhatnánk ezt a tételt a mi kis hálózatunkra.

Az biztos, hogy találtunk egy olyan vágást, aminek a kapacitása 18.

És az is biztos, hogy van egy olyan folyam, aminek az értéke 18.

Hiszen 18 egység indul S-ből…

és annyi is érkezik T-be.

Mivel van 18 kapacitású vágás, nem lehet 18-nál nagyobb értékű folyam.

Vagyis a maximális folyam értéke 18.

És mivel van 18 értékű folyam, nem lehet 18-nál kisebb kapacitású vágás.

Tehát a minimális vágás kapacitása 18.