7.c) Halozati folyamok

Halozati folyamok

Def.: A $(G,c,s,t)$ negyes egy halozat ahol $G=(V,E)$ egy iranyitott graf es $c:E\to \mathbb{R}$ a kapacitas fuggveny ahol $c(e)\ge 0\forall e\in E$, valamint $s\ne t\in V$ csucsok ahol $s$ a forras es $t$ a nyelo.

Def.: Egy halozaton egy $f:E\to \mathbb{R}$ fuggveny folyam, ha a kovetkezok teljesulnek ra:

• $\forall e\in E:0\le f(e)\le c(e)$ – tehat a folyam erteke $0$ es a kapacitas kozott van minden elen.
• $\forall v\in V\setminus \{s,t\}$-re $f_{\text{be}}(v)=f_{\text{ki}}(v)$ ahol $f_{\text{be}}(v)$ a $v$ be-elein levo folyam ertekeinek osszege, hasonloan $f_{\text{ki}}(v)$ a ki-elek folyamanak osszege.

Megj.: Azt mondjuk hogy $|f|:=f_{\text{ki}}(s)=f_{\text{be}}(t)$ a folyam erteke
Celunk az hogy adjunk egy maximalis erteku folyamot egy halozaton.

Tetel: (Ford–Fulkerson)

1. Egy $f$ folyamra $|f|$ maximalis akkor es csak akkor, ha $G^{\prime }$ maradek halozataban nem letezik $s⇝t$ ut.
2. A maximalis folyamertek egyenelo a minimalis vagaskapacitassla. (Max flow - min cut)
3. Ha $c(e)$ egesz minden $e$ elre, akkor van olyan $f$ maximalis folyam, hogy $f(e)$ szinten egesz minden $e$ elre.

Ford-Fulkerson algoritmus: Keressunk maximalis megengedett folyamot egy halozatban.

1. Induljunk ki egy tetszoleges megegngedett folyambol (peldaul $f\equiv 0$).
2. Keszitsuk el azt az iranyitott $D_f=(V,E_f)$ grafot a kovetkezokeppen:
   • Ha $uv\in E$ es $f(uv)<c(uv)$, akkor $(uv)$ elt bevesszuk $E_f$-be elore elkent.
   • Ha $vu\in E$ es $f(vu)>0$, akkor $(uv)$ elt bevesszuk $E_f$-be hatr elkent. Figyelem hogy megforditottuk az elet a $D_f$-ben.
3. Jelolje $S$ az $s$-bol iranyitott uton elerheto pontok halmazat $D_f$-ben.
4. Ha $t\notin S$, azaz $t$ nem erheto el $s$-bol $D_f$-ben, akkor keszen vagyunk es $f$ maximalis folyam.
5. Ha $t\in S$, azaz $t$ elerheto $s$-bol $D_f$-ben, akkor tudjuk novelni a folyam erteket a kovetkezokeppen:
   • Legyen $P$ az az ut $D_f$-ben amin $t$ elerheto $s$-bol
   • Legyen ${\Delta }_1=\min \{c(uv)-f(uv)\}$ ahol $uv$ elore el $P$-ben.
   • Legyen ${\Delta }_2=\min \{f(vu)\}$ ahol $uv$ hatra el $P$-ben.
   • Legyen $\Delta =\min \{{\Delta }_1,{\Delta }_2\}$.
   • Tudjuk novelni a folyamot ugy, hogy az elore eleket $P$-ben noveljuk $\Delta$-vel, es a hatra eleket $P$-ben csokkentjuk $\Delta$-vel.

Menger-tetel

Tetel: (Menger-el) $G$ iranyitott vagy iranyitatlan grafban az $s⇝t$ paronkent eldiszjunkt utak maximalis szama egyenlo a $t$ csucsot az $s$-tol elszeparalo elek minimalis szamaval.

Megj.: A Menger-el tetel konnyen kovetkezik a Ford-Fulkerson MFMC tetelbol. Eloszor iranyitott grafba lassuk be, vegyuk azt a halozatot ahol minden elen a kapacitas $1$. Az MFMC tetel szerint a maximalis folyamertek egyenlo a minimalis vagaskapacitassal, tovabba mivel $c(e)$ egesz minden $e\in E$-re ezert a maximalis folyam $f$ is egesz minden elre. Na tehat a maximalis folyam mindenhol vagy $1$-et vagy $0$-et vesz fel.
Ezekbol kovetkezik, hogy ha a min vagas kapacitasa $k$ akkor a max folyam merete $k$ es a min vagas az $k$ szeparalo el es a max folyam a max eldiszjunkt ut.
Iranyitatlan grafra csak csereljuk le az iranyitatlan eleket ket iranyitott elre es kesz vagyunk.

Tetel: (Menger-csucs) $G$ iranyitott vagy iranyitatlan grafban az $s⇝t$ paronkent csucsdiszjunkt utak maximalis szama egyenlo a $t$ csucsot az $s$-tol elszeparalo csucsok minimalis szamaval.

Grafok tobbszoros osszefuggosege

Tetel: (Menger-el) $G$ graf $k$-szorosan el-osszefuggo akkor es csak akkor, ha $\forall x\ne y\in V$-re van $k$ darab paronkent el-diszjunk $x⇝y$ ut.

Tetel: (Menger-csucs) $G$ graf $k$-szorosan csucs-osszefuggo akkor es csak akkor, ha $\forall x\ne y\in V$-re van $k$ darab paronkent csucs-diszjunk $x⇝y$ ut.