6.2. 6.2. A feladat matematikai vizsgálata és megoldási algoritmusa

A csúcskapacitásos folyamfeladatra az alábbi ún. általánosított maximális folyam-minimális vágás tétel érvényes:

TÉTEL (Általánosított FORD-FULKERSON tétel):

Csúcs- és élkapacitásokkal is rendelkező hálózatban az -ből a -be irányuló folyam maximális értéke egyenlő az -et -től elválasztó vegyes vágás minimális átbocsátóképességével.

Bizonyítás.

Konstruktív jellegű a bizonyítás, kiolvasható belőle a megoldási algoritmus is.

Növeljük meg a hálózat méretét azáltal, hogy a csúcskapacitásokkal rendelkező pontokat duplázzuk meg és e két pont között vegyünk fel egy élet, amelynek élkapacitása legyen egyenlő a pont csúcskapacitásával. Legyen a csúcskapacitásos pont az i, ekkor a két pont legyen és , az élkapacitás pedig Az pontba érkeznek be azok az élek, amelyek az i pontba érkeztek be, az pontból pedig azok az élek indulnak ki, amelyek az i pontból indultak ki. Ezzel az átalakítással egy csúcskapacitás nélküli folyamfeladathoz jutottunk. Erre a feladatra érvényes a FORD-FULKERSON tétel és ismerjük a feladat megoldási algoritmusát is. Könnyen észrevehető, hogy a keletkező csúcskapacitás nélküli feladat minimális vágásában, ha van olyan él, amelyet most vezettünk be, akkor az a csúcskapacitásos feladathoz tartozó minimális vágásban pontot fog jelenteni. Így érthető, hogy a csúcskapacitásos folyamfeladatának duálisa minimális vegyes vágás feladat.

Algoritmus:

A megoldási algoritmus tehát megegyezik a standard folyamprobléma megoldási algoritmusával, csupán előkészületi munkákat (pontok duplázása és élek felvétele) kell végezni a standard alakra hozáshoz.