Graph Theory37 sections · 1633 units
Open in Course

Residual Graph

(Captures remaining capacity)

The residual graph shows remaining capacity after you have assigned some flow. For each edge (u,v)(u,v) with flow f(u,v)f(u,v) and capacity c(u,v)c(u,v), the residual graph has:

1.1. Forward edge (u,v)(u,v) with capacity c(u,v)f(u,v)c(u,v) - f(u,v) (remaining capacity).

2.2. Backward edge (v,u)(v,u) with capacity f(u,v)f(u,v) (allows you to undo flow).

The backward edge is the core concept. It lets you reroute flow if you find a better path later. This is what makes flow algorithms work.