네트워크 플로우로 최대 유량과 최소 컷 모델링하기

용량 제약 아래에서 보낼 수 있는 흐름

네트워크 플로우는 방향 그래프 (G=(V,E)), 용량 함수 (c(u,v) \ge 0), 소스 (s), 싱크 (t)로 구성한다. 흐름 (f(u,v))는 (0 \le f(u,v) \le c(u,v))라는 용량 제한과 (\sum f(in)=\sum f(out))라는 유량 보존 조건을 만족해야 한다.

목표는 (s)에서 (t)로 보내는 총 유량 (\sum_v f(s,v))를 최대화하는 것이다. 네트워크 링크뿐 아니라 작업 배정, 공급망, 이미지 분할처럼 자원과 이동 경로를 그래프로 표현할 수 있는 문제에 같은 구조를 적용할 수 있다.

현재 해를 개선하는 핵심은 잔여 그래프다. 정방향 잔여 용량은 (r(u,v)=c(u,v)-f(u,v))이고, 역방향 잔여 용량은 (r(v,u)=f(u,v))다. 역방향 간선이 있어야 앞선 선택을 되돌리고 유량을 다른 경로로 재배치할 수 있다. 소스에서 싱크까지 남은 용량이 있는 증대 경로를 찾은 뒤, 그 경로의 병목 용량만큼 유량을 늘리는 작업을 반복한다.

최대 유량/최소 컷 정리에 따르면 어떤 컷 ((S,T))의 용량 (cap(S,T)=\sum c(u,v), u\in S, v\in T)에 대해 최대 유량 값과 최소 컷 용량은 같다. 알고리즘이 끝난 뒤 잔여 그래프에서 (s)로부터 도달 가능한 정점 집합 (S)를 구하면 최소 컷을 유도할 수 있다.

⤢✕

음수 용량 입력은 허용되지 않는다. (s=t)이면 유량은 0을 반환한다. 부동소수 용량을 사용할 때는 상대·절대 오차 한계를 정해야 한다.

경로를 고르는 방식이 달라지면

Ford-Fulkerson은 증대 경로를 찾는 프레임워크이며, 어떤 경로를 선택할지는 정하지 않는다. DFS처럼 임의의 탐색 전략을 사용할 수 있고 정수 용량에서는 유한 시간 종료가 보장된다. 다만 실제 성능은 경로 선택에 크게 좌우된다.

Edmonds-Karp는 BFS로 간선 수 기준 최단 증대 경로를 택하는 Ford-Fulkerson의 구현 방식이다. 시간 복잡도는 (O(VE^2))로 보장되며, 구현이 단순하고 성능을 예측하기 쉽다.

항목	Ford-Fulkerson	Edmonds-Karp
성능(복잡도)	경로 선택에 따라 상이, 최악 시 매우 비효율, 정수 용량 시 유한 종료	O(VE^2) 보장, 실무에서 안정적
확장성	경로 전략 최적화 필요, 큰 그래프에서 변동성 큼	BFS 기반 예측 가능한 확장성
일관성	비결정적 결과(경로 선택 영향)	결정적 결과(경로 고정 규칙)
안정성	부동소수 용량 시 진동 가능, ε 필요	BFS로 반복 수 억제, 수렴 안정
운영 편의	고급 튜닝 여지 큼(스케일링 등)	구현 단순, 디버깅 용이

경로마다 병목 용량을 계산하면 한 번의 반복에서 가능한 최대 증분을 반영할 수 있다. 갱신 시 경로의 각 간선 ((u,v))에서 (r(u,v))는 줄고 (r(v,u))는 늘어난다. 이 역방향 간선이 유량 롤백과 재배치를 담당한다.

모든 용량이 정수라면 증대량도 정수이므로 반복 횟수는 유한하다. 반면 실수 용량에는 정밀도 문제가 있어 ε-임계 처리가 필요하다. 구현에서는 인접 리스트와 해시(딕셔너리) 기반의 잔여 그래프가 실용적이며, 역방향 간선을 미리 만들어 두면 갱신 비용을 상수화할 수 있다. 희소 그래프에서는 메모리와 시간의 균형을 고려해야 하고, 탐색과 갱신 사이의 경쟁 조건 때문에 병렬화에는 제약이 있다.

초대규모 그래프에서 질의가 빈번하다면 Dinic, Push-Relabel 같은 대안을 검토할 수 있다.

흐름 모델이 유용한 문제

네트워크 라우팅과 대역폭 할당에서는 여러 경로로 트래픽을 나누고, 링크 용량 제약 아래의 체증 구간을 찾아 증설 우선순위를 정할 수 있다.

이분 매칭과 작업 스케줄링도 최대 유량 문제로 환원할 수 있다. 작업과 자원을 정점으로 두고 시간창과 자원 용량을 간선 용량으로 표현한다.

이미지 분할에서는 픽셀 또는 슈퍼픽셀 사이의 에너지 최소화 문제를 (s)-(t) 최소 컷으로 바꿔 전경과 배경을 나눈다. 공급망과 생산 계획에서는 원재료에서 공정, 제품까지의 흐름을 그래프로 표현해 병목 공정을 찾고 증설을 시뮬레이션한다. 회선 임대와 요금 정책에는 최소 컷 분석을 적용해 임대 구간의 가치를 평가하고 가격 책정과 SLA 설계의 근거를 마련할 수 있다.

Edmonds-Karp는 (E=10^4), (V=10^3) 규모에서 수 초 내 해를 구할 수 있다. 다만 이는 하드웨어와 그래프 구조에 의존한다. 트래픽 재분배나 스케줄링을 적용하면 자원 활용률을 ≥ 10~30% 개선할 수 있는 사례가 있으며, 병목 구간을 명확히 보여 주고 모델·알고리즘·결과 사이의 추적 가능성도 높인다.

BFS 기반 Edmonds-Karp 구현

Python 3.9+ 환경에서 외부 라이브러리 없이 구현할 수 있다. 그래프는 cap[u][v] = 용량 형태의 dict-of-dict 용량 맵을 사용한다.

from collections import deque
from math import inf

def edmonds_karp(capacity, s, t):
    # 노드 집합 구성
    nodes = set(capacity.keys())
    for u in capacity:
        nodes.update(capacity[u].keys())
    if s == t:
        return 0, {s}, set(), []

    # 잔여 그래프 초기화
    residual = {u: {} for u in nodes}
    for u in nodes:
        for v in nodes:
            residual[u][v] = 0
    for u in capacity:
        for v, c in capacity[u].items():
            if c < 0:
                raise ValueError("용량은 음수 불가")
            residual[u][v] += c  # 병렬 간선 합산
            # 역방향 간선 초기 0 유지

    max_flow = 0

    def bfs():
        parent = {s: None}
        flow = {s: inf}
        q = deque([s])
        while q:
            u = q.popleft()
            for v, r in residual[u].items():
                if r > 0 and v not in parent:
                    parent[v] = u
                    flow[v] = min(flow[u], r)
                    if v == t:
                        return parent, flow[v]
                    q.append(v)
        return parent, 0

    while True:
        parent, delta = bfs()
        if delta == 0:
            break
        max_flow += delta
        v = t
        while v != s:
            u = parent[v]
            residual[u][v] -= delta
            residual[v][u] += delta
            v = u

    # 최소 컷 S 집합 계산
    visited = set()
    q = deque([s])
    visited.add(s)
    while q:
        u = q.popleft()
        for v, r in residual[u].items():
            if r > 0 and v not in visited:
                visited.add(v)
                q.append(v)

    S = visited
    T = set(nodes) - S
    cut_edges = []
    for u in S:
        for v in T:
            if capacity.get(u, {}).get(v, 0) > 0:
                cut_edges.append((u, v, capacity[u][v]))

    return max_flow, S, T, cut_edges

if __name__ == "__main__":
    # 예제 그래프
    cap = {
        's': {'a': 10, 'c': 10},
        'a': {'b': 4, 'c': 2, 'd': 8},
        'b': {'t': 10},
        'c': {'d': 9},
        'd': {'b': 6, 't': 10},
        't': {}
    }
    maxflow, S, T, cut = edmonds_karp(cap, 's', 't')
    print("max flow:", maxflow)
    print("min cut S:", S, "T:", T)
    print("cut edges:", cut)

입력은 용량 맵과 소스 (s), 싱크 (t)다. 함수는 BFS로 증대 경로를 반복 탐색하고 잔여 그래프를 갱신한 다음, 종료 시점의 (S) 집합을 계산한다. 반환값은 최대 유량, 최소 컷 분할 ((S,T)), 컷 간선 목록이다.

정수 용량을 권장하며 실수 용량에는 ε-절삭 또는 정수 스케일링을 적용할 수 있다. 정확도와 반복 수 사이에는 트레이드오프가 있다. 대규모 그래프는 희소 표현을 유지하고 불필요한 0 간선을 만들지 않는 편이 좋지만, 메모리 사용량과 연산 단순화 사이의 균형을 함께 봐야 한다. 빈번한 질의 환경에서는 정점 분할, 계층 그래프 전처리와 Dinic, Push-Relabel 같은 고급 알고리즘을 고려할 수 있다.