최대 유량 문제

문제에 대한 흐름 네트워크: 각 사람(ri)은 고양이(wi1) 및 개(wi2)를 입양할 의향이 있다. 그러나 각 반려동물(pi)은 사람의 일부 하위 집합에 대해서만 선호도를 가진다. 최대 수의 반려동물이 선호하는 사람 중 한 명에 의해 입양되도록 반려동물과 사람을 매칭하는 방법을 찾아라. 최적화 이론에서 **최대 유량 문제**(maximum flow problem)는 최대 가능한 유량을 얻는 네트워크 흐름을 통한 실행 가능한 흐름을 찾는 것을 포함한다. 최대 유량 문제는 순환 문제와 같은 더 복잡계 네트워크 흐름 문제의 특별한 경우로 볼 수 있다. s-t 흐름(즉, 소스 s에서 싱크 t로의 흐름)의 최대값은 최대 유량 최소 컷 정리에 명시된 바와 같이 네트워크에서 s-t 컷 (즉, s를 t에서 분리하는 컷)의 최소 용량과 같다.
# 역사
최대 유량 문제는 1954년 T. E. 해리스와 F. S. 로스에 의해 소련 철도 교통 흐름의 단순화된 모델로 처음 공식화되었다.s2cid = 10210675isbn = 978-1-4020-8116-3archive-date = 8 January 2014 1955년에 레스터 R. 포드 주니어와 D. R. 풀커슨은 최초로 알려진 알고리즘인 포드-풀커슨 알고리즘을 만들었다.doi-access = freeFord, L.R., Jr.; Fulkerson, D.R., Flows in Networks, Princeton University Press (1962). 1955년 논문에서 포드와 풀커슨은 해리스와 로스의 문제가 다음과 같이 공식화되었다고 썼다( 5페이지 참조):

> 연결된 두 도시를 여러 중간 도시를 거쳐 연결하는 철도 네트워크를 고려하고, 네트워크의 각 링크에는 그 용량을 나타내는 숫자가 할당된다. 정상 상태 조건을 가정하고, 한 주어진 도시에서 다른 도시로의 최대 흐름을 찾아라.

1962년 저서 《네트워크 흐름》에서 포드와 풀커슨은 다음과 같이 썼다:

> 1955년 봄에 T. E. 해리스가 F. S. 로스 장군(퇴역)과 함께 철도 교통 흐름의 단순화된 모델을 공식화하고 이 특정 문제를 모델이 제시하는 핵심 문제로 지목했다 [11].

여기서 [11]은 1955년 해리스와 로스의 비밀 보고서 《철도 네트워크 용량 평가 방법의 기본》을 참조한다( 5페이지 참조). 수년에 걸쳐 최대 흐름 문제에 대한 다양한 개선된 솔루션이 발견되었는데, 특히 에드먼즈와 카프, 그리고 독립적으로 디니츠의 최단 증대 경로 알고리즘, 디니츠의 블로킹 흐름 알고리즘, 밀어내기-재표시 알고리즘인 골드버그와 타잔의 알고리즘, 골드버그와 라오의 이진 블로킹 흐름 알고리즘이 있다. 셔먼s2cid = 14681906과 켈너, 리, 오레키아, 시드포드archive-date =2016-03-03publisher = MIT News의 알고리즘은 각각 대략적으로 최적의 최대 흐름을 찾지만 무방향 그래프에서만 작동한다. 2013년 제임스 B. 올린은 O(|V| |E|) 알고리즘을 설명하는 논문을 발표했다. 2022년 리 천, 라스무스 킹, 양 P. 리우, 리처드 펭, 막시밀리안 프로브스트 구텐베르크, 수샨트 사흐데바는 최대 흐름 문제의 특정 사례인 최소 비용 흐름 문제를 위해 O(|E|^{1+o(1)})으로 실행되는 거의 선형 시간 알고리즘을 발표했다.language=en 음수 가중치를 갖는 단일 원천 최단 경로 문제의 또 다른 특정 최소 비용 흐름 문제의 경우 거의 선형 시간 알고리즘도 보고되었다.eprint=2203.03456language=en 두 알고리즘 모두 2022년 컴퓨터 과학의 기초 심포지엄에서 최고 논문으로 선정되었다.website=focs2022.eecs.berkeley.edulanguage=en-gb
# 정의
소스 s와 싱크 t를 갖는 흐름 네트워크. 간선 옆 숫자는 용량이다. 먼저 몇 가지 표기법을 설정한다: * N = (V, E)는 흐름 네트워크이고, s, t \in V는 각각 N의 소스와 싱크이다. * g가 N의 간선에 대한 함수이면, (u,v) \in E에서 그 값은 g_{uv} 또는 g(u,v)로 표기된다. **정의.** 간선의 **용량**은 간선을 통해 통과할 수 있는 최대 흐름량이다. 형식적으로는 c: E \to \R^+ 함수이다. **정의.** **흐름**은 다음을 만족하는 f : E \to \R 함수이다: *용량 제약. 간선의 흐름은 용량을 초과할 수 없다. 즉, 모든 (u, v) \in E에 대해 f_{uv} \leq c_{uv}이다. * 흐름 보존. 노드로 들어오는 흐름의 합은 소스와 싱크를 제외하고 그 노드에서 나가는 흐름의 합과 같아야 한다. 즉, 다음이다: ::\forall v \in V \setminus \\{s, t\\}: \quad \sum_{u:(u, v) \in E, f_{uv}>0} f_{uv} = \sum_{u:(v, u) \in E, f_{vu}>0} f_{vu}. 비고. 흐름은 대칭 왜곡적이다: 모든 (u, v) \in E에 대해 f_{uv} = -f_{vu}이다. **정의.** **흐름의 값**은 소스에서 싱크로 통과하는 흐름의 양이다. 형식적으로 f : E \to \R^+인 흐름에 대해 다음으로 주어진다: :|f| = \sum_{v:\ (s,v) \in E} f_{sv} = \sum_{u:\ (u,t) \in E} f_{ut}. **정의.** **최대 흐름 문제**는 소스에서 싱크로 가능한 한 많은 흐름을 보내는 것이다. 즉, 최대 값을 갖는 흐름 f_\textrm{max}를 찾는 것이다. 여러 개의 최대 흐름이 존재할 수 있으며, (정수뿐만 아니라) 임의의 실수 (또는 임의의 유리수) 흐름 값이 허용되는 경우, 기본 최대 흐름의 무한한 선형 조합이 있기 때문에 정확히 하나의 최대 흐름이 있거나 무한히 많은 최대 흐름이 있다. 즉, 한 최대 흐름에서 간선 u에 x 단위의 흐름을 보내고 다른 최대 흐름에서 y > x 단위의 흐름을 보낸다면, 각 \Delta \in [0, y-x]에 대해 u에 x+\Delta 단위를 보내고 나머지 간선에 흐름을 적절히 라우팅하여 다른 최대 흐름을 얻을 수 있다. 흐름 값이 임의의 실수 또는 유리수일 수 있다면, 각 쌍 x, y에 대해 무한히 많은 \Delta 값이 존재한다.
# 알고리즘
다음 표는 최대 흐름 문제를 해결하기 위한 알고리즘의 역사적 발전을 보여준다. 나열된 많은 출판물에는 초기 연구와 결과를 비교하는 유사한 표가 포함되어 있다.
## 강한 다항 시간
강한 다항 시간 알고리즘은 입력 수에만 의존하고 이 숫자의 크기에는 의존하지 않는 다항 시간 경계를 가진다. 여기서 입력은 정점(V로 표기)과 간선(E로 표기)이다. 각 알고리즘의 복잡도는 빅 O 표기법을 사용하여 명시된다. {| class="wikitable" ! 방법 ! 연도 ! 복잡도 ! 설명 |- | 에드먼즈-카프 알고리즘volume = 19 Previously announced at the International Conference on Combinatorial Structures and their Applications, Calgary, Alberta, 1969, 0266680. | 1969 | O(VE^2) | 포드-풀커슨 알고리즘의 특수화된 버전으로, 너비 우선 탐색을 사용하여 증가 경로를 찾는다. |- | 디니츠 알고리즘year = 1970 | 1970 | O(V^2E) (임의 가중치)
O(\min\\{V^{2/3}, E^{1/2}\\}E) (단위 가중치) | 잔여 그래프의 최단 경로에 속하는 "계층" 서브그래프를 너비 우선 탐색을 사용하여 구축하고, 각 단계에서 O(VE) 시간 안에 블로킹 흐름(이 계층 그래프의 최대 흐름)을 찾는 반복 단계. 최단 경로 길이는 각 단계에서 증가하므로 최대 V-1단계가 있다. |- | 카르자노프의 알고리즘year = 1974 | 1974 | O(V^3) | 밀어내기-재표시 알고리즘의 전신으로, 각 단계에서 O(V^2) 시간 안에 디니츠 알고리즘의 블로킹 흐름을 찾기 위해 선흐름(정점에서 초과를 허용하는 흐름 함수)을 사용한다. 최초의 3차 시간 흐름 알고리즘. |- | 체르카스키의 알고리즘year = 1977 | 1977 | O\bigl(V^2 \sqrt{E}\bigr) | 디니츠의 블로킹 흐름 방식(연속적인 BFS 계층 블록 내)과 카르자노프의 방식(블록 결합)을 결합한다. 희소 그래프에 대한 최초의 3차 미만 강력 다항 시간 경계. KRT 1988까지 E의 일부 값에 대해 최고를 유지했다. |- | 말호트라, 쿠마르, 마헤슈와리url =https://eprints.utas.edu.au/160/1/iplFlow.pdf | 1978 | O(V^3) | 카르자노프 알고리즘에 대한 복잡도 개선은 아니지만 단순화. 계층 그래프의 "참조 노드"와 그 노드로 들어오거나 나가는 모든 간선을 포화시키는 흐름을 반복적으로 찾아 블로킹 흐름을 찾는데, 노드 수와 포화된 간선 수에 비례하는 시간이 걸린다. |- | 갈릴의 알고리즘year = 1980 Preliminary version, "A new algorithm for the maximal flow problem", 19th Annual Symposium on Foundations of Computer Science (FOCS), 1978. | 1978 | O(V^{5/3}E^{2/3}) | 연속 계층 블록 내에서 흐름을 찾는 방법을 대체하여 체르카스키의 알고리즘을 수정한다. |- | 갈릴, 나아마드, 1980 | 1978 | O\bigl(VE(\log V)^2\bigr) | 계층 그래프의 너비 우선 탐색 포리스트에서 트리 축소를 사용하여 블로킹 흐름 속도를 높인다. 많은 O(VE\operatorname{polylog}V) 알고리즘 중 첫 번째이며, 강력한 다항 알고리즘에 대한 여전히 최고의 다항 지수이다. |- | 링크/컷 트리를 이용한 블로킹 플로우.year = 1983 Preliminary version, 13th ACM Symposium on Theory of Computing (STOC), 1981, 10.1145/800076.802464 | 1981 | O(VE \log V) | 링크/컷 트리 데이터 구조를 도입하고 이를 사용하여 계층 네트워크에서 경로당 로그 분할 상환 시간으로 증가 경로를 찾는다. |- | 링크/컷 트리를 사용한 밀어내기-재표시 알고리즘doi-access = free Preliminary version, 18th Annual ACM Symposium on Theory of Computing (STOC), 1986, 10.1145/12130.12144 | 1986 | O\left( VE \log \frac{V^2}{E} \right) | 밀어내기-재표시 알고리즘은 선흐름(preflow)과 싱크까지의 잔여 거리를 추정하는 높이 함수를 유지한다. 이 알고리즘은 초과분을 더 낮은 높이의 정점으로 밀어내고, 더 낮은 높이로 향하는 잔여 간선이 없는 정점의 높이 함수를 증가시켜 모든 초과분이 소스로 돌아갈 때까지 이 과정을 반복한다. 링크/컷 트리는 한 번에 하나의 간선이 아니라 경로를 따라 밀어내는 것을 허용한다. |- | 체리얀과 하게럽year = 1995 Preliminary version in 30th Annual Symposium on Foundations of Computer Science (FOCS), 1989, 10.1109/SFCS.1989.63465 | 1989 | 무작위, 높은 확률로 O\bigl(VE + V^2(\log V)^2\bigr) | 한 번에 한 간선씩 추가되는 부분 그래프에 대한 밀어내기-재표시 알고리즘, 높은 초과량 푸시를 우선시하며, 무작위로 순열된 인접 리스트 사용 |- | 알론year = 1990 Cited as a 1989 manuscript by Cheriyan, Hagerup, and Mehlhorn 1990. | 1989 |O(VE+V^{8/3}\log V) | 체리얀과 하게럽 알고리즘의 탈무작위화 |- | 체리얀, 하게럽, 멜혼year = 1996 Preliminary version, "Can a maximum flow be computed in o(nm) time?", 17th International Colloquium on Automata, Languages and Programming (ICALP), 1990, 10.1007/BFb0032035 | 1990 | \displaystyle O\left(\frac{V^3}{\log V}\right) | 네 명의 러시아인 방법과 관련된 아이디어를 사용하여 체리얀과 하게럽의 알론의 탈무작위화를 사용하여 초과분을 밀어낼 높이 감소 간선 검색 속도를 높인다. |- | 킹, 라오, 타잔year = 1992 | 1992 | O(VE+V^{2+\varepsilon})
모든 \varepsilon>0에 대해 | 체리얀과 하게럽의 또 다른 탈무작위화. 더 약한 경계를 갖는 1994년 킹, 라오, 타잔의 예비 버전. |- | 필립스와 웨스트브룩year = 1998 Preliminary version, 25th ACM Symposium on Theory of Computing (STOC), 1993, 10.1145/167088.167201. | 1993 | O(VE\log_{E/V}V+V(\log V)^{2+\varepsilon})
모든 \varepsilon>0에 대해 | 유사한 아이디어를 사용하여 킹, 라오, 타잔 1992에서 개선되었다. |- | 킹, 라오, 타잔year = 1994 | 1994 | O\left( VE \log_{\frac{E}{V \log V V \right) | 유사한 아이디어를 사용하여 필립스와 웨스트브룩에서 개선되었다. |- | 올린s2cid = 207205207 | 2013 | O(VE) | 골드버그와 라오의 의사 다항 알고리즘을 동적 추이 클로저를 위한 데이터 구조를 사용하여 유지되는 압축 네트워크에 적용한다. O\bigr(VE+E^{31/16}(\log V)^2\bigr) 시간이 걸리는데, 이는 E = O(V^{16/15 - \varepsilon})일 때 O(VE)로 단순화되며, 이전 경계는 E =\Omega(V^{1+\epsilon})일 때 O(VE)로 단순화된다. |- | 올린과 공year = 2021 | 2021 | \displaystyle O\left(\frac{VE\log V}{\log\log V+\log\tfrac{E}{V\right) | Ahuja, Orlin, Tarjan의 의사 다항 알고리즘을 기반으로 한다. 킹, 라오, 타잔보다 빠르며 링크/컷 트리를 사용하지 않지만, 올린 + KRT보다 빠르지는 않다. |}
## 의사 다항 시간 및 약한 다항 시간
강한 다항 흐름 알고리즘 개발과 병행하여 입력 용량의 크기에 따라 실행 시간이 달라지는 의사 다항 시간 및 약한 다항 시간 경계가 오랫동안 존재했다. 여기서 U 값은 모든 용량을 정수 값으로 재조정했을 때 가장 큰 간선 용량을 나타낸다. (네트워크에 무리수 용량이 포함된 경우, 이 재조정은 불가능할 수 있으며 이러한 알고리즘은 정확한 솔루션을 생성하지 못하거나 근사 솔루션으로도 수렴하지 못할 수 있다.) 의사 다항 시간과 약한 다항 시간의 차이점은 의사 다항 시간 경계는 U에 대해 다항식일 수 있지만, 약한 다항 시간 경계는 \log U에 대해서만 다항식일 수 있다는 점이다. {| class="wikitable" ! 방법 ! 연도 ! 복잡도 ! 설명 |- | 포드-풀커슨 알고리즘year = 1956 | 1956 | O(EU) | 잔여 그래프를 통해 열린 경로가 있는 한, 해당 경로의 잔여 용량 중 최소값을 보낸다. |- | 이진 블로킹 흐름 알고리즘doi-access = free | 1998 | O\left( E \cdot \min\\{V^{2/3}, E^{1/2}\\} \cdot \log \frac{V^2}{E} \cdot \log U \right) | |- | 카투리아-리우-시드포드 알고리즘pages=119–130 | 2020 | E^{4/3+o(1)}U^{1/3} | \ell_p-노름 흐름을 사용하는 내점법 및 엣지 부스팅. 매드리(Madry)의 이전 알고리즘( \tilde O(E^{10/7}U^{1/7}) 런타임 달성)을 기반으로 한다.pages=593–602 |- | BLNPSSSW / BLLSSSW 알고리즘pages=919–930 eprint=2101.05719 | 2020 | \tilde O((E + V^{3/2}) \log U) | 내점법 및 확장 분해를 이용한 전기 흐름의 동적 유지. |- | 가오-리우-펭 알고리즘eprint = 2101.07233 | 2021 | \tilde O(E^{\frac 32 - \frac 1{328 \log U) | 가오, 리우, 펭의 알고리즘은 [Mądry JACM ‘16]의 내점법 기반 알고리즘의 핵심인 동적으로 증가하는 전기 흐름을 유지하는 것을 중심으로 한다. 이는 제한된 설정에서 저항 업데이트를 겪는 그래프에서 큰 전기 에너지를 가진 간선을 반환하는 데이터 구조를 설계하는 것을 포함한다. |- | 천, 킹, 리우, 펭, 구텐베르크, 사흐데바의 알고리즘eprint = 2203.00671 | 2022 |O(E^{1+o(1)} \log U) 논문에서 정확한 복잡도는 명확하게 명시되어 있지 않지만, E \exp O(\log^{7/8} E \log \log E) \log U인 것으로 보인다. | 천, 킹, 리우, 펭, 구텐베르크, 사흐데바의 알고리즘은 E^{1+o(1)}개의 근사 무방향 최소 비율 사이클 시퀀스를 통해 흐름을 구축하여 최대 흐름 및 최소 비용 흐름을 거의 선형 시간 안에 해결한다. 각 사이클은 동적 데이터 구조를 사용하여 분할 상환 E^{o(1)} 시간 안에 계산되고 처리된다. |- | 번스타인, 블릭스타드, 사라누락, 투eprint = 2406.03648 | 2024 | 간선 용량이 \\{1, \dots, U\\} 집합에서 나오는 경우 O(n^{2 + o(1)} \log U) 무작위 알고리즘 | 이 알고리즘은 가중치 변형을 도입한 밀어내기-재표시 알고리즘의 변형이다. 이 논문은 유향 비순환 그래프(DAG)에 대한 가중치 함수를 설정하고, 유향 확장자 계층을 사용하여 일반 그래프에서 이를 모방하려고 시도한다. 이는 DAG 특수 사례와 유사한 가중치 함수를 생성하는 자연스러운 정점 순서를 유도한다. 무작위화 측면(및 결과적으로 n^{o(1)} 인자)은 희소 컷 계산에 유향 확장자 계층을 적용하는 어려움에서 비롯되며, 이는 자연스러운 동적 업데이트를 허용하지 않는다. |}
# 정수 흐름 정리
정수 흐름 정리(integral flow theorem)는 다음을 명시한다. : **흐름 네트워크의 각 간선이 정수 용량을 가진다면, 정수 최대 흐름이 존재한다.** 이 주장은 흐름의 값이 정수라는 것뿐만 아니라(이는 최대 유량 최소 컷 정리에서 직접 파생된다), 모든 간선에 대한 흐름이 정수라는 것이다. 이는 많은 조합론적 응용(아래 참조)에서 중요하며, 간선을 가로지르는 흐름은 해당 간선에 해당하는 항목이 탐색되는 집합에 포함되어야 하는지 여부를 인코딩할 수 있다.
# 응용

## 다중 소스 다중 싱크 최대 흐름 문제
그림 4.1.1. 다중 소스 다중 싱크 최대 흐름 문제를 단일 소스 단일 싱크 최대 흐름 문제로 변환 하나의 소스와 하나의 싱크 대신, 소스 집합 S = \\{s_1, \ldots, s_n\\}과 싱크 집합 T = \\{t_1, \ldots, t_m\\}을 갖는 네트워크 N = (V, E)가 주어졌을 때, N을 가로지르는 최대 흐름을 찾아야 한다. 이 다중 소스 다중 싱크 문제는 S의 각 정점에 연결되는 통합 소스와 T의 각 정점에 연결되는 통합 싱크(슈퍼소스 및 슈퍼싱크라고도 함)를 각 간선에 무한 용량을 할당하여 최대 흐름 문제로 변환할 수 있다(그림 4.1.1 참조).
## 최대 이분 매칭
그림 4.3.1. 최대 이분 매칭 문제를 최대 흐름 문제로 변환 이분 그래프 G = (X \cup Y, E)가 주어졌을 때, G에서 최대 매칭을 찾아야 한다. 이는 가능한 가장 많은 수의 간선을 포함하는 매칭이다. 이 문제는 다음과 같이 네트워크 N = (X \cup Y \cup \\{s,t\\}, E')를 구성하여 최대 흐름 문제로 변환할 수 있다. # E'는 G의 간선을 X에서 Y로 향하도록 포함한다. # 각 x \in X에 대해 (s,x) \in E'이고, 각 y \in Y에 대해 (y,t) \in E'이다. # 각 e \in E'에 대해 c(e) = 1이다 (그림 4.3.1 참조). 그러면 N의 최대 흐름 값은 G의 최대 매칭 크기와 같으며, 정수 최대 흐름에서 흐름이 1인 간선을 선택하여 최대 매칭을 찾을 수 있다.
## 유향 비순환 그래프의 최소 경로 커버
유향 비순환 그래프 G = (V, E)가 주어졌을 때, V의 각 정점을 덮는 최소 수의 정점-분리 경로를 찾아야 한다. G로부터 이분 그래프 G' = (V_\textrm{out} \cup V_\textrm{in}, E')를 구성할 수 있는데, 여기서 # V_\textrm{out} = \\{ v_\textrm{out} \mid v \in V \land v \text{ has outgoing edge(s)} \\} # V_\textrm{in} = \\{ v_\textrm{in} \mid v \in V \land v \text{ has incoming edge(s)} \\} # E' = \\{(u_\textrm{out}, v_\textrm{in}) \in V_{out} \times V_{in} \mid (u, v) \in E \\}이다. 그러면 G'가 크기 m의 매칭 M을 갖는 경우에만 G가 m개의 간선과 n-m개의 경로를 포함하는 정점-분리 경로 커버 C를 갖는다는 것을 보일 수 있다. 여기서 n은 G의 정점 수이다. 따라서 이 문제는 G'에서 최대 매칭을 찾음으로써 해결할 수 있다. G'의 매칭 M을 찾고 그로부터 커버 C를 구성했다고 가정하자. 직관적으로 u_\mathrm{out}, v_\mathrm{in} 두 정점이 M에서 매칭되면, 간선 (u, v)는 C에 포함된다. 분명히 C의 간선 수는 m이다. C가 정점-분리임을 보이기 위해 다음을 고려한다. # G'의 각 정점 v_\textrm{out}은 M에서 매칭되지 않거나, 이 경우 C에서 v를 떠나는 간선이 없다. 또는 매칭될 수 있으며, 이 경우 C에서 v를 떠나는 간선은 정확히 하나다. 어느 경우든, C에서 어떤 정점 v를 떠나는 간선은 하나를 넘지 않는다. # 마찬가지로 G'의 각 정점 v_\textrm{in}에 대해서도 동일하다. 매칭되면 C에서 v로 들어오는 간선이 하나만 있고, 그렇지 않으면 v는 C에서 들어오는 간선이 없다. 따라서 어떤 정점도 C에서 두 개의 들어오는 간선이나 두 개의 나가는 간선을 가지지 않으며, 이는 C의 모든 경로가 정점-분리임을 의미한다. 커버 C의 크기가 n-m임을 보이기 위해, 빈 커버에서 시작하여 점진적으로 구축한다. 커버에 정점 u를 추가하려면, 기존 경로에 추가하거나, 해당 정점에서 시작하는 길이가 0인 새 경로를 생성할 수 있다. 전자의 경우는 (u,v) \in E이고 커버의 어떤 경로가 v에서 시작하거나, (v,u) \in E이고 어떤 경로가 v에서 끝날 때 적용 가능하다. 후자의 경우는 항상 적용 가능하다. 전자의 경우 커버의 총 간선 수는 1 증가하고 경로 수는 동일하게 유지된다. 후자의 경우 경로 수는 증가하고 간선 수는 동일하게 유지된다. 이제 모든 n개 정점을 덮은 후 커버의 경로 수와 간선 수의 합이 n이라는 것이 분명하다. 따라서 커버의 간선 수가 m이면 경로 수는 n-m이다.
## 정점 용량 포함 최대 흐름
그림 4.4.1. 정점 용량 제약이 있는 최대 흐름 문제를 노드 분할을 통해 원래의 최대 흐름 문제로 변환 N = (V, E)를 네트워크라고 하자. 간선 용량 외에 각 노드에 용량이 있다고 가정하자. 즉, c: V\to \R^+인 맵핑이 있어서, 흐름 f는 용량 제약과 흐름 보존뿐만 아니라 다음 정점 용량 제약도 만족해야 한다. : \sum_{i\in V} f_{iv} \le c(v) \qquad \forall v \in V \backslash \\{s,t\\}. 즉, 정점을 통과하는 흐름의 양은 해당 용량을 초과할 수 없다. N을 가로지르는 최대 흐름을 찾기 위해 N을 확장하여 문제를 원래의 최대 흐름 문제로 변환할 수 있다. 먼저, 각 v\in V는 v_{\text{in과 v_{\text{out으로 대체되는데, 여기서 v_{\text{in은 v로 들어가는 간선에 연결되고 v_{\text{out은 v에서 나오는 간선에 연결된다. 그리고 v_{\text{in과 v_{\text{out을 연결하는 간선에 용량 c(v)를 할당한다(그림 4.4.1 참조). 이 확장된 네트워크에서는 정점 용량 제약이 제거되므로 문제는 원래의 최대 흐름 문제로 취급될 수 있다.
## s에서 t까지의 최대 경로 수
유향 그래프 G = (V, E)와 두 정점 s, t가 주어졌을 때, s에서 t까지의 최대 경로 수를 찾아야 한다. 이 문제는 몇 가지 변형이 있다. 1\. 경로는 간선-분리여야 한다. 이 문제는 G로부터 네트워크 N = (V, E)를 구성하고, s와 t를 각각 N의 소스와 싱크로 삼으며, 각 간선에 용량을 1로 할당함으로써 최대 흐름 문제로 변환될 수 있다. 이 네트워크에서 최대 흐름이 k이면 k개의 간선-분리 경로가 존재한다. 2\. 경로는 독립적이어야 한다. 즉, ( s와 t를 제외하고) 정점-분리여야 한다. 모든 정점과 모든 간선의 용량이 1인 정점 용량을 가진 G로부터 네트워크 N = (V, E)를 구성할 수 있다. 그러면 최대 흐름의 값은 s에서 t까지의 독립 경로의 최대 수와 같다. 3\. 경로가 간선-분리 또는 정점-분리일 뿐만 아니라, 경로 길이에 대한 제약도 있다. 즉, 길이가 정확히 k이거나 최대 k인 경로만 계산한다. 이 문제의 대부분의 변형은 작은 k 값을 제외하고는 NP-완전이다.issn=1097-0037
## 클로저 문제
클로저 문제 유향 그래프의 **클로저**는 간선이 C를 떠나지 않는 정점들의 집합 C이다. **클로저 문제**는 정점 가중 유향 그래프에서 최대 가중치 또는 최소 가중치 클로저를 찾는 과제이다. 이 문제는 최대 흐름 문제로의 환원을 사용하여 다항 시간에 해결될 수 있다.
# 실제 응용

## 야구 토너먼트 탈락 문제
야구 토너먼트 탈락 문제에 대한 네트워크 흐름 구성 야구 토너먼트 탈락 문제에서는 n개의 팀이 리그에서 경쟁한다. 리그 시즌의 특정 단계에서, w_i는 팀 i의 승리 횟수이고 r_i는 팀 i가 남은 경기 수이며, r_{ij}는 팀 j와의 남은 경기 수이다. 팀은 시즌을 1위로 마칠 기회가 없으면 탈락된다. 야구 토너먼트 탈락 문제의 과제는 시즌 중 각 시점에서 어떤 팀이 탈락되는지 결정하는 것이다. 슈워츠bibcode = 1966SIAMR...8..302S는 이 문제를 최대 네트워크 흐름으로 환원하는 방법을 제안했다. 이 방법에서는 팀 k가 탈락되는지 여부를 결정하기 위해 네트워크가 생성된다. s,t \in V가 각각 소스와 싱크인 네트워크 G = (V, E)라고 하자. 두 팀 간의 경기 수를 나타내는 게임 노드_{\text{ij를 추가한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드 i, j (i < j)를 V에 연결하고, 각각을 s에서 용량 r_{ij}(두 팀 간의 경기 수)를 가진 간선으로 연결한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드 i, j를 두 팀 노드 i와 j에 연결하여 그 중 하나가 이기도록 한다. 이 간선들의 흐름 값은 제한할 필요가 없다. 마지막으로, 팀 노드 i에서 싱크 노드 t로 간선을 만들고 *w**'k* \+ *r**'k* – *w**i*의 용량을 설정하여 팀 i가 w_k + r_k보다 많이 이기는 것을 방지한다. S를 리그에 참가하는 모든 팀의 집합이라고 하고 :r(S - \\{k\\}) = \sum_{i,j \in \\{S-\\{k\\}\\} \atop i < j} r_{ij}. 이 방법에서는 팀 k가 네트워크 G에서 크기 r(S - \\{k\\})의 흐름 값이 존재하는 경우에만 탈락하지 않는다고 주장한다. 언급된 기사에서는 이 흐름 값이 s에서 t까지의 최대 흐름 값임을 증명한다.
## 항공사 스케줄링
항공 산업에서 주요 문제 중 하나는 승무원 스케줄링이다. 항공사 스케줄링 문제는 확장된 최대 네트워크 흐름의 응용으로 간주될 수 있다. 이 문제의 입력은 각 항공편이 어디서 언제 출발하고 도착하는지에 대한 정보를 포함하는 항공편 집합 F이다. 항공사 스케줄링의 한 버전에서는 최대 k개의 승무원으로 실행 가능한 스케줄을 생성하는 것이 목표이다. 이 문제를 해결하기 위해 네트워크 흐름 문제의 일반화인 경계 순환(bounded circulation)이라는 순환 문제의 변형을 사용하는데, 이는 간선 흐름에 대한 하한이라는 추가 제약이 있다. s,t \in V가 각각 소스 및 싱크 노드인 네트워크 G = (V, E)라고 하자. 각 항공편 i의 출발지 및 목적지에 대해, 항공편 i의 소스 노드 s_i와 목적지 노드 d_i를 V에 추가한다. 또한 E에 다음 간선들을 추가한다. # s와 각 s_i 사이에 용량이 [0, 1]인 간선. # 각 d_i와 t 사이에 용량이 [0, 1]인 간선. # 각 s_i와 d_i 쌍 사이에 용량이 [1, 1]인 간선. # 각 d_i와 s_j 사이에 용량이 [0, 1]인 간선 (만약 항공편 i의 목적지에서 항공편 j의 출발지까지 합리적인 시간과 비용으로 도달할 수 있다면). # s와 t 사이에 용량이 [0, ∞]인 간선. 언급된 방법에서, s와 t 사이에서 k 값의 흐름을 찾는 것은 F 항공편 집합에 대해 최대 k명의 승무원으로 실행 가능한 스케줄을 찾는 것과 같다고 주장하고 증명된다.title-link=Introduction to Algorithms 항공사 스케줄링의 또 다른 버전은 모든 항공편을 수행하는 데 필요한 최소 승무원 수를 찾는 것이다. 이 문제에 대한 해답을 찾기 위해 이분 그래프 G' = (A \cup B, E)가 생성되는데, 여기서 각 항공편은 집합 A와 집합 B에 복사본을 가진다. 동일한 비행기가 항공편 i 다음에 항공편 j를 수행할 수 있다면, *i*∈*A*는 *j*∈*B*에 연결된다. G'에서의 매칭은 F에 대한 스케줄을 유도하며, 분명히 이 그래프에서의 최대 이분 매칭은 최소 승무원 수로 항공사 스케줄을 생성한다. 이 문서의 응용 부분에서 언급된 바와 같이, 최대 이분 매칭은 최대 흐름 문제의 응용이다.
## 순환-수요 문제
물건을 생산하는 공장과 물건을 배달해야 하는 마을이 있다. 이들은 도로 네트워크로 연결되어 있으며, 각 도로에는 최대 물건 흐름을 위한 용량 c가 있다. 이 문제는 수요를 만족하는 순환이 존재하는지 찾는 것이다. 이 문제는 최대 흐름 문제로 변환될 수 있다. # 소스 노드 s를 추가하고, 각 공장 노드 f_i로 가는 간선을 추가하며, 용량은 p_i ( p_i는 공장 f_i의 생산율)이다. # 싱크 노드 t를 추가하고, 모든 마을 v_i에서 t로 가는 간선을 추가하며, 용량은 d_i ( d_i는 마을 v_i의 수요율)이다. 이 새로운 네트워크를 G = (V, E)라고 하자. 수요를 만족하는 순환은 다음 경우에만 존재한다: : {\text{최대 흐름 값(G) = \sum_{i \in v} d_i. 순환이 존재한다면, 최대 흐름 해를 통해 특정 도로에서 수요를 만족하기 위해 얼마만큼의 물건을 보내야 하는지에 대한 답을 얻을 수 있다. 일부 간선에 흐름의 하한을 추가하여 문제를 확장할 수 있다.last=Carl Kingsford
## 이미지 분할
access-date=2019-12-22 클라인베르크와 타르도스는 그들의 책에서 이미지를 분할하는 알고리즘을 제시한다.access-date=2019-12-21 그들은 이미지에서 배경과 전경을 찾는 알고리즘을 제시한다. 더 정확히 말하면, 이 알고리즘은 다음과 같이 모델링된 비트맵을 입력으로 받는다. a_i \ge 0은 픽셀 i가 전경에 속할 가능성, b_i \ge 0은 픽셀 i가 배경에 속할 가능성, p_{ij}는 두 인접 픽셀 i와 j가 하나는 전경에, 다른 하나는 배경에 놓일 경우의 페널티이다. 목표는 다음 양을 최대화하는 픽셀 집합의 분할 (A, B)을 찾는 것이다. :q(A, B) = \sum_{i \in A} a_i + \sum_{i \in B} b_i - \sum_{\begin{matrix}i, j \text{ adjacent} \\\ |A \cap \\{i, j\\}| = 1 \end{matrix p_{ij}, 실제로 A에 있는 픽셀(전경으로 간주)의 경우 a_i를 얻고, B에 있는 모든 픽셀(배경으로 간주)의 경우 b_i를 얻는다. 경계에서는 두 인접 픽셀 i와 j 사이에 p_{ij}를 잃는다. 이는 다음 양을 최소화하는 것과 동등하다. :q'(A, B) = \sum_{i \in A} b_i + \sum_{i \in B} a_i + \sum_{\begin{matrix}i, j \text{ adjacent} \\\ |A \cap \\{i, j\\}| = 1 \end{matrix p_{ij} 왜냐하면 :q(A, B) = \sum_{i \in A\cup B} a_i + \sum_{i \in A\cup B} b_i - q'(A, B). 네트워크에 표시된 최소 컷(삼각형 대 원). 이제 노드가 픽셀인 네트워크에 소스와 싱크를 추가하여 구축한다(오른쪽 그림 참조). 소스에서 픽셀 i로 가중치 a_i인 간선을 연결한다. 픽셀 i에서 싱크로 가중치 b_i인 간선을 연결한다. 픽셀 i에서 픽셀 j로 가중치 p_{ij}인 간선을 연결한다. 이제 이 네트워크에서 최소 컷(또는 동등하게 최대 흐름)을 계산하는 것이 남았다. 마지막 그림은 최소 컷을 보여준다.
# 확장
1\. **최소 비용 흐름 문제**에서는 각 간선 (u,v)가 용량 외에 **비용 계수** a_{uv}도 가진다. 간선을 통한 흐름이 f_{uv}이면, 총 비용은 a_{uv}f_{uv}이다. 주어진 크기 d의 흐름을 최소 비용으로 찾는 것이 요구된다. 대부분의 변형에서 비용 계수는 양수 또는 음수일 수 있다. 이 문제에 대한 다양한 다항 시간 알고리즘이 존재한다. 2\. 최대 흐름 문제는 **선택적 제약**으로 보강될 수 있다. 음의 선택적 제약은 특정 쌍의 간선이 동시에 0이 아닌 흐름을 가질 수 없음을 나타낸다. 양의 선택적 제약은 특정 쌍의 간선 중 적어도 하나는 0이 아닌 흐름을 가져야 함을 나타낸다. 음의 제약이 있는 경우, 문제는 단순한 네트워크에서도 강하게 NP-난해가 된다. 양의 제약이 있는 경우, 분수 흐름이 허용되면 문제는 다항식으로 풀리지만, 흐름이 정수여야 할 때는 강하게 NP-난해일 수 있다.s2cid=6598669
# 더 읽어보기
* citeseerx = 10.1.1.42.8563 * issue = 3 * pages = 109–177 위키데이터 속성 추적 분류:그래프 이론의 계산 문제