네트워크 흐름

1. 개요[편집]

네트워크 흐름(network flow)은 용량이 정해진 간선들로 이루어진 그래프 위에서, 각 간선에 얼마씩 흘려보낼지를 정하는 최적화 문제군이다. 수도관에 물을, 도로에 차를, 통신망에 패킷을, 전력망에 전류를 흘리는 상황을 하나의 수학적 틀로 묶어버린 물건이라 보면 된다.

유량 네트워크는 방향그래프 $G=(V,E)$와 간선 용량 $c: E \to \mathbb{R}_{\ge 0}$, 그리고 공급원 $s$와 흡수원 $t$로 정의된다. 흐름 $f: E \to \mathbb{R}_{\ge 0}$은 두 가지를 지켜야 한다.

• 용량 제약: 모든 간선에서 $0 \le f(u,v) \le c(u,v)$.
• 유량 보존: $s$, $t$를 제외한 모든 정점에서 들어온 만큼 나간다. $\sum_{u} f(u,v) = \sum_{w} f(v,w)$.

이 조건 아래 $s$에서 $t$로 흘려보낼 수 있는 총량 $|f|$를 최대화하는 것이 최대유량 문제(maximum flow problem)다. 형태만 보면 선형계획법의 특수한 경우지만, 구조가 워낙 좋아서 범용 LP 솔버보다 훨씬 빠른 전용 조합 알고리즘이 존재하고, 게다가 용량이 정수면 최적해도 반드시 정수라는 보너스가 붙는다.¹

2. 잔여 그래프와 증대 경로[편집]

최대유량 알고리즘의 핵심 도구는 잔여 그래프(residual graph) $G_f$다. 현재 흐름 $f$가 주어졌을 때, 간선 $(u,v)$의 잔여 용량을

$$c_f(u,v) = c(u,v) - f(u,v), \qquad c_f(v,u) = f(u,v)$$

로 정의한다. 앞의 항은 “앞으로 더 밀어넣을 수 있는 양”, 뒤의 항이 역방향 간선으로, “이미 보낸 흐름을 되돌릴 수 있는 양”이다. 이 역방향 간선이 이 이론의 진짜 발명품이다. 탐욕적으로 경로를 채우다 잘못 배분해도, 나중에 역방향으로 흘려 취소하면 되므로 알고리즘이 국소 최적에 갇히지 않는다.

$G_f$에서 잔여 용량이 양수인 간선만 따라 $s \to t$ 경로가 존재하면 이를 증대 경로(augmenting path)라 하고, 그 경로의 최소 잔여 용량만큼 흐름을 늘릴 수 있다. 여기서 바로 종료 조건이 나온다.

흐름 $f$가 최대 $\iff$ 잔여 그래프에 증대 경로가 없다.

3. 최대유량 알고리즘[편집]

포드-풀커슨 방법(Ford-Fulkerson, 1956)은 위 명제를 그대로 알고리즘으로 만든 것이다. 증대 경로를 아무거나 찾아 흐름을 늘리기를 경로가 없을 때까지 반복한다. 정수 용량이면 매 반복마다 유량이 최소 1씩 늘어나므로 $O(E \cdot |f^*|)$에 끝나는데, 유량 값 자체가 입력 크기에 들어가므로 이건 다항시간이 아니다. 용량이 $10^9$짜리 간선 두 개와 용량 1짜리 중간 간선을 지그재그로 놓으면 반복이 $2 \times 10^9$번 돌아가는 유명한 반례가 있다. 용량이 무리수면 아예 수렴하지 않고 엉뚱한 값으로 다가가는 예시까지 존재한다.

에드먼즈-카프 알고리즘(Edmonds-Karp, 1972)은 증대 경로를 BFS로 찾은 최단 경로(간선 수 기준) 로 고정한다. 그러면 각 간선이 병목이 되는 횟수가 $O(V)$로 제한되어 총 반복이 $O(VE)$, 전체 복잡도가 $O(VE^2)$가 된다. 용량 값과 무관한 최초의 다항 알고리즘이라는 데 의의가 있다.

디닉 알고리즘(Dinic, 1970)은 한 걸음 더 나간다. BFS로 $s$부터의 거리 레벨을 매겨 레벨 그래프를 만들고, 레벨이 정확히 1씩 증가하는 간선만 남긴 뒤 그 위에서 DFS로 차단 흐름(blocking flow)을 한 번에 찾는다. 한 페이즈가 끝나면 $t$까지의 최단거리가 반드시 1 이상 늘어나므로 페이즈는 최대 $V-1$번, 페이즈당 $O(VE)$로 총 $O(V^2E)$다. 실측에서는 이론치보다 훨씬 빠르고, 특수한 경우에는 복잡도 자체가 더 좋아진다 — 모든 용량이 1인 단위 용량 네트워크에서는 $O(E\sqrt{E})$, 이분 매칭에 적용하면 $O(E\sqrt{V})$가 되어 홉크로프트-카프 알고리즘과 같은 경계에 도달한다.

이후 계보는 밀어내기-재라벨(push-relabel, Goldberg-Tarjan)로 이어진다. 경로를 통째로 찾는 대신 정점에 높이(라벨)를 매기고 국소적으로 초과 유량을 밀어내는 방식이라 병렬화에 유리하고, 동적 트리를 얹으면 $O(VE\log(V^2/E))$까지 내려간다. 실무 라이브러리는 보통 디닉이나 push-relabel을 얹고 있다.

4. 최대유량-최소절단 정리[편집]

이 분야의 대표 정리이자, 조합 최적화에서 가장 우아한 결과 중 하나.

$s$-$t$ 절단은 정점 집합을 $s \in S$, $t \in T$로 나누는 분할이고, 그 용량은 $S$에서 $T$로 향하는 간선 용량의 합 $c(S,T) = \sum_{u \in S, v \in T} c(u,v)$이다. 역방향 간선은 세지 않는다.

최대유량-최소절단 정리: 임의의 유량 네트워크에서 최대유량의 값은 최소 절단의 용량과 정확히 같다.

한쪽 방향(약한 쌍대성)은 쉽다. 어떤 흐름이든 $S$에서 $T$로 건너가야 하므로 $|f| \le c(S,T)$다. 반대 방향은 최대유량에서 잔여 그래프상 $s$에서 도달 가능한 정점 집합을 $S$로 잡으면 그 절단이 정확히 포화됨을 보여 증명한다. 이 구조가 선형계획법 강쌍대정리의 조합적 실현이라는 점도 중요하다 — 최대유량 LP의 쌍대문제가 바로 최소절단(의 LP 완화)이고, 접속행렬이 전체 단모듈이라 완화가 정수해에서 딱 맞아떨어진다. 자세한 논의는 최대유량 최소절단 정리 문서로.

5. 최소비용 흐름[편집]

용량뿐 아니라 간선마다 단위 비용 $a(u,v)$가 붙고, 요구 유량 $F$를 가장 싸게 보내라는 문제가 최소비용 흐름(min-cost flow)이다.

$$\min \sum_{(u,v) \in E} a(u,v) f(u,v) \quad \text{s.t.} \quad \text{용량 제약, 보존 제약, } |f| = F$$

수송문제·배정문제·최단경로·최대유량이 전부 이것의 특수 사례라서, 조합 최적화의 스위스 아미 나이프 취급을 받는다. 대표 해법은 세 갈래다.

• 음의 순환 소거(cycle canceling): 아무 실행가능 흐름에서 시작해, 잔여 그래프에 비용이 음수인 순환이 있으면 그 순환을 따라 흘려 비용을 낮춘다. 음의 순환이 없어지면 최적. 최적성 조건 자체가 명쾌하다.
• 연속 최단경로(successive shortest path): 0에서 시작해 매번 잔여 그래프의 최단(비용) 경로로만 증대한다. 음수 간선이 생기므로 존슨 퍼텐셜로 재가중해 다익스트라를 쓴다.
• 네트워크 심플렉스(network simplex): 심플렉스법을 네트워크 구조에 특화시킨 것으로, 기저가 곧 신장트리라 $B^{-1}$을 명시적으로 다룰 필요가 없다. 실무 대형 문제에서 가장 빠른 축.

여기서도 정수성 정리가 성립한다. 용량과 공급/수요가 정수면 최적 흐름도 정수로 잡을 수 있다. 이 성질 덕분에 배정·매칭처럼 본질적으로 이산인 문제를 정수계획법 없이 다항시간에 풀 수 있다.

6. 환원과 응용[편집]

네트워크 흐름의 진짜 위력은 “전혀 흐름처럼 안 생긴 문제”를 흐름으로 바꿔 푸는 데 있다.

• 이분 매칭. 좌우 정점 집합에 $s$, $t$를 붙이고 모든 간선 용량을 1로 두면 최대 매칭 = 최대유량. 정수성 정리가 매칭이 0/1로 나오는 것을 보장한다. 최소절단 쪽으로 읽으면 최대 매칭 = 최소 정점덮개라는 쾨니그 정리가 그대로 떨어진다. 자세히는 이분 매칭 참고.
• 프로젝트 선택 / 최대 가중 폐포. “A를 하려면 B를 먼저 해야 한다”는 선행 관계와 이익·비용이 섞인 문제는 최소절단으로 정확히 풀린다.
• 이미지 분할. 픽셀을 정점, 이웃 픽셀 쌍을 간선으로 두고 전경/배경 레이블 비용을 $s$, $t$ 간선 용량으로 넣으면, 최소절단이 곧 에너지 최소 분할이 된다. 이게 그래프 컷 기반 분할이고, 이진 레이블에 대해 서브모듈러 조건을 만족하면 전역 최적이 보장된다는 점에서 지역 최적에 만족해야 하는 여느 에너지 최소화와 격이 다르다. 컴퓨터 그래픽스의 이미지 스티칭·텍스처 합성에서도 같은 도구가 쓰인다.
• 수송·배차·스케줄링. 공급지-수요지 물류비 최소화, 승무원 배정, 기계 스케줄링의 완화 문제가 최소비용 흐름으로 떨어진다.
• 공학 해석에서의 접점. 유한요소 메시를 병렬 계산용으로 쪼개는 그래프 분할, 파이프 네트워크의 정상상태 유량 배분, 교통 배정 문제(사용자 균형은 볼록 비용 흐름 문제로 정식화된다) 등. 병렬 컴퓨팅 영역의 도메인 분할도 결국 절단 최소화 문제다.²

7. 확장과 한계[편집]

기본형에서 조금만 벗어나면 난이도가 급격히 올라간다는 것도 알아둘 만하다.

• 다품종 흐름(multicommodity flow): 서로 다른 상품이 같은 용량을 공유하면, 분수 흐름은 여전히 LP로 다항시간에 풀리지만 정수 다품종 흐름은 NP-난해다. 접속행렬의 전체 단모듈성이 깨지기 때문이다.
• 간선 용량에 하한이 있는 경우: 실행가능해 존재 여부부터 별도의 흐름 문제로 판정해야 한다.
• 오목 비용·규모의 경제: 비용이 오목하면 최적해가 극점에 몰려 조합 폭발이 일어난다. 고정비가 붙는 고정비 흐름 문제는 대표적인 정수계획법 대상이다.
• 시변 네트워크: 시간축을 복제한 시간확장 그래프로 바꾸면 정적 문제로 환원되지만, 크기가 시간 단계 수만큼 곱해진다.³

8. 관련 문서[편집]

• 선형계획법 · 정수계획법
• 조합 최적화 · 동적 계획법
• 최대유량 최소절단 정리 · 이분 매칭 · 그래프 컷
• 볼록 최적화 · 내점법
• 희소행렬 · 병렬 컴퓨팅
• 내비게이션 메시 · 군중 시뮬레이션
• 최적설계

9. Footnotes[편집]

1. 이걸 정수성 정리라고 부른다. 증명은 허무할 정도로 간단하다 — 포드-풀커슨을 정수 용량에서 돌리면 증대량이 매번 정수이므로 흐름이 정수를 벗어날 일이 없다. 정수 제약을 붙이지도 않았는데 정수해가 나오는, 최적화 세계에서 몇 안 되는 공짜 점심. ↩

2. 다만 균형 잡힌 그래프 분할(각 파티션 크기를 비슷하게)은 최소절단과 달리 NP-난해라, METIS 같은 실무 도구는 다단계 조대화 + 국소 개선 휴리스틱을 쓴다. “절단이니까 다항시간이겠지”라고 방심하면 안 되는 지점. ↩

3. 시간확장 그래프는 개념적으로 우아하지만 메모리를 정직하게 시간 단계 수만큼 먹는다. 대피 계획 문제에서 이걸 순진하게 만들었다가 RAM이 먼저 대피하는 사례가 종종 보고된다. ↩