5.4. 5.4. Példamegoldás

Az algoritmus működésének bemutatására 2 számpéldát oldunk meg.

1. példa

Tekintsük mégegyszer a fejezet elején vázolt hálózatot és az ott megfogalmazottak szerint határozzuk meg a hálózaton az 1-ből a 6-ba irányuló maximális folyamot és az 1-et a 6-tól elválasztó minimális vágást! Most a megoldási algoritmust mutatjuk be, az előzőekben csupán a feladat matematikai megfogalmazását adtuk meg.

Először a hálózatot teljes hálózattá egészítjük ki. Induló folyamként a zérus folyamot választjuk. Ebben az esetben az élek szabad kapacitása a kapacitással azonos. Javasoljuk az olvasónak, hogy válasszon zérustól különböző induló folyamot és ezzel indulva is oldja meg a feladatot. A mindenkori szabad kapacitásokon történő útkereséseket az alábbiak mutatják:

1. útkeresés:

Az útkeresés során találtunk utat, amely az alábbi:

Ez az út folyamnövelő út, hiszen minden élén valamennyivel növelhető a folyam. Az úton az s-ből t-be maximálisan 3 mennyiségű folyam áramoltatható át a kapacitáskorlátok miatt. Az út kapacitása tehát az útbeli élek szabad kapacitásainak minimumaként adódik, azaz . Az út mindegyik élén ugyanannyivel kell növelni a folyamot a Kirchoff törvény miatt.

Javasoljuk, hogy a továbbiakban az út leírása helyett az út éleit (az út definiálása során már említett módon) a táblázatban szimbólummal jelöljük és ekkor az út kapacitása a szimbólummal jelölt számok minimumaként határozható meg, azaz = min{ }. A visszút éleit pedig jelöljük szimbólummal. Ezt mutatja az alábbi táblázat.

A táblázatban az élek ill. visszélek bejelölése esetén a szabad kapacitások módosítását az alábbiak szerint végezhetjük el:

2. útkeresés:

.

3. útkeresés:

.

4. útkeresés:

Vége az algoritmusnak, mert nem találtunk folyamnövelő utat. A táblázatból a maximális folyam és a minimális vágás feladatpár optimális megoldása az alábbiak szerint adódik.

A maximális folyamfeladat megoldása:

Az élekre adódó optimális mennyiségeket az eredeti kapacitástáblázat és az utolsó szabad kapacitás táblázat, mint mátrix különbsége adja.

A folyam maximális értékét többféle módon is kiolvashatjuk a táblázatból. Egyrészt a forrásból kifolyó folyamok összegeként, amelyet úgy kapunk, hogy a forrásnak megfelelő sorban lévő elemeket összeadjuk.

A folyam maximális értéke: .

Ugyanezt az eredmény kapjuk, ha a nyelőbe (t) befolyó folyamok összegét számoljuk, amelynél a nyelőnek megfelelő oszlopban lévő elemeket kell összeadni. Ha a forrásnak (s) megfelelő oszlopban ill. a nyelőnek megfelelő sorban lévő elemeket adjuk össze, akkor a folyam maximális értékének a (-1)-szeresét kapjuk. Ha a zérus folyamból indulunk ki, akkor az útkeresések során nyert folyamnövelő értékek összege is a folyam maximális értékét adja. Könnyen meggyőződhetünk arról, hogy a folyam valóban teljesíti a korlátozottsági, a ferde szimmetricitási feltételeket és a csomóponti megmaradási törvényt. Ez utóbbi akkor teljesedik, ha a közbülső (forrást és nyelőt kivéve) pontoknak megfelelő sorban és oszlopban lévő elemek összege zérus. Tekintsük például az 5 pontot és annak sorát. A sor pozitív számai azt mutatják, hogy az 5 pontból az és az éleken van kifolyás 1 ill. 2 mennyiségben, tehát összesen 3 mennyiségű folyam folyik ki az 5 pontból. A sor negatív értéke az , a ferdeszimmetricitás miatt , ez pedig az 5 pontba befolyó folyamot jelenti. Valóban igaz, hogy az 5 közbülső pontba befolyó és onnan kifolyó folyamösszegek megegyeznek.

A minimális vágás feladat megoldása:

Az utolsó címkézés során adódott vágás a minimális vágás. Az vágás ponthalmazai:

,

.

Mint ismert a címkézett pontok az ponthalmazt, a címkézetlen pontok pedig a ponthalmazt alkotják.

Az minimális vágás élei: .

Az minimális vágás átbocsátóképessége, vagyis a minimális értéke: .

Az vágás éleit a kapacitás táblázat lefedésével is ábrázolhatjuk. A értéke a fedetlen helyek kapacitásainak összegeként adódik.

Az s-ből -be irányuló folyam maximális értéke és az s-et t-től elválasztó vágás minimális átbocsátóképessége valóban megegyezik, amelyet a FORD-FULKERSON tétel állított. A folyamprobléma és a vágás feladat optimális megoldását a hálózaton is szemléltethetjük. Az eredeti (nem teljessé alakított) hálózaton a feladatpár megoldása egyszerűen adódik, mivel csupán a pozitív értékű folyamokat kell tekinteni. Az alábbi hálózaton az élekre írt számok a folyamot jelentik.

Láthatjuk azt is, hogy optimális esetben a vágás minden éle telített.

2. Példa:

Adott az alábbi „honnan-hova” táblázattal egy hálózat és abban egy induló folyam. Határozza meg az 5 pontból a 2 pontba irányuló maximális folyamot!

0. lépés:

A kapacitás táblázata (baloldalon) és az induló folyam táblázata (jobboldalon) az eredeti hálózaton az alapadatok alapján a következő:

            

A hálózatot kiegészítjük teljes hálózattá. Az eredetileg nem létező élek kapacitása zérus lesz.

A folyamot is elő kell készíteni, mivel az ferdeszimmetrikus, így a visszafelé mutató éleken ellenkező előjelű lesz a folyam.

A teljes hálózaton a kapacitás és a folyam táblázata az alábbi:

            

1. lépés:

Először az induló szabad kapacitás () táblázatot kell meghatározni, amely , tehát a fenti balodali táblázat elemeiből ki kell vonni a jobboldali táblázat elemeit. Természetesen a fenti táblázatok felrajzolása nélkül sem bonyolult a szabad kapacitás táblázat előállítása, táblázatelemenként kitölthető egy kis odafigyeléssel. Ezután elkezdhetjük az útkeresések sorozatát.

2. lépés:

Nem találtunk növelő utat a forrásból a nyelőbe, így megkaptuk az optimális megoldást. A primál és a duál feladat optimális megoldását az alábbiakban adjuk meg:

A maximális folyamfeladat megoldása:

Az élekre adódó optimális mennyiségeket az eredeti kapacitástáblázat és az utolsó szabad kapacitás táblázat, mint mátrix különbsége adja.

A folyam maximális értéke: .

A minimális vágás feladat megoldása:

Az utolsó címkézés során adódott vágás a minimális vágás. Az vágás ponthalmazai:

,

.

A vágást lefedéssel is ábrázolhatjuk a kapacitás táblázaton.

Az minimális vágás átbocsátóképessége, vagyis a minimális értéke: 11. Ez nem más mint a fedetlen helyeken lévő kapacitások összege.

Javasoljuk az olvasónak gyakorlás érdekében, hogy az induló folyam figyelembevétele nélkül is oldja meg a feladatot.

Megjegyzések:

  1. Előfordulnak olyan folyamfeladatok is, amelyeknél a hálózat élein a folyamra nemcsak felső korlátok (), hanem alsó korlátok is szerepelnek, ekkor a korlátozási feltétel

    Az alábbiakban megmutatjuk, hogy egyszerűen visszavezethető a standard zérus alsó korlátos (nemnegatív) feladatra. Az döntési változó helyett vezessük be az új változót a következőképpen

    Ekkor az változóra a szokásos nemnegativitási feltétel teljesül és a korlátozás pedig az alábbi lesz:

    A célfüggvényben is és a közbülső pontokra felírt egyenleteknél is a transzformáció elvégzése után egy standard folyamfeladatot kell megoldani, amelynek optimális megoldásából egyszerűen számítható az eredeti folyamfeladat optimális megoldása.

  2. Előfordulnak olyan folyamfeladatok is, amelyeknél több forrás és nyelő van. Ekkor a folyamot úgy értelmezzük, hogy az összes forrásból az összes nyelőbe áramló folyam maximális értékét keressük.

    Az alábbiakban megmutatjuk, hogy egyszerűen visszavezethető a standard (egy forrással és egy nyelővel rendelkező) feladatra. Vegyünk fel a hálózatban egy s és egy t pontot és ezeket tekintsük forrásnak ill. nyelőnek. Az s pontból mindegyik eredeti forráshoz vegyünk fel élet végtelen kapacitással. A t pontba mindegyik eredeti nyelőből vegyünk fel élet végtelen kapacitással. Most ezen a módosított hálózaton keressük meg az s-ből t-be irányuló maximális folyamot. Ennél a feladatnál nyilván az eredeti források és a nyelők közbülső pontoknak tekintendők, amelyekre szintén érvényes Kirchoff csomóponti törvénye. Nem nehéz belátni, hogy az így nyert feladat optimális megoldása az eredeti feladatnak is optimális megoldása lesz.