6. fejezet - Csúcskapacitásos folyamfeladat

6.1. 6.1. A feladat megfogalmazása

Tekintsünk egy olyan hálózatot, amelyben az élekre vonatkozó élkapacitásokon kívül a pontokra vonatkozó , egész értékű csúcskapacitások is adottak. A folyamfeladatot most úgy lehet megfogalmazni, hogy a csúcsokra vonatkozó megmaradási feltételeken és az élekre vonatkozó korlátozottsági megkötéseken kívül a csúcsokra kirótt megszorítások is teljesüljenek, azaz egyik közbülső pontban se haladja meg a kifolyó folyam (amely egyenlő a befolyó folyammal) a csúcs kapacitását. Az ilyen problémát csúcskapacitásos folyamfeladatnak nevezzük. Ha a csúcsokra kirótt csúcskapacitások mindegyike végtelen nagy érték, akkor nyilvánvaló, hogy az előző fejezetben ismertetett standard folyamfeladathoz jutunk. Bizonyos gyakorlati problémákban természetes követelmény a csúcskapacitás. Ilyen pontok lehetnek például az áruszállításnál az átrakodási pontok, csapatmozgásoknál az utánpótlási pontok, szárazföldi csővezetékeknél a tisztítóállomások vagy a hírközlési hálózatokban az erősítő berendezések. A csúcskapacitásos maximális folyamfeladathoz is rendelhető egy minimális vágás feladat. Itt azonban a vágást másképpen kell definiálni, ezt a vágást vegyes vágásnak nevezzük, amelynek elemei nemcsak élek, hanem pontok is lehetnek. A vegyes vágás átbocsátóképességét a vágásban szereplő élek és pontok kapacitásainak összege adja.