Matchings and Flow Summary

Graph Theory · Axiom Academy

SUMMARY Matchings and Network Flow A concise review of matching theory, network flows, and their fundamental connections. Matching: A set of edges M where no two edges share a vertex Maximum Matching: A matching with the largest possible number of edges Perfect Matching: A matching that covers all vertices (M-saturated for all vertices) Augmenting Path: An alternating path between two M-unsaturated vertices Key Property: A matching is maximum if and only if there is no augmenting path Flow Network: A directed graph with source s, sink t, and edge capacities c(e) Valid Flow: Satisfies capacity constraints and flow conservation at all intermediate vertices Flow Value: The total flow out of source s (equals total flow into sink t) Cut: A partition (S, T) where s ∈ S and t ∈ T Cut Capacity: Sum of capacities of edges from S to T Initialize: Start with zero flow on all edges (f(e) = 0 for all e) Build Residual Graph: For each edge, forward capacity = c(e) − f(e), backward capacity = f(e) Find Augmenting Path: Search for an s-t path in the residual graph using BFS or DFS Augment Flow: Find bottleneck capacity along the path and increase flow by this amount Repeat: Continue until no augmenting path exists in the residual graph Termination: The algorithm terminates with a maximum flow (equals minimum cut capacity) Reducing Bipartite Matching to Network Flow Setup: Given bipartite graph G = (X ∪ Y, E), create flow network with source s and sink t

This is the written version of the interactive lesson above. See the full Graph Theory course.