Max Flow, Min Cut, and Matching TODO
Concept
A flow network is a directed graph where every edge has a capacity, and the max-flow problem asks for the largest flow that can be pushed from a source to a sink. The max-flow min-cut theorem says that the minimum total capacity over all cuts separating the source and sink equals the maximum flow exactly — a combinatorial instance of LP duality. The basic algorithmic approach is to repeatedly find an augmenting path in the residual graph and push flow along it; depending on how the path is chosen, this splits into Edmonds-Karp (shortest augmenting path) or Dinic's algorithm (level graph plus blocking flow). Bipartite matching reduces to a flow problem where every capacity is set to 1, and in that setting König's theorem — that the maximum matching size equals the minimum vertex cover size — follows as a special case of the min-cut theorem. Once cost is factored in, this generalizes to min-cost max-flow (MCMF), the general form of resource-to-demand allocation.
Whenever a "who gets what, how much" question comes up — scheduling, order allocation, node-to-shard assignment — it usually reduces to flow or matching, and getting the model wrong means ending up writing an exponential-time search instead.
Code & Formula
# Day 12: 최대 유량·최소 컷과 매칭 — Edmonds-Karp로 최대 유량을 구하고 최소 컷을 복원
# BFS로 최단 증가 경로를 찾아 유량을 밀어 넣고, 잔여 그래프에서 도달 가능한 집합이 곧 최소 컷이다.
from collections import defaultdict, deque
def edmonds_karp(capacity, source, sink):
graph = defaultdict(dict)
for (u, v), cap in capacity.items():
graph[u][v] = graph[u].get(v, 0) + cap
graph[v].setdefault(u, 0)
def bfs_path():
parent = {source: None}
queue = deque([source])
while queue:
u = queue.popleft()
if u == sink:
break
for v, cap in graph[u].items():
if cap > 0 and v not in parent:
parent[v] = u
queue.append(v)
if sink not in parent:
return None
path, v = [], sink
while parent[v] is not None:
path.append((parent[v], v))
v = parent[v]
return list(reversed(path))
flow = 0
while True:
path = bfs_path()
if path is None:
break
path_flow = min(graph[u][v] for u, v in path)
for u, v in path:
graph[u][v] -= path_flow
graph[v][u] += path_flow
flow += path_flow
reachable, queue = {source}, deque([source])
while queue:
u = queue.popleft()
for v, cap in graph[u].items():
if cap > 0 and v not in reachable:
reachable.add(v); queue.append(v)
min_cut = [(u, v) for (u, v) in capacity if u in reachable and v not in reachable]
return flow, min_cut
capacity = {
("S", "A"): 3, ("S", "B"): 2,
("A", "B"): 1, ("A", "T"): 2,
("B", "T"): 3,
}
max_flow, min_cut = edmonds_karp(capacity, "S", "T")
print("최대 유량 =", max_flow)
print("최소 컷 간선 =", min_cut, "(용량 합 =", sum(capacity[e] for e in min_cut), ")")
docs/code/algorithms/algorithms-12.py
Exercise
Implement bipartite matching using Dinic's algorithm, then, for the same input, reconstruct the minimum vertex cover from the minimum cut and verify König's theorem in code.
Practical Connection
Splitting multiple orders across multiple liquidity sources for fills, or netting a large set of debt-credit relationships at settlement to reduce the number of on-chain transfers, both fall out naturally as min-cost flow models.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.