- Gráfelméleti alapok
- Kuratowski gráfok, síkbarajzolhatóság
- Gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózati folyamok
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák
Hálózati folyamok
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.
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.
É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.
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.
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.
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.
