Graph Theory37 sections · 1633 units
Open in Course

Core Idea - Flow Decomposition

(Extracting paths from flow)

After computing max flow, the residual graph has flow on some edges. For each unit of flow, trace a path from ss to tt using edges with positive flow. You are reconstructing the paths. Start at ss, follow any edge with flow >0> 0 to the next vertex, and repeat until you reach tt.

Subtract 11 from the flow on each edge you use. Repeat this process until no more flow remains. Each trace gives you one edge-disjoint path. The subtraction ensures paths do not overlap on edges.