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
[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