[prev] 77 [next]

Residual Network

Assume …   flow network G=(V,E)  and  flow f(v,w)

Residual network (V,E'):

  • same vertex set V
  • for each edge v →c w ∈ E …
    • f(v,w) < c    ⇒ add edge (v →c-f(v,w) w) to E'
    • f(v,w) > 0    ⇒ add edge (v ←f(v,w) w) to E'


Example:

[Diagram:Pic/flow.png]

[Diagram:Pic/residual.png]