Ford-Fulkerson tétel

A Ford - Fulkerson tétel egy gráfmaximális áramlási tétel, amely szorosan kapcsolódik Menger tételéhez .

Ez így hangzik: a maximális áramlás értéke az útvonalgráfban megegyezik a minimális vágás áteresztőképességének értékével .

Elegendőség: a t és s csúcsok közötti áramlás kisebb vagy egyenlő bármely vágás értékével . Adott legyen némi áramlás és bizonyos szakasz. Ennek az áramlásnak az értéke a t csúcstól s pontig minden lehetséges útvonalon szállított "rakomány" értékeinek összege . Minden ilyen útvonalnak közös éle kell, hogy legyen az adott szakasszal. Mivel a szakasz minden élére lehetetlen a teherbíró képességénél nagyobb „terhelést” átvinni, ezért az összes terhelés összege kisebb vagy egyenlő, mint a szakasz éleinek összes teherbírásának összege. Az állítás bebizonyosodott.

Ebből következik, hogy bármely áramlás kisebb vagy egyenlő, mint a minimális szakasz értéke, és ennélfogva a maximális áramlás kisebb vagy egyenlő, mint a minimális szakasz értéke.

Ezen a tételen alapul a gráfban a maximális áramlást megkereső Ford-Fulkerson algoritmus , amely egyben bizonyítja a tétel szükségességét, azaz konstruktív.

Újabb bizonyíték (erősítéssel)

Erősítsük meg a Ford-Fulkerson tételt a következőképpen. Egy f áramlású hálózatnál a következő három tény egyenértékűségét bizonyítjuk egyszerre: $G(V,E)$

1° Áramlási f maximum

2° A minimális vágás kapacitása megegyezik az f áramlás értékével

3° A gráfban nincs komplementer út $G$

1° → 3°. Ennek ellenkezőjét feltételezve a transzportgráfban a komplementer út információiban leírt ellentmondást kapjuk .

3° → 2°. Nyilvánvaló, hogy az f áramlás értéke nem haladja meg a minimális vágás kapacitását . Hadd . Ezután vegyünk egy vágást, ahol a halmaz az összes csúcsot tartalmazza, kivéve a . Ekkor az áteresztőképessége nem kisebb, mint a minimális vágás áteresztőképessége, amely viszont nagyobb, mint az f áramlás értéke. Ennélfogva van egy irány -tól -ig , úgy, hogy . Most vegyük ezeket mind, és helyezzük át ide . Figyelembe véve a kapott vágást, megjegyezzük, hogy az áteresztőképessége is nagyobb, mint az áramlási érték. Ismét növeljük a halmazt, és addig csináljuk, amíg csak a csúcs marad a halmazban . Ez lesz az első csúcs az úton, amelyet létrehozunk. Most nézzük meg, melyik párost választottuk utoljára. Legyen egy pár . Ezután hozzáadunk egy csúcsot az útvonalhoz . Ezután megnézzük egy párban, hogy melyik csúcs volt az első helyen . Hagyd . Majd tovább az útvonalhoz adjuk hozzá a csúcsot . Ezt addig csináljuk, amíg el nem érjük a csúcsot . A konstrukció szerint azonban ez az út maradék, ami ellentmond a feltételezésnek. $(UTCA)$ $c(S,T)>f$ $S$ $t$ $(u,t)$ $S$ $T$ $f(u,t)<c(u,t)$ $u$ $T$ $T$ $S$ $s$ $(s,u)$ $u$ $u$ $(u,v)$ $v$ $t$

2° → 1°. Mint már említettük, nyilvánvaló, hogy egyetlen áramlás értéke sem haladja meg a minimális vágás áteresztőképességét, és a mi áramlásunk értéke egyenlő. Ekkor az áramlás értéke nem kisebb, mint bármely más áramlás értéke a hálózatunkban, vagyis az áramlás maximális. $f$ $f$ $f$

Ez a bizonyítás azért jó, mert nem használ bonyolult algoritmust a maximális áramlás megtalálására egy tetszőleges szállítási hálózatban.

Példa

A jobb oldalon egy 6 csúcsból álló hálózat látható , és a forrástól a lefolyóig terjedő teljes áramlás 5. Ez az áramlás a hálózat maximuma. $V = \{s,o,p,q,r,t\}$ $s$ $t$

Ebben a hálózatban 2 minimális vágás lehetséges:

Metszés	Folyam
$S=\{s,o,p\},T=\{q,r,t\}$	$c(o,q)+c(p,r)=3+2=5$
$S=\{s,o,p,q,r\},T=\{t\}$	$c(q,t)+c(r,t)=2+3=5$

Irodalom

Novikov F. A. Diszkrét matematika programozóknak . - 3. - Szentpétervár. : Péter , 2009. - S. 277 -279. — 384 p. - ISBN 978-5-91180-759-7 .

Linkek

Ford-Fulkerson algoritmus : algolist.manual.ru.
Hálózatok, áramlások hálózatokban. Ford-Fulkerson tétel a Mini-Soft.ru oldalon