최대 유량 & 최소 컷

수도관 네트워크가 있다. 각 관에는 초당 최대로 흘릴 수 있는 물의 양(용량)이 정해져 있다. 발전소 S에서 도시 T까지, 한꺼번에 보낼 수 있는 물의 최대량은 얼마일까? 이 질문을 푸는 것이 Ford-Fulkerson 알고리즘이고, 그 답이 바로 네트워크의 병목(최소 컷)과 정확히 같다.

1. 유량 네트워크의 규칙

용량 제한 — 어떤 관도 용량 c(u,v)보다 많이 흘릴 수 없다. 0 ≤ f(u,v) ≤ c(u,v)
유량 보존 — S와 T를 뺀 모든 지점에서 들어온 물 = 나간 물. 물은 중간에 생기거나 사라지지 않는다.
총 유량 — S에서 빠져나가는 순수 물의 양. 이것과 T로 들어가는 양은 항상 같다.

직관: 관을 아무리 굵게 만들어도, 중간 어딘가 좁은 구간 하나가 전체 처리량을 결정한다. 그 "좁은 구간의 묶음"이 최소 컷이다.

2. 직접 흘려보기 — 증가 경로(augmenting path)

다음 증가 경로 버튼을 누르면, 아직 여유가 남은 관만 따라 S→T 경로를 하나 찾는다(BFS, 가장 짧은 경로부터). 그 경로에서 가장 좁은 관의 여유(병목)만큼 물을 더 흘린다. 더 이상 경로가 없으면 그 값이 최대 유량이다.

0현재 총 유량

0찾은 증가 경로 수

–최소 컷 용량

S(발전소)에서 T(도시)까지 물을 최대한 흘려보자. 관 위 숫자는 흐르는 양 / 용량.

3. 되돌리는 간선(reverse edge)이 핵심

탐욕적으로 아무 경로나 채우면 잘못된 선택에 갇힐 수 있다. Ford-Fulkerson은 이를 잔여 그래프(residual graph)로 해결한다.

관 u→v에 용량 10 중 7을 흘리고 있다면 → 앞으로 갈 여유 간선 u→v: 남은 3
동시에 되돌리는 간선 v→u: 7 (이미 보낸 7만큼 "취소"할 수 있다는 뜻)

나중에 찾은 경로가 되돌리는 간선을 지나가면, 앞서 보낸 물의 일부를 다른 길로 재배치하는 효과가 난다. 덕분에 순서와 상관없이 항상 진짜 최댓값에 도달한다.

4. 최대 유량 = 최소 컷 정리

컷(cut)이란 지점들을 S가 속한 쪽과 T가 속한 쪽 두 그룹으로 가르는 것이다. 이때 S쪽 → T쪽으로 건너가는 관들의 용량 합이 그 컷의 용량이다.

정리 — 어떤 유량도 어떤 컷의 용량을 넘을 수 없다. 그리고 최대 유량은 정확히 가장 작은 컷의 용량과 같다. 위 시뮬레이터에서 알고리즘이 끝난 뒤, 잔여 그래프에서 S로부터 도달 가능한 지점이 바로 S쪽 그룹이고, 그 경계를 건너는(모두 가득 찬) 관들이 최소 컷이다. — 빨간 점선으로 표시된다.

이 위 예제의 최소 컷은 {S, A, B} 대 {C, D, T}로, 건너는 관은 A→C(6), B→C(4), B→D(6) = 16.

5. 알고리즘 (Edmonds-Karp)

def max_flow(cap, s, t):        # cap[u][v] = 용량
    flow = 0
    while True:
        # BFS로 잔여 용량 > 0 인 간선만 따라 s→t 경로 탐색
        parent = bfs(cap, s, t)
        if parent is None:
            break                  # 더 이상 증가 경로 없음 → 종료
        # 경로 위 최소 잔여 용량 = 병목
        b = min(residual(u, v) for (u, v) in path)
        for (u, v) in path:
            cap[u][v] -= b          # 여유 간선 감소
            cap[v][u] += b          # 되돌리는 간선 증가
        flow += b
    return flow

방식	경로 선택	시간 복잡도
Ford-Fulkerson	아무 경로 (DFS)	O(E · max_flow)
Edmonds-Karp	가장 짧은 경로 (BFS)	O(V · E²)
Dinic	레벨 그래프 + blocking flow	O(V² · E)

6. 어디에 쓰나

이분 매칭 — 지원자–일자리를 연결. 양쪽에 가상의 S, T를 붙이고 모든 용량을 1로 두면 최대 유량 = 최대 매칭 수.
이미지 분할(segmentation) — 픽셀을 전경/배경으로 나누는 문제를 최소 컷으로 푼다(graph cut).
네트워크 신뢰도 — 링크 몇 개를 끊어야 두 서버가 단절되는가 = 최소 컷.
프로젝트 선택, 스케줄링 — 이익/비용 트레이드오프를 최소 컷으로 모델링.

관련 학습: BFS/DFS · 다익스트라 · 최소 신장 트리

한 줄 요약 — 여유가 남은 관을 따라 S→T 경로를 찾아 병목만큼 계속 흘리고(되돌리는 간선 포함), 경로가 없어지면 멈춘다. 그 값은 네트워크를 두 쪽으로 가르는 가장 약한 관 묶음(최소 컷)의 용량과 정확히 같다.