Maximális folyam, minimális vágás, Ford-Fulkerson algoritmus
Ennek a témakörnek a képletei
Letöltöm az egész kurzus összes képletét:
LetöltömLetöltöm ennek a témakörnek a képleteit:
LetöltömVálogass kedvedre a témakör képletei között:
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.
Vágás kapacitása
Egy $(S,T)$ vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.
Ford-Fulkerson algoritmus
A Ford-Fulkerson algoritmus egy olyan algoritmus, amit a maximális folyam megkeresésére használunk. 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.
Él kapacitása
Legyen $G$ egy irányított gráf és értelmezzünk a gráf élein egy $E \rightarrow R^{+}_0 $ függvényt, ami minden élhez hozzárendeli a $c(e)$ nem negatív számot, amit az él kapacitásának nevezünk.
Hálozat
Legyen $G$ egy irányított gráf és értelmezzünk a gráf élein egy $E \rightarrow R^{+}_0 $ függvényt, ami minden élhez hozzárendeli a $c(e)$ nem negatív számot, amit az él kapacitásának nevezünk.
Van továbbá két kitüntetett pont a gráfban, $S$ (source = forrás) és $T$ (target = cél).
Ekkor a $(G, S, T, c)$ egy hálózat.
Folyam
A hálózatban folyamnak nevezünk egy olyan $ f(e) \; E \rightarrow R^{+}_0$ függvényt, amire teljesül, hogy bármely $e$ élre $0 \leq f(e) \leq c(e)$ és bármely $T$-től és $S$-től különböző $V$ csúcsra:
\( \sum_{Vbe} f(e) - \sum_{Vki} f(e) = 0 \)
Folyam értéke
Egy folyam értékének az
\( m_f = \sum_{Ski} f(e) - \sum_{Sbe} f(e) \)
számot nevezzük.
Ford-Fulkerson tétel
A Ford-Fulkerson tétel azt mondja ki, hogy egy hálózatban a maximális folyam mindig megegyezik a minimális vágással.
Kritikus út
Mindig létezik egy olyan út, ami csak azokon a pontokon halad át, ahol a tartalékidő nulla, és az út hossza megegyezik a teljes folyamat hosszával. Ezt az utat kritikus útnak nevezzük.
Ennek a témakörnek a feladatai
Letöltöm az egész kurzus összes feladatát:
LetöltömLetöltöm ennek a témakörnek a feladatait:
LetöltömVálogass kedvedre a témakör feladatai között:
Itt egy csőrendszer, melyet irányított gráffal jelölünk.
Úgy tűnik, hogy 5+2=7 egység víz indul S-ből és 0+3+4=7 egység is érkezik meg.
Próbáljunk meg ezen javítani.
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.
Itt van ez a hálózat, benne egy folyammal.
Készítsük el a javító gráfot.
Történetünk lényege, hogy szeretnénk eljutni repülővel S-ből T-be, és ezek közül az útvonalak közül választhatunk.
Adott minden járat menetideje, a kérdés pedig az, hogy mennyi ideig fog tartani az út, és mennyi időnk lesz átszállni a repülőtereken.
Adjunk meg egy maximális folyamot és egy minimális vágást az alábbi hálózatban.
Adjunk meg egy maximális folyamot és egy minimális vágást az alábbi hálózatban.
Adjunk meg egy maximális folyamot és egy minimális vágást az alábbi hálózatban.
Adjunk meg egy maximális folyamot és egy minimális vágást az alábbi hálózatban.
Adjunk meg egy maximális folyamot és egy minimális vágást az alábbi hálózatban.
Adjunk meg egy maximális folyamot és egy minimális vágást az alábbi hálózatban.
Adjuk meg a legkorábbi és legkésőbbi bekövetkezéseket, valamint kritikus utat.
Adjuk meg a legkorábbi és legkésőbbi bekövetkezéseket, valamint kritikus utat.
Adjuk meg a legkorábbi és legkésőbbi bekövetkezéseket, valamint kritikus utat.
Adjuk meg a legkorábbi és legkésőbbi bekövetkezéseket, valamint kritikus utat.
Adjuk meg a legkorábbi és legkésőbbi bekövetkezéseket, valamint kritikus utat.
Adjuk meg a legkorábbi és legkésőbbi bekövetkezéseket, valamint kritikus utat.
Itt ez a vízvezeték hálózat, amin keresztül víz áramlik S-ből T-be.
A zárójelben lévő számok a csövek kapacitását jelentik.
Vagyis azt jelentik, hogy mennyi víz képes rajtuk átfolyni.
A zárójel előtti szám pedig azt mondja meg, hogy éppen mennyi víz folyik most a csőben.
Hát, vannak itt még kihasználatlan részek.
A kérdés az, hogyan tudnánk még egy kicsit növelni az átfolyó víz mennyiségét.
Kell hozzá egy kis trükk.
Ezt a csövet itt elzárjuk.
Most rosszabb…
Viszont szabaddá tettük a jobb oldali ágat.
Ahol le tudunk engedni 10 egység vizet.
És így az eddigi 10 helyett most már 15 egység víz folyik S-ből T-be.
Remek hír, de két kínzó kérdés merül föl.
Az egyik: Hogyan lehet rájönni ezekre a javítási lehetőségekre az ennél bonyolultabb esetekben?
A másik: Honnan lehetünk biztosak benne, hogy a legjobb megoldást találtuk meg?
Hát, ezekre a kérdésekre fogunk most válaszolni.
Itt van egy másik hálózat…
ez már egy kicsit bonyolultabb.
És a csőrendszert egy irányított gráffal fogjuk jelölni.
Úgy tűnik, hogy 5+2=7 egység víz indul útnak S-ből…
és 0+3+4=7 egység is érkezik meg.
Próbáljunk meg ezen javítani.
A javításhoz egy úgynevezett javító gráfot fogunk használni.
Nézzük, hogyan készül a javító gráf.
Itt van ez az él…
szabad kapacitással.
Ezt az élt így tesszük be a javító gráfba.
A zöld nyíl azt jelenti, hogy ennyivel tudjuk még a csőben növelni a vizet.
A piros nyíl pedig azt mutatja, hogy jelenleg mennyi folyik át, de szaggatott vonallal, és visszafelé mutat.
A zöld nyíl túl sok magyarázatot nem igényel.
De mire jó a piros nyíl szaggatott vonallal és visszafelé?
A piros nyíl egy zseniális terv része. És hamarosan az is kiderül, hogy mi ez a terv.
Most menjünk szépen tovább.
Ennek az élnek a szabad kapacitása .
Berakjuk ezt is a javító gráfba szépen.
A zöld nyíl azt jelenti, hogy 6-tal tudjuk még a csőben növelni a vizet.
A piros nyíl pedig azt mutatja, hogy jelenleg 2 egység folyik át ezen a csövön,
de már megint ez a rejtélyes szaggatott vonal, és megint visszafelé.
Itt van aztán az A-ból B-be vezető cső.
Ez fullon van, úgyhogy a javító gráfban ide nem rakunk zöld nyilat.
De a rejtélyes piros nyíl itt is kell.
Mivel jelenleg 2 egység víz folyik át a csövön, ezért így:
Most lássuk, mi a helyzet az A-ból C-be vezető csővel.
Ez a cső teljesen üres.
A zöld nyíl tehát megegyezik a cső teljes kapacitásával…
Piros nyíl pedig itt nincs.
Ugyanez a helyzet az A-ból D-be vezető csőnél is.
És szépen lépésről lépésre elkészítjük a javító gráfot.
Elkészült a javító gráf.
A javító gráf megmutatja nekünk, hogy milyen útvonalon tudjuk növelni a meglévő folyamot.
Ezen az útvonalon például tudjuk.
Mégpedig 3 egységgel.
De van még itt más javító út is…
Ezen az útvonalon a szűk keresztmetszet a 3…
Így aztán ennyivel tudunk javítani.
Hát, eddig megvolnánk.
A kérdés, hogy tudunk-e még ezen is javítani.
Készítsük el az ehhez tartozó új javító gráfot, és nézzük meg.
És most nézzük, van-e még itt javító út.
Olyan már nincs, ami csupa zöld éleken keresztül vezet S-ből T-be.
De itt az ideje felfedni a titkos terv részleteit.
Létezik ugyanis még egy javító út…
ami piros élen is halad.
A szűk keresztmetszet ezúttal 2, vagyis 2 egység vizet tudunk még ezen az útvonalon szállítani.
A piros élen történő szállítás pedig azt jelenti…
hogy ezt a csövet elzárjuk.
A bal oldali ágról másfelé tereljük a vizet…
és így a jobb oldali ágon tudjuk növelni 2-vel.
De az egészben az a legjobb, hogy nekünk ezen nem kell gondolkodnunk.
Minden ki fog jönni szépen magától.
Nem kell mást tennünk, csak egyszerűen alkalmazni a hálózatra a javítást.
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 a szokásos módon.
És úgy tűnik, hogy ez már tovább nem javítható.
Azért nem, mert nincsen a javító gráfban S-ből T-be vezető út.
Szerencsére létezik egy tétel, ami végérvényesen el tudja dönteni, hogy létezik-e még további javító út vagy sem.
Ezt a tételt Ford-Fulkerson tételnek nevezzük, és ezzel fogjuk folytatni...
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.
Itt az ideje, hogy egy kicsit precízebbé tegyük a hálózatokkal kapcsolatos fogalmakat.
Legyen G egy irányított gráf és értelmezzünk a gráf élein egy függvényt, ami minden élhez hozzárendeli a nem negatív számot, amit az él kapacitásának nevezünk.
Van továbbá két kitüntetett pont a gráfban, S (source=forrás) és T (target=cél).
Ekkor a (G, S, T, c) egy hálózat.
A hálózatban folyamnak nevezünk egy olyan függvényt, amire teljesül, hogy bármely e élre és bármely T-től és S-től különböző V csúcsra
Vagyis egy csúcsba befolyó mennyiség…
mindig megegyezik a csúcsból kifolyóval.
A két kivétel S és T. S-ből csak kifelé folyik…
T-be csak befelé.
Egy folyam értékének az
számot nevezzük.
Most éppen…
Végül még egy fontos definíció: a 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.
Egy (S,T) vágás kapacitása, a vágásban szereplő élek kapacitásainak összege.
A Ford-Fulkerson tétel azt mondja ki, hogy egy hálózatban a maximális folyam mindig megegyezik a minimális vágással.
És most pedig lássunk egy mindent összefoglaló példát.
Itt van ez a hálózat, benne egy folyammal.
Készítsük el a javító gráfot.
Most nézzük, lehet-e még javítani…
Úgy tűnik, igen.
Ezen az ágon a szűk keresztmetszet 1…
és a másik ágon hozzájön még plusz 3.
Nézzük, tudjuk-e ezt még javítani…
Megint elkészítjük a javító gráfot.
És úgy tűnik, már nem lehet tovább javítani.
Találtunk egy minimális vágást.
Ennek a vágásnak a kapacitása 14.
Ez azt jelenti, hogy minden folyam értéke maximum 14 lehet.
Ennek a folyamnak az értéke szintén 14.
Ez azt jelenti, hogy minden vágás kapacitása minimum 14 kell, hogy legyen.
A minimális folyam értéke és a maximális vágás kapacitása tehát 14.
