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.
Where it lands in Jayverse
- Verex: route split orders as min-cost max-flow, not a greedy allocator. When a large order fills across multiple liquidity sources or market makers, model it as a flow problem rather than an ad hoc split.
- Verex: net settlement obligations as min-cost flow before pushing on-chain transfers. Add a test verifying the netted result matches gross obligations, so batching debts and credits actually reduces the number of on-chain transfers it claims to.
- OFA: match solvers to intents as bipartite matching. Reason about the auction's worst case with Dinic's/König's theorem rather than an unbounded search, when assigning solvers to competing intents.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| reduces to | ~로 환원되다, 결국 ~ 문제가 되다 · 복잡한 문제를 더 단순한 형태로 바꿔 풀 때 · "Bipartite matching reduces to a flow problem" |
| falls out naturally as | 자연스럽게 ~로 도출되다 · 별도 모델링 없이도 저절로 그 형태가 나온다는 뜻 · "both fall out naturally as min-cost flow models" |
| follows as a special case | ~의 특수한 경우로서 성립하다 · 더 일반적인 정리에서 자동으로 따라 나오는 결과 · "follows as a special case of the min-cut theorem" |
| end up -ing | 결국 ~하게 되다 · 잘못된 모델링을 하면 비효율적인 방법에 빠지게 된다는 뜻 · "ending up writing an exponential-time search instead" |
| net (v.) | (채권채무를) 상계처리하다 · 여러 거래를 서로 상쇄시켜 이체 건수를 줄이는 것 · "netting a large set of debt-credit relationships" |
| push flow along | (경로를 따라) 흐름을 밀어넣다 · 그래프 알고리즘에서 유량을 보내는 동작 · "push flow along it" |
| LP | 선형계획법(Linear Programming) · 최대유량-최소컷 정리가 LP 쌍대성의 조합론적 특수 사례임을 설명할 때. "a combinatorial instance of LP duality" |
| MCMF | 최소비용 최대유량(Min-Cost Max-Flow) · 비용까지 고려한 자원-수요 배분 문제의 일반형. "generalizes to min-cost max-flow (MCMF)" |
| König's theorem | 쾨니그 정리 · 이분그래프에서 최대 매칭 크기가 최소 정점 커버 크기와 같다는 정리, 최소컷 정리의 특수 사례. "König's theorem — that the maximum matching size equals" |
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/.