8. Hálózat, folyam, vágás
8. Hálózat, folyam és st-vágás fogalma, folyam értéke, vágás kapacitása. Algoritmus maximális folyam és minimális vágás megkeresésére, Ford-Fulkerson tétel, Edmonds-Karp tétel (biz. nélkül). Egészértékűségi lemma.
A hálózat fogalma
Definíció
Legyen adott a $G = (V,E)$ irányított gráf, annak az $s, t \in V(G)$ egymástól különböző csúcsai és a $c : E \to \mathbb{R}^+ \cup \{0\}$ kapacitás függvény. Ez a függvény minden $e \in E$ élhez egy nemnegatív $c(e)$ kapacitás értéket rendel. Ekkor a **$(G,s,t,c)$ négyest hálózatnak nevezzük**.
A hálózat elméleti modellje lehetővé teszi a különböző áramlási problémák (pl. adatforgalom, szállítás) matematikai vizsgálatát. A **forrás ($s$)** az a pont, ahonnan az áramlás indul, a **nyelő ($t$)** pedig az, ahol végződik.
A folyam fogalma
Definíció
Egy adott $(G,s,t,c)$ hálózat esetén folyamnak nevezzük az $f : E \to \mathbb{R}^+ \cup \{0\}$ függvényt, ha rá az alábbi feltételek teljesülnek:
- 1 $0 \le f(e) \le c(e)$ minden $e \in E(G)$ él esetén;
- 2 $\sum_{e:v \to \bullet} f(e) = \sum_{e:\bullet \to v} f(e)$ minden $v \in V(G), v \neq s,t$ csúcs esetén.
Az (1) feltétel a kapacitáskorlát: egy élen nem folyhat át több, mint annak a teherbírása.
A (2) feltétel a konzervációs szabály (vagy Kirchhoff-törvény): minden belső csúcsra igaz, hogy a befolyó éleken érkező folyam összege megegyezik a kifolyó éleken távozó folyam összegével. Vagyis a folyam nem „veszhet el” és nem „keletkezhet” a belső csúcsokban.
Interaktív Labor: Áramlás és Konzerváció
Állítsd be a forrásból induló vizet! Figyeld meg, hogyan oszlik meg a folyam az $A$ csúcsnál, hogy teljesüljön a konzervációs szabály.
Ellenőrzés
A folyam értéke
Definíció
A $(G,s,t,c)$ hálózatban adott $f$ folyam **$m_f$-fel jelölt értéke**:
A folyam értéke tehát megmutatja a hálózaton keresztül áramló nettó mennyiséget. Ezt úgy számoljuk ki, hogy a forrásból ($s$) kimenő élek folyamértékeinek összegéből kivonjuk a forrásba esetlegesen visszatérő élek folyamértékeit.
Érdekesség, hogy a belső csúcsokra vonatkozó konzervációs szabály miatt belátható, hogy ugyanez az érték jelenik meg a nyelőnél ($t$) is, csak fordított előjellel: a nyelőbe befolyó és onnan kifolyó mennyiségek különbsége pontosan $m_f$ lesz.
A segédgráf fogalma
Definíció
Legyen $f$ folyam a $(G,s,t,c)$ hálózatban. Ekkor az $f$-hez tartozó **$H_f$ segédgráfot** a következőképpen definiáljuk:
$H_f$ egy olyan irányított gráf, amelyre $V(H_f) = V(G)$, azaz csúcshalmaza azonos az eredeti gráféval. Élkészletébe az alábbi két típusú él kerül:
- 1 Előre él: Ha $e = (u,v)$ olyan éle $G$-nek, amelyre $f(e) < c(e)$, akkor $e = (u,v)$ bekerül $H_f$-be.
- 2 Visszaél: Ha $e = (u,v)$ olyan éle $G$-nek, amelyre $f(e) > 0$, akkor $e$ megfordítása, az $e' = (v,u)$ él kerül be $H_f$-be.
A segédgráf lényege, hogy megmutassa, hol és milyen irányban lehet még változtatni a folyam értékén. Az előre élek azt jelzik, hogy az adott élen még van szabad kapacitás, tehát növelhető rajta az átfolyás. A visszaélek pedig azt mutatják meg, hogy egy élen már van valamekkora folyam, amit szükség esetén "visszaküldhetünk" vagy csökkenthetünk, hogy más utakon több férjen el.
Interaktív Labor: Segédgráf-építő ($H_f$)
Változtasd a folyamot és figyeld, hogyan alakulnak ki az előre- és visszaélek a segédgráfban!
A javítóút fogalma
Definíció
Legyen $f$ folyam a $(G,s,t,c)$ hálózatban. Ekkor a **$H_f$ segédgráfbeli, $s$-ből $t$-be vezető irányított utakat** javítóútnak nevezzük $f$-re nézve.
A javítóút létezése kritikus fontosságú: ha találunk ilyen utat a segédgráfban, az azt jelenti, hogy a folyam értéke ($m_f$) még növelhető. Az út mentén található élek (legyenek azok előre vagy visszaélek) mentén egy meghatározott mennyiséggel módosíthatjuk az áramlást anélkül, hogy megsértenénk a kapacitáskorlátokat vagy a konzervációs szabályt.
Amikor a segédgráfban már nem létezik $s \to t$ irányított út, akkor a folyam értéke elérte a maximumát. Ez vezet el minket a Ford-Fulkerson tételhez.
A javítóutas algoritmus
Algoritmus (Maximális folyam keresésére)
-
1.
Induljunk ki egy kezdeti folyamból (például minden élre $f(e) = 0$).
-
2.
CIKLUS:
- Készítsük el az aktuális $f$-hez tartozó $H_f$ segédgráfot.
- Keressünk egy $P$ javítóutat $H_f$-ben $s$-ből $t$-be (például BFS algoritmussal).
- Ha nincs ilyen út: Álljunk le, a folyam maximális.
A folyam módosítása
Ha találtunk javítóutat, határozzuk meg a javítás $\delta$ mértékét:
$\delta_2 = \min\{f(e) : e \text{ megfordítottja visszaéle } P\text{-nek}\}$
$\delta = \min\{\delta_1, \delta_2\}$
Minden élre frissítsük a folyamot:
- $f(e) + \delta$, ha $e$ előre éle $P$-nek
- $f(e) - \delta$, ha $e$ megfordítottja visszaéle $P$-nek
- $f(e)$ változatlan marad egyébként.
Az algoritmus helyessége és a folyam növekedése
Állítás
Ha $f$ folyam, akkor a javítóutas algoritmus 8. sorában végrehajtott változtatások után is az marad, és $m_f$ értéke $\delta$-val nő.
A bizonyítás vázlata
1. Kapacitáskorlát: Az előre éleknél $\delta \le c(e) - f(e)$, a visszaéleknél pedig $\delta \le f(e)$, így a módosított folyamértékek $0$ és $c(e)$ között maradnak.
2. Konzervációs feltétel: Ha a javítóút $P$ áthalad egy belső $v$ csúcson, négy esetet vizsgálhatunk az érkező ($e_1$) és távozó ($e_2$) élek típusa alapján:
- Mindkettő előre él: Mindkét élen $\delta$-val nő a folyam, így az egyenleg változatlan.
- Mindkettő visszaél: Mindkét élen $\delta$-val csökken a folyam, az egyenleg itt is megmarad.
- Vegyes esetek: Az egyik élen történő növekedés és a másikon történő csökkenés kiejti egymást a csúcs egyenlegében.
3. A folyamérték növekedése: A forrásból ($s$) kilépő első él mentén a nettó kiáramlás pontosan $\delta$-val nő (akár előre élről, akár visszaélről van szó), így $m_f$ értéke is $\delta$-val emelkedik.
Az st-vágás fogalma
Definíció
A $(G,s,t,c)$ hálózatban **st-vágásnak** nevezzük az $X \subseteq V(G)$ csúcshalmazt, ha rá $s \in X$ és $t \notin X$ teljesül. Ha a szövegkörnyezetből $s$ és $t$ szerepe egyértelmű, akkor $X$-et st-vágás helyett röviden **vágásnak** is hívjuk.
A vágás vizuálisan úgy képzelhető el, mint egy határvonal, amely két részre osztja a hálózat csúcsait: az egyik oldalon marad a forrás ($s$), a másik oldalon pedig a nyelő ($t$).
A hálózati folyamok elméletében a vágás azért fontos, mert minden folyamnak, ami $s$-ből $t$-be tart, előbb-utóbb "át kell kelnie" ezen a határon. A vágás korlátozza a hálózat áteresztőképességét, hasonlóan ahhoz, ahogy egy csővezeték legszűkebb keresztmetszete meghatározza a maximális átfolyást.
A folyamérték és a vágások kapcsolata
Állítás
Ha $f$ tetszőleges folyam, $X$ pedig tetszőleges vágás a $(G,s,t,c)$ hálózatban, akkor:
Bizonyítás
Írjunk fel $X$ minden csúcsára egy-egy egyenletet:
$s$ forrásra:
$$m_f = \sum_{e:s\bullet\to} f(e) - \sum_{e:s\bullet\leftarrow} f(e)$$
minden $x \in X, x \neq s$ csúcsra:
$$0 = \sum_{e:x\bullet\to} f(e) - \sum_{e:x\bullet\leftarrow} f(e)$$
Ezek az egyenletek persze mind igazak: az első a folyamérték definíciója, a többi pedig a folyam definíciójának folyammegmaradási követelményéből fakad (átrendezés után).
Adjuk most össze ezt az $|X|$ darab egyenletet és vizsgáljuk meg, hogy mit kapunk! A bal oldalon persze $m_f$ áll (hiszen ehhez $(|X|-1)$-szer nullát adtunk). Az összeg jobb oldalát pedig úgy tekinthetjük át, ha minden $e$ élre megnézzük, hogy $f(e)$ hányszor és milyen előjellel jelenik ott meg. Válasszunk ezért egy tetszőleges $e = (u,v)$ élet! Mivel $u$ és $v$ is lehet $X$-ben vagy azon kívül, ezért négy esetet kell megvizsgálnunk:
1. Ha $u \in X$ és $v \in X$, vagyis $e$ $X$-en belül halad, akkor $f(e)$ kétszer is megjelenik az összeg egyenlet jobb oldalán: egyszer az $x = u$ csúcsra felírt egyenletből pozitív előjellel (hiszen $e$ kilép $u$-ból) és egyszer az $x = v$-re felírt egyenletből negatív előjellel (hiszen $e$ belép $v$-be); így ebben az esetben végül is $f(e)$ nem járul hozzá az összeg jobb oldalához, mert a két elfordulása kiejti egymást.
2. Ha $u \in X$ és $v \notin X$, vagyis $e$ kilép $X$-ből, akkor $f(e)$ egyszer, az $x = u$ csúcsra felírt egyenlet jobb oldalán jelenik meg, mégpedig pozitív előjellel (mert $e$ kilép $u$-ból). Így $f(e)$ az összeg jobb oldalán is megjelenik.
3. Ha $u \notin X$ és $v \in X$, vagyis $e$ belép $X$-be, akkor $f(e)$ szintén egyszer jelenik meg az összeg jobb oldalán, de negatív előjellel: az $x = v$-re felírt egyenletből (mert $e$ belép $v$-be).
4. Végül az $u \notin X, v \notin X$ esetben $f(e)$ egyáltalán nem jelenik meg az egyenletek jobb oldalán (és így persze az összegben sem).
Összefoglalva a fentieket: az összeg egyenlet jobb oldalán az $X$-ből kilépő élekre az $f(e)$ 1-szeres szorzóval, az $X$-be belépőkre pedig (-1)-szeres szorzóval jelenik meg. Más szóval: a felírt $|X|$ darab egyenlet összege éppen az állításbeli egyenlet, ami így nyilván szintén igaz.
A maximális folyam tételének bizonyítása
Tétel
Ha a $(G,s,t,c)$ hálózatban az $f$ folyamra nézve nincs javítóút, akkor $f$ maximális folyam (vagyis nincs $m_f$-nél nagyobb értékű folyam).
Bizonyítás
Megmutatjuk, hogy létezik olyan $X$ $st$-vágás, aminek a kapacitása $c(X) = m_f$. Ebből az állítás szerint következni fog, hogy minden $f'$ folyamra $m_{f'} \le c(X) = m_f$ teljesül, és ezért $f$ értéke valóban maximális.
Álljon $X$ azokból a $v$ csúcsokból, amikre létezik $s$-ből $v$-be vezető irányított út a $H_f$ segédgráfban. Ekkor $t \notin X$, mert $f$-re nézve nem létezik javítóút. Másrészt $s \in X$ világos, így $X$ valóban $st$-vágás.
Azt állítjuk, hogy ha $e = (u,v)$ tetszőleges, $X$-ből kilépő él, akkor rá $f(e) = c(e)$ teljesül. Ha ez nem volna igaz, akkor $f(e) < c(e)$ miatt $e$ bekerülne $H_f$ élhalmazába (előre élként). Így egy $H_f$-ben $s$-ből $u$-ba vezető irányított út (ami $u \in X$ miatt létezik) megtoldható volna az $e = (u,v)$ éllel $v$-ig, és így egy $s$-ből $v$-be vezető irányított utat kapnánk; ez azonban ellentmond annak, hogy $v \notin X$.
Megmutatjuk azt is, hogy ha $e = (u,v)$ $X$-be belépő él, akkor rá $f(e) = 0$ teljesül. Ha ez nem volna igaz, akkor $f(e) > 0$ miatt $e' = (v,u)$, az $e$ megfordítottja bekerülne $H_f$ élhalmazába visszaélként. Így egy $H_f$-ben $s$-ből $v$-be vezető irányított út (ami $v \in X$ miatt létezik) megtoldható volna $e'$-vel $u$-ig, és így egy $s$-ből $u$-ba vezető irányított utat kapnánk; ez is ellentmondás, hiszen $u \notin X$.
Mindezekből az következik, hogy $f$-re és $X$-re megismételhető az állítás bizonyításának a számolása – azzal a lényeges különbséggel, hogy egyenlőtlenség helyett egyenlőséget írhatunk:
Valóban: a fentiek szerint az $X$-ből kilépő, illetve az $X$-be belépő élekre $f(e) = c(e)$, illetve $f(e) = 0$ teljesül (ezeken kívül pedig ismét csak az állítást és a definíciót alkalmaztuk).
Az Edmonds-Karp tétel
Tétel (Edmonds-Karp)
Ha a $G$ gráf $n$ csúcsú és $m$ élű és a $(G,s,t,c)$ hálózatban a maximális folyam keresésére szolgáló javítóutas algoritmus futása során $H_f$-ben mindig az egyik legrövidebb (vagyis legkevesebb élű) $s$-ből $t$-be vezető irányított utat választjuk javítóútnak, akkor az eljárás legföljebb $n \cdot m$ javító lépés után megáll.
Ez a tétel alapvető fontosságú a hálózati folyamok algoritmikus kezelésében, mivel garantálja, hogy a javítóutas módszer — a legrövidebb utak szisztematikus kiválasztásával — polinomiális időben véget ér, függetlenül az élek kapacitásától.
A Ford-Fulkerson tétel
Tétel (Ford-Fulkerson tétel)
Bármely $(G,s,t,c)$ hálózatra $\max\{m_f : f \text{ folyam}\} = \min\{c(X) : X \text{ st-vágás}\}$, vagyis a hálózatbéli maximális folyam értéke megegyezik az st-vágások kapacitásának minimumával.
Bizonyítás
Futtassuk a $(G,s,t,c)$ hálózatban a javítóutas algoritmust (például az azonosan nulla folyamból indítva) leállásig – ami a Tétel szerint véges sok javító lépés után bekövetkezik; a kapott folyamot jelölje $f$.
A Tétel bizonyításában láttuk, hogy ekkor a $H_f$-ben $s$-ből irányított úton elérhető csúcsok alkotta $X$ vágásra $m_f = c(X)$ teljesül; jelölje ezt a közös értéket $d$.
Ebből tehát $\max \{m_f : f \text{ folyam}\} = d = \min \{c(X) : X \text{ st-vágás}\}$ valóban adódik.
Az egész értékűségi lemma
Lemma (Egész értékűségi lemma)
Tegyük fel, hogy a $(G,s,t,c)$ hálózatban minden $e \in E(G)$ élre $c(e) \in \mathbb{Z}$. Ekkor:
- (i) létezik olyan $f$ maximális folyam a hálózatban, amelyre $f(e) \in \mathbb{Z}$ minden $e \in E(G)$ élre és
- (ii) ilyen egész értékű maximális folyam a javítóutas algoritmussal található.
Bizonyítás
Indítsuk a javítóutas algoritmust egy tetszőleges egész értékű $f$ folyamtól, például az azonosan nullától. Ekkor az algoritmus a működése során végig fenntartja $f$ egész értékűségét.
Valóban, ha az aktuális $f$ folyamra $f(e) \in \mathbb{Z}$ minden $e$ élre, akkor az algoritmus pszeudokódjának 7. sorában $\delta_1$ és $\delta_2$ számításakor is egész számok minimumát vesszük. Mivel a $c(e)$ kapacitásokról feltettük az egész értékűséget, és $f(e)$ is egész, így $c(e) - f(e)$ és maga $f(e)$ is egész lesz minden élre. Ebből következően $\delta$ is egész marad, így a folyam módosítása után is igaz marad az egész értékűség.
Következik, hogy $f$ az algoritmus leállásakor is egész értékű marad; azt pedig a tételből tudjuk, hogy ekkor $f$ maximális folyam.
Összefoglaló Kvíz
Hálózati folyamok és vágások
Vidd az egeret a kártyák fölé a helyes válaszért!
#01 Konzervációs szabály
Mit ír elő a folyam definíciója a hálózat belső csúcsaira vonatkozóan?
#02 Segédgráf élei
Mikor kerül be egy visszaél a $H_f$ segédgráfba egy eredeti $e=(u,v)$ él esetén?
#03 Ford-Fulkerson tétel
Milyen kapcsolat van a maximális folyam és a minimális vágás között?
#04 Egészértékűségi lemma
Mikor garantálható az egész értékű maximális folyam létezése?
Tudtad-e?
EGÉSZÉRTÉKŰSÉGI LEMMA
Ha egy hálózatban minden kapacitás egész szám, akkor a javítóutas algoritmussal talált maximális folyam minden élen egész értékű lesz. Ez elengedhetetlen a logisztikai feladatoknál, ahol nem küldhetünk "fél kamiont".
EDMONDS-KARP HATÉKONYSÁG
Míg az alap Ford-Fulkerson algoritmus lassú lehet, az Edmonds-Karp tétel kimondja: ha mindig a legrövidebb javítóutat választjuk, legfeljebb $n \cdot m$ lépésben célhoz érünk.
MIN-CUT JELENTŐSÉGE
A minimális vágás nemcsak matematikai korlát, hanem a hálózat legsebezhetőbb pontja. A Max-flow Min-cut tétel szerint itt dől el, mennyi adat vagy víz juthat át a rendszeren.
INTERNET ÉS FORGALOM
Az internetes csomagküldés vagy a városi forgalomirányítás mind folyamoptimalizálás. A szoftverek folyamatosan "javítóutakat" keresnek a hálózatban, hogy elkerüljék a túlterhelt csomópontokat.