6.3. 6.3. Példamegoldás

Határozzuk meg az alábbi hálózaton a csúcskapacitásos folyamfeladat és duálisának optimális megoldását!

Először végezzük el a hálózat kibővítését, vezessük be a „be” és „ki” pontokat.

1. lépés

2. lépés

3. lépés

Nem találtunk utat, vége az algoritmusnak.

Eredmények:

  1. A kibővített hálózaton:

    Maximális folyam értéke: 3

    Minimális vágás: , a vágás átbocsátóképessége: 3

  2. Az eredeti hálózaton:

    Maximális folyam értéke: 3

    Minimális vegyes vágás: élek: , pontok: 2, a vegyes vágás átbocsátóképessége: 3