Számítástudomány alapjai epizód tartalma:
Elmeséljük, hogyan működik a Ford-Fulkerson algoritmus, hogyan lehet megtalálni a maximális folyamot és a minimális vágást. Megnézzük a Ford-Fulkerson tételt, és azt is, hogy, mi az a javító gráf és hogyan kell használni.
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.
Számítástudomány alapjai epizód.