Az alábbi páros gráf maximális párosítását keressük (a sárga és a kék csúcsok között):

Hány elemű a maximális párosítás élhalmaza?

A maximális párosítást előállító algoritmus használata során minden él súlya +1 vagy -1, attól függően, hogy kimenő vagy bemenő élről van-e szó.

Tekintsük az alábbi folyamot.

Mennyi a minimális vágás értéke ennek a hálózatnak?

Mennyi a maximális folyam értéke az alábbi hálózat esetén?

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot.

Legyen egy vágása a fenti hálózati folyamnak: ({s, v1, v3},{v2, v4, t}). Azaz S={s, v1, v3}, T={v2, v4, t}.

Mennyi az (S, T) vágáson keresztülfolyó folyam értéke?

Tekintsük az alábbi hálózatot és az ehhez tartozó folyamot.

Legyen egy vágása a fenti hálózati folyamnak: ({s, v1, v3},{v2, v4, t}). Azaz S ={s, v1, v3}, T={v2, v4, t}.

Mennyi az (S, T) vágás kapacitása?

Futtassuk le az Edmonds-Karp algoritmust az alábbi hálózaton:

Hány alkalommal talál javító utat az algoritmus?

Egy G hálózat tetszőleges folyamának a nagysága nem lehet nagyobb, mint bármely vágásának az értéke.

Adott egy tetszőleges G(V,E) élsúlyozott, irányított, körmentes gráf, ahol minden él súlya nem-negatív. Mely algoritmusokat használhatjuk az adott csúcsból induló legrövidebb utak meghatározására, ha biztosan helyes eredményt szeretnénk kapni?

Adott egy tetszőleges G(V,E) élsúlyozott, irányított, körmentes gráf. Mely algoritmusokat használhatjuk az adott csúcsból induló legrövidebb utak meghatározására, ha biztosan helyes eredményt szeretnénk kapni?