5.2. 5.2. A feladatpár matematikai vizsgálata

A folyam és a vágás közötti alapvető összefüggést a következő lemmában mondjuk ki:

LEMMA (A folyamprobléma alaplemmája):

A feltételeket kielégítő tetszőleges, s-ből t-be irányuló folyam (megengedett folyam) és tetszőleges, s-et t-től elválasztó vágás esetén a folyam értéke nem lehet nagyobb, mint a vágás átbocsátóképessége, azaz képletben

Bizonyítás.

Felhasználva a közbülső pontokra vonatkozó összefüggést és az addíciós összefüggéseket, egyszerűen adódik, hogy

A lemmából két fontos következményt olvashatunk ki.

1. KÖVETKEZMÉNY:

Ha a megengedett folyam és a vágás olyan, hogy a lemmában egyenlőség áll fenn, akkor a folyam maximális a vágás pedig minimális.

Bizonyítás.

Legyen a szóbanforgó folyam , a vágás pedig , amelyre . Indirekte tegyük fel, hogy az nem maximális, azaz létezik egy megengedett folyam, amelyre

Mivel az folyamra is igaz a lemma állítása, így

A fenti két összefüggés ellentmond egymásnak, így feltevésünk szerint nem létezik folyam, tehát az folyam maximális.

A vágás oldaláról történő bizonyítás hasonló módon végezhető, amelyet az olvasóra bízunk.

A második következményt szokás optimalitási kritériumnak vagy egyensúlyi összefüggésnek is nevezni, mivel arra ad választ, hogy milyen feltételek esetén egyezik meg a két célfüggvény, azaz mikor optimálisak a megengedett megoldások.

2. KÖVETKEZMÉNY (optimalitási kritérium):

A lemmában egyenlőség akkor és csak akkor áll fenn, ha az vágás minden élén

Bizonyítás.

A lemma bizonyításának utolsó lépése szerint

amely részletezve

és ebben az összefüggésben egyenlőség akkor és csak akkor állhat fenn, ha az egyenlőtlenség mindkét oldalán az összegben lévő megfelelő tagok megegyeznek, azaz minden vágásbeli élen .

FORD-FULKERSON tétel (a folyamprobléma főtétele):

Létezik olyan megengedett folyam és vágás, hogy a lemmában egyenlőség áll fenn, azaz lézezik -ből -be irányuló maximális folyam és -et -től elválasztó minimális vágás, továbbá a maximális folyam értéke egyenlő a minimális vágás átbocsátóképességével, azaz képletben

A folyamprobléma főtételét L. R. FORD és D. R. FULKERSON adták meg 1962-ben [ 5 ]. A FORD-FULKERSON néven ismertté vált jelentős tételt a további modelljeinkben is fel fogjuk használni.

Bizonyítás.

A tételre konstruktív bizonyítást adunk, amelyből a megoldás menete is kiolvasható.

Legyen egy tetszőleges s-ből t-be irányuló folyam. Konstruáljuk meg azt a digráfot, amelynek E élhalmazán . Az ilyen éleket telítetlen éleknek nevezzük, mivel még rajtuk növelhető a folyam. Az olyan éleket, amelyekben telített éleknek nevezzük. Keressünk az digráfban utat s-ből t-be. A MINTY tétel értelmében két eset állhat fenn:

1. eset: nincs út

MINTY tétel szerint ekkor van üres vágás. Ez pedig azt jelenti, hogy ebben a vágásban nincs telítetlen él. A hálózatra vonatkozóan pedig ebben a vágásban csak telített élek vannak, a lemma két következménye értelmében a folyam is és a vágás is optimális.

2. eset: van út

A hálózatban ennek a P útnak minden éle telítetlen, azaz rendelkezik szabad kapacitással. Ezt az utat folyamnövelő útnak nevezzük, hiszen minden élén valamennyivel növelhető a folyam.

Határozzuk meg az út mentén lévő élekre a szabad kapacitások minimumát, jelölje ezt az értéket , azaz legyen

A értéket az út kapacitásának nevezzük. Az út mindegyik élén ugyanannyivel kell növelni a folyamot a Kirchoff törvény miatt. Maximálisan tehát a értékkel növelhető a folyam az út mentén. Természetesen ennél kevesebbel is növelhető a folyam. Mivel a folyamfeladat célja a maximális folyam átáramoltatása, célszerű ezzel a maximális mennyiséggel növelni a folyamot. Egyébként, ha nem ezt tennénk, akkor a következő útkeresés során is ugyanezt az utat találnánk meg, hisz mindegyik útbeli élen lenne szabad kapacitás. Ezzel a növeléssel az út mentén bizonyos élek telítetté válnak. A folyamot tehát az út mentén a növeljük, a folyamfüggvény ferdeszimmetricitása miatt a „visszút” mentén ugyanennyivel csökkenteni kell. Az új folyam a következőképpen határozható meg:

Az új folyam értéke , azaz a folyam értéke nő. Az új folyam megengedett marad, hiszen teljesíti a folyamra vonatkozó összes feltételt. Az új folyamra megismételjük a fentebb leírt eljárást. Mivel az alapadatok miatt egész szám és a lemma miatt felülről korlátos, így véges lépésben eljutunk az optimális megoldáshoz, azaz az 1. esethez.

A FORD-FULKERSON tétel bizonyításából tehát kiolvasható, hogy maximális folyam és minimális vágás esetén igaz, hogy a minimális vágásban minden élen a kapacitásnak megfelelő folyam folyik, azaz a minimális vágásra az jellemző, hogy minden éle telített.