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]

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

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]

Az egyik irány könnyű:

Legyen x megengedett folyam, . Ekkor , 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]

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]

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]

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]

Keressük a maximális folyamot:

Az egyenlőtlenségrendszer:

Korlátok:

Duál program[szerkesztés]

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

Az egyenlőtlenségrendszer:

Korlátok:

Motivációk[szerkesztés]

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]

  • 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