Graph Theory37 sections · 1633 units
Open in Course

Vocabulary - Residual Graph

Remaining capacities after ...

The residual graph shows how much capacity remains after assigning some flow. For each edge with flow ff and capacity cc, the residual graph has a forward edge with capacity cfc - f and a backward edge with capacity ff.

The backward edge allows you to undo flow if needed. This is what makes the algorithm work. You update the residual graph after each augmentation. The algorithm searches for paths in this graph.