Maximális folyam – minimális vágás

Ford és Fulkerson maximális folyam – minimális vágás tétele (angolul: max-flow-min-cut theorem), más néven a Ford–Fulkerson tétel azt mondja ki, hogy egy irányított gráfban a maximális folyam nagysága egyenlő a minimális vágás méretével.

Legyen D=(V,A) irányított gráf, s,t két kijelölt pont D-ben. Legyen adva a g kapacitásfüggvény D élein. A megengedett folyamok maximális nagysága egyenlő az S halmaz összes kiáramlásának minimumára, ahol a minimum az összes olyan S halmazra megy, ami tartalmazza s-t, de t-t nem.

Ha még az is teljesül, hogy g egész, akkor a maximális folyam is választható egész értékűnek.

Ekvivalens alakban

Jelölje δ_g(S) az S halmaz összes kiáramlását a g kapacitás szerint. Ezzel a jelöléssel a megengedett s-t folyamok nagysága egyenlő a δ_g(S) értékek minimumával, ahol $s\in S,t\not \in S$

Ha még g egész értékű is, akkor akkor a maximális folyam is választható egész értékűnek.

Bizonyítások

Az egyik irány könnyű:

Legyen x megengedett folyam, $s\in S,t\not \in S$. Ekkor $\delta _{x}(s)=\delta _{x}(S)-\rho _{x}(S)\leq \delta _{g}(S)$, ahol ρ_x az S-be áramlás nagysága az x folyam szerint. Az egyenlőtlenségből következik, hogy a maximum nem nagyobb a minimumnál.

Az egyenlőséghez elég megmutatmi, hogy a minimum tényleg a maximum. Ezt legegyszerűbb a Hoffman-tételből bizonyítani.

A Hoffman-tételből

Jelöljük a minimum értékét m_g-vel. Ez a minimum biztosan létezik, hiszen véges sok S halmaz lehetséges.

Adjunk a gráfhoz egy új e=ts élt, és kapacitása legyen egy elég nagy M szám. Vezessük be minden élre az f(a) alsó korlátot: a régi éleken legyen ez nulla, és az e élen legyen m_g.

Teljesülnek a Hoffman-tétel feltételei, ezért a tétel szerint van megengedett áram. A hozzáadott élt elhagyva m_g nagyságú folyamot kapunk.

Maximális folyam algoritmussal

A Hoffman-tétellel való bizonyítás nem konstruktív, nem algoritmikus. A tétel azonban bizonyítható a Hoffman-tételtől függetlenül, maximális folyam algoritmusokkal is, amik kiadják mind a maximális folyamot, mind a minimális S halmazt. Vigyázni kell, hogy olyan algoritmusra van szükség, ami minden kapacitásra működik, különben a tétel csak racionális kapacitásokra lesz bizonyítva.

Lineáris programok

Lineáris programokkal: a maximális folyam a minimális vágás duálisa, ezért a dualitástétel szerint egyenlőek.

Primál program

Keressük a maximális folyamot:

$\qquad \mathbf {f({\overrightarrow {TS}})}$

Az egyenlőtlenségrendszer:

$\sum _{{\overrightarrow {vu}}\in E}f({\overrightarrow {vu}})-\sum _{{\overrightarrow {uv}}\in E}f({\overrightarrow {uv}})=0\qquad \forall u\in V\neq {S,T}\qquad \leftrightarrow p(u)$

$\sum _{{\overrightarrow {vT}}\in E}f({\overrightarrow {vT}})-\sum _{{\overrightarrow {Tv}}\in E}f({\overrightarrow {Tv}})-f({\overrightarrow {TS}})=0\qquad \leftrightarrow p(T)$

$\sum _{{\overrightarrow {vS}}\in E}f({\overrightarrow {vS}})+f({\overrightarrow {TS}})-\sum _{{\overrightarrow {Sv}}\in E}f({\overrightarrow {Sv}})=0\qquad \leftrightarrow p(S)$

$f({\overrightarrow {uv}})\leq c({\overrightarrow {uv}})\qquad \forall {\overrightarrow {uv}}\in E\qquad \leftrightarrow x({\overrightarrow {uv}})$

Korlátok:

$f({\overrightarrow {uv}})\geq 0\qquad \forall {\overrightarrow {uv}}\in E,\quad f({\overrightarrow {TS}})\geq 0$

Duál program

Keressük a minimális vágást:

$\mathbf {\sum _{{\overrightarrow {uv}}\in E}c({\overrightarrow {uv}}).x({\overrightarrow {uv}})}$

Az egyenlőtlenségrendszer:

$p(v)-p(u)+x({\overrightarrow {uv}})\geq 0\qquad \forall {\overrightarrow {uv}}\in E\qquad \leftrightarrow f({\overrightarrow {uv}})$

$p(S)-p(T)\geq 1\qquad \leftrightarrow f({\overrightarrow {TS}})$

Korlátok:

$p(u)\leq \infty ,\quad \forall u,x({\overrightarrow {uv}})\geq 0\quad \forall {\overrightarrow {uv}}$

Motivációk

Számos elméleti és gyakorlati alkalmazása van például a gráfelméletben, vagy szállítási problémák, tesztfeladatok megoldására, vagy éppen a PERT megoldására.

Források

• P. Elias, A. Feinstein, and C. E. Shannon. Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117—119, 1956.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 26: Maximum Flow, pp. 643–700.
• http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf