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

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Jelöljük a minimum értékét mg-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 mg.

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

Maximális folyam algoritmussal[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  • 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