최대 유량 문제

alt=Flow network for the problem: Each human (ri) is willing to adopt a cat (wi1) and/or a dog (wi2). However each pet (pi) has a preference for only a subset of the humans. Find any matching of pets to humans such that the maximum number of pets are adopted by one of its preferred humans.|thumb|252x252px|문제에 대한 흐름 네트워크: 각 사람(ri)은 고양이(wi1) 및 개(wi2)를 입양할 의향이 있다. 그러나 각 반려동물(pi)은 사람의 일부 하위 집합에 대해서만 선호도를 가진다. 최대 수의 반려동물이 선호하는 사람 중 한 명에 의해 입양되도록 반려동물과 사람을 매칭하는 방법을 찾아라.
최적화 이론에서 최대 유량 문제(maximum flow problem)는 최대 가능한 유량을 얻는 네트워크 흐름을 통한 실행 가능한 흐름을 찾는 것을 포함한다.

최대 유량 문제는 순환 문제와 같은 더 복잡계 네트워크 흐름 문제의 특별한 경우로 볼 수 있다. s-t 흐름(즉, 소스 s에서 싱크 t로의 흐름)의 최대값은 최대 유량 최소 컷 정리에 명시된 바와 같이 네트워크에서 s-t 컷 (즉, s를 t에서 분리하는 컷)의 최소 용량과 같다.

역사
최대 유량 문제는 1954년 T. E. 해리스와 F. S. 로스에 의해 소련 철도 교통 흐름의 단순화된 모델로 처음 공식화되었다.
1955년에 레스터 R. 포드 주니어와 D. R. 풀커슨은 최초로 알려진 알고리즘인 포드-풀커슨 알고리즘을 만들었다. 1955년 논문에서 포드와 풀커슨은 해리스와 로스의 문제가 다음과 같이 공식화되었다고 썼다( 5페이지 참조):연결된 두 도시를 여러 중간 도시를 거쳐 연결하는 철도 네트워크를 고려하고, 네트워크의 각 링크에는 그 용량을 나타내는 숫자가 할당된다. 정상 상태 조건을 가정하고, 한 주어진 도시에서 다른 도시로의 최대 흐름을 찾아라.1962년 저서 《네트워크 흐름》에서 포드와 풀커슨은 다음과 같이 썼다:1955년 봄에 T. E. 해리스가 F. S. 로스 장군(퇴역)과 함께 철도 교통 흐름의 단순화된 모델을 공식화하고 이 특정 문제를 모델이 제시하는 핵심 문제로 지목했다 [11].여기서 [11]은 1955년 해리스와 로스의 비밀 보고서 《철도 네트워크 용량 평가 방법의 기본》을 참조한다( 5페이지 참조).

수년에 걸쳐 최대 흐름 문제에 대한 다양한 개선된 솔루션이 발견되었는데, 특히 에드먼즈와 카프, 그리고 독립적으로 디니츠의 최단 증대 경로 알고리즘, 디니츠의 블로킹 흐름 알고리즘, 밀어내기-재표시 알고리즘인 골드버그와 타잔의 알고리즘, 골드버그와 라오의 이진 블로킹 흐름 알고리즘이 있다. 셔먼과 켈너, 리, 오레키아, 시드포드의 알고리즘은 각각 대략적으로 최적의 최대 흐름을 찾지만 무방향 그래프에서만 작동한다.

2013년 제임스 B. 올린은 알고리즘을 설명하는 논문을 발표했다.

2022년 리 천, 라스무스 킹, 양 P. 리우, 리처드 펭, 막시밀리안 프로브스트 구텐베르크, 수샨트 사흐데바는 최대 흐름 문제의 특정 사례인 최소 비용 흐름 문제를 위해 으로 실행되는 거의 선형 시간 알고리즘을 발표했다. 음수 가중치를 갖는 단일 원천 최단 경로 문제의 또 다른 특정 최소 비용 흐름 문제의 경우 거의 선형 시간 알고리즘도 보고되었다. 두 알고리즘 모두 2022년 컴퓨터 과학의 기초 심포지엄에서 최고 논문으로 선정되었다.

정의
thumb|upright=0.8|소스 s와 싱크 t를 갖는 흐름 네트워크. 간선 옆 숫자는 용량이다.

먼저 몇 가지 표기법을 설정한다:
 는 흐름 네트워크이고, 는 각각 의 소스와 싱크이다.
 가 의 간선에 대한 함수이면, 에서 그 값은 또는 로 표기된다.

정의. 간선의 용량은 간선을 통해 통과할 수 있는 최대 흐름량이다. 형식적으로는 함수이다.

정의. 흐름은 다음을 만족하는 함수이다:
용량 제약. 간선의 흐름은 용량을 초과할 수 없다. 즉, 모든 에 대해 이다.
 흐름 보존. 노드로 들어오는 흐름의 합은 소스와 싱크를 제외하고 그 노드에서 나가는 흐름의 합과 같아야 한다. 즉, 다음이다:

비고. 흐름은 대칭 왜곡적이다: 모든 에 대해 이다.

정의. 흐름의 값은 소스에서 싱크로 통과하는 흐름의 양이다. 형식적으로 인 흐름에 대해 다음으로 주어진다:

정의. 최대 흐름 문제는 소스에서 싱크로 가능한 한 많은 흐름을 보내는 것이다. 즉, 최대 값을 갖는 흐름 를 찾는 것이다.

여러 개의 최대 흐름이 존재할 수 있으며, (정수뿐만 아니라) 임의의 실수 (또는 임의의 유리수) 흐름 값이 허용되는 경우, 기본 최대 흐름의 무한한 선형 조합이 있기 때문에 정확히 하나의 최대 흐름이 있거나 무한히 많은 최대 흐름이 있다. 즉, 한 최대 흐름에서 간선 에 단위의 흐름을 보내고 다른 최대 흐름에서 단위의 흐름을 보낸다면, 각 에 대해 에 단위를 보내고 나머지 간선에 흐름을 적절히 라우팅하여 다른 최대 흐름을 얻을 수 있다. 흐름 값이 임의의 실수 또는 유리수일 수 있다면, 각 쌍 에 대해 무한히 많은 값이 존재한다.

알고리즘
다음 표는 최대 흐름 문제를 해결하기 위한 알고리즘의 역사적 발전을 보여준다. 나열된 많은 출판물에는 초기 연구와 결과를 비교하는 유사한 표가 포함되어 있다.

강한 다항 시간
강한 다항 시간 알고리즘은 입력 수에만 의존하고 이 숫자의 크기에는 의존하지 않는 다항 시간 경계를 가진다. 여기서 입력은 정점(로 표기)과 간선(로 표기)이다. 각 알고리즘의 복잡도는 빅 O 표기법을 사용하여 명시된다.

의사 다항 시간 및 약한 다항 시간
강한 다항 흐름 알고리즘 개발과 병행하여 입력 용량의 크기에 따라 실행 시간이 달라지는 의사 다항 시간 및 약한 다항 시간 경계가 오랫동안 존재했다. 여기서 값은 모든 용량을 정수 값으로 재조정했을 때 가장 큰 간선 용량을 나타낸다. (네트워크에 무리수 용량이 포함된 경우, 이 재조정은 불가능할 수 있으며 이러한 알고리즘은 정확한 솔루션을 생성하지 못하거나 근사 솔루션으로도 수렴하지 못할 수 있다.) 의사 다항 시간과 약한 다항 시간의 차이점은 의사 다항 시간 경계는 에 대해 다항식일 수 있지만, 약한 다항 시간 경계는 에 대해서만 다항식일 수 있다는 점이다.

정수 흐름 정리
정수 흐름 정리(integral flow theorem)는 다음을 명시한다.
 흐름 네트워크의 각 간선이 정수 용량을 가진다면, 정수 최대 흐름이 존재한다.

이 주장은 흐름의 값이 정수라는 것뿐만 아니라(이는 최대 유량 최소 컷 정리에서 직접 파생된다), 모든 간선에 대한 흐름이 정수라는 것이다. 이는 많은 조합론적 응용(아래 참조)에서 중요하며, 간선을 가로지르는 흐름은 해당 간선에 해당하는 항목이 탐색되는 집합에 포함되어야 하는지 여부를 인코딩할 수 있다.

응용

다중 소스 다중 싱크 최대 흐름 문제
thumb|right|그림 4.1.1. 다중 소스 다중 싱크 최대 흐름 문제를 단일 소스 단일 싱크 최대 흐름 문제로 변환
하나의 소스와 하나의 싱크 대신, 소스 집합 과 싱크 집합 을 갖는 네트워크 가 주어졌을 때, 을 가로지르는 최대 흐름을 찾아야 한다. 이 다중 소스 다중 싱크 문제는 의 각 정점에 연결되는 통합 소스와 의 각 정점에 연결되는 통합 싱크(슈퍼소스 및 슈퍼싱크라고도 함)를 각 간선에 무한 용량을 할당하여 최대 흐름 문제로 변환할 수 있다(그림 4.1.1 참조).

최대 이분 매칭
thumb|right|그림 4.3.1. 최대 이분 매칭 문제를 최대 흐름 문제로 변환
이분 그래프 가 주어졌을 때, 에서 최대 매칭을 찾아야 한다. 이는 가능한 가장 많은 수의 간선을 포함하는 매칭이다. 이 문제는 다음과 같이 네트워크 를 구성하여 최대 흐름 문제로 변환할 수 있다.
 는 의 간선을 에서 로 향하도록 포함한다.
 각 에 대해 이고, 각 에 대해 이다.
 각 에 대해 이다 (그림 4.3.1 참조).

그러면 의 최대 흐름 값은 의 최대 매칭 크기와 같으며, 정수 최대 흐름에서 흐름이 인 간선을 선택하여 최대 매칭을 찾을 수 있다.

유향 비순환 그래프의 최소 경로 커버
유향 비순환 그래프 가 주어졌을 때, 의 각 정점을 덮는 최소 수의 정점-분리 경로를 찾아야 한다. 로부터 이분 그래프 를 구성할 수 있는데, 여기서
 
 
 이다.

그러면 가 크기 의 매칭 을 갖는 경우에만 가 개의 간선과 개의 경로를 포함하는 정점-분리 경로 커버 를 갖는다는 것을 보일 수 있다. 여기서 은 의 정점 수이다. 따라서 이 문제는 에서 최대 매칭을 찾음으로써 해결할 수 있다.

의 매칭 을 찾고 그로부터 커버 를 구성했다고 가정하자. 직관적으로 두 정점이 에서 매칭되면, 간선 는 에 포함된다. 분명히 의 간선 수는 이다. 가 정점-분리임을 보이기 위해 다음을 고려한다.
 의 각 정점 은 에서 매칭되지 않거나, 이 경우 에서 를 떠나는 간선이 없다. 또는 매칭될 수 있으며, 이 경우 에서 를 떠나는 간선은 정확히 하나다. 어느 경우든, 에서 어떤 정점 를 떠나는 간선은 하나를 넘지 않는다.
 마찬가지로 의 각 정점 에 대해서도 동일하다. 매칭되면 에서 로 들어오는 간선이 하나만 있고, 그렇지 않으면 는 에서 들어오는 간선이 없다.
따라서 어떤 정점도 에서 두 개의 들어오는 간선이나 두 개의 나가는 간선을 가지지 않으며, 이는 의 모든 경로가 정점-분리임을 의미한다.

커버 의 크기가 임을 보이기 위해, 빈 커버에서 시작하여 점진적으로 구축한다. 커버에 정점 를 추가하려면, 기존 경로에 추가하거나, 해당 정점에서 시작하는 길이가 0인 새 경로를 생성할 수 있다. 전자의 경우는 이고 커버의 어떤 경로가 에서 시작하거나, 이고 어떤 경로가 에서 끝날 때 적용 가능하다. 후자의 경우는 항상 적용 가능하다. 전자의 경우 커버의 총 간선 수는 1 증가하고 경로 수는 동일하게 유지된다. 후자의 경우 경로 수는 증가하고 간선 수는 동일하게 유지된다. 이제 모든 개 정점을 덮은 후 커버의 경로 수와 간선 수의 합이 이라는 것이 분명하다. 따라서 커버의 간선 수가 이면 경로 수는 이다.

정점 용량 포함 최대 흐름
thumb|right|그림 4.4.1. 정점 용량 제약이 있는 최대 흐름 문제를 노드 분할을 통해 원래의 최대 흐름 문제로 변환

를 네트워크라고 하자. 간선 용량 외에 각 노드에 용량이 있다고 가정하자. 즉, 인 맵핑이 있어서, 흐름 는 용량 제약과 흐름 보존뿐만 아니라 다음 정점 용량 제약도 만족해야 한다.

즉, 정점을 통과하는 흐름의 양은 해당 용량을 초과할 수 없다. 을 가로지르는 최대 흐름을 찾기 위해 을 확장하여 문제를 원래의 최대 흐름 문제로 변환할 수 있다. 먼저, 각 는 과 으로 대체되는데, 여기서 은 로 들어가는 간선에 연결되고 은 에서 나오는 간선에 연결된다. 그리고 과 을 연결하는 간선에 용량 를 할당한다(그림 4.4.1 참조). 이 확장된 네트워크에서는 정점 용량 제약이 제거되므로 문제는 원래의 최대 흐름 문제로 취급될 수 있다.

s에서 t까지의 최대 경로 수
유향 그래프 와 두 정점 , 가 주어졌을 때, 에서 까지의 최대 경로 수를 찾아야 한다. 이 문제는 몇 가지 변형이 있다.

1. 경로는 간선-분리여야 한다. 이 문제는 로부터 네트워크 를 구성하고, 와 를 각각 의 소스와 싱크로 삼으며, 각 간선에 용량을 로 할당함으로써 최대 흐름 문제로 변환될 수 있다. 이 네트워크에서 최대 흐름이 이면 개의 간선-분리 경로가 존재한다.

2. 경로는 독립적이어야 한다. 즉, ( 와 를 제외하고) 정점-분리여야 한다. 모든 정점과 모든 간선의 용량이 인 정점 용량을 가진 로부터 네트워크 를 구성할 수 있다. 그러면 최대 흐름의 값은 에서 까지의 독립 경로의 최대 수와 같다.

3. 경로가 간선-분리 또는 정점-분리일 뿐만 아니라, 경로 길이에 대한 제약도 있다. 즉, 길이가 정확히 이거나 최대 인 경로만 계산한다. 이 문제의 대부분의 변형은 작은 값을 제외하고는 NP-완전이다.

 클로저 문제 

유향 그래프의 클로저는 간선이 C를 떠나지 않는 정점들의 집합 C이다. 클로저 문제는 정점 가중 유향 그래프에서 최대 가중치 또는 최소 가중치 클로저를 찾는 과제이다. 이 문제는 최대 흐름 문제로의 환원을 사용하여 다항 시간에 해결될 수 있다.

실제 응용

야구 토너먼트 탈락 문제
thumb|야구 토너먼트 탈락 문제에 대한 네트워크 흐름 구성
야구 토너먼트 탈락 문제에서는 n개의 팀이 리그에서 경쟁한다. 리그 시즌의 특정 단계에서, 는 팀 i의 승리 횟수이고 는 팀 i가 남은 경기 수이며, 는 팀 j와의 남은 경기 수이다. 팀은 시즌을 1위로 마칠 기회가 없으면 탈락된다. 야구 토너먼트 탈락 문제의 과제는 시즌 중 각 시점에서 어떤 팀이 탈락되는지 결정하는 것이다. 슈워츠는 이 문제를 최대 네트워크 흐름으로 환원하는 방법을 제안했다. 이 방법에서는 팀 k가 탈락되는지 여부를 결정하기 위해 네트워크가 생성된다.

가 각각 소스와 싱크인 네트워크 라고 하자. 두 팀 간의 경기 수를 나타내는 게임 노드를 추가한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드 (i < j)를 에 연결하고, 각각을 에서 용량 (두 팀 간의 경기 수)를 가진 간선으로 연결한다. 또한 각 팀에 대한 팀 노드를 추가하고, 각 게임 노드 를 두 팀 노드 i와 j에 연결하여 그 중 하나가 이기도록 한다. 이 간선들의 흐름 값은 제한할 필요가 없다. 마지막으로, 팀 노드 i에서 싱크 노드 t로 간선을 만들고 의 용량을 설정하여 팀 i가 보다 많이 이기는 것을 방지한다.
를 리그에 참가하는 모든 팀의 집합이라고 하고
.
이 방법에서는 팀 k가 네트워크 G에서 크기 의 흐름 값이 존재하는 경우에만 탈락하지 않는다고 주장한다. 언급된 기사에서는 이 흐름 값이 에서 까지의 최대 흐름 값임을 증명한다.

항공사 스케줄링
항공 산업에서 주요 문제 중 하나는 승무원 스케줄링이다. 항공사 스케줄링 문제는 확장된 최대 네트워크 흐름의 응용으로 간주될 수 있다. 이 문제의 입력은 각 항공편이 어디서 언제 출발하고 도착하는지에 대한 정보를 포함하는 항공편 집합 F이다. 항공사 스케줄링의 한 버전에서는 최대 k개의 승무원으로 실행 가능한 스케줄을 생성하는 것이 목표이다.

이 문제를 해결하기 위해 네트워크 흐름 문제의 일반화인 경계 순환(bounded circulation)이라는 순환 문제의 변형을 사용하는데, 이는 간선 흐름에 대한 하한이라는 추가 제약이 있다.

가 각각 소스 및 싱크 노드인 네트워크 라고 하자. 각 항공편 i의 출발지 및 목적지에 대해, 항공편 i의 소스 노드 와 목적지 노드 를 에 추가한다. 또한 에 다음 간선들을 추가한다.
 와 각 사이에 용량이 [0, 1]인 간선.
 각 와 사이에 용량이 [0, 1]인 간선.
 각 와 쌍 사이에 용량이 [1, 1]인 간선.
 각 와 사이에 용량이 [0, 1]인 간선 (만약 항공편 i의 목적지에서 항공편 j의 출발지까지 합리적인 시간과 비용으로 도달할 수 있다면).
 와 사이에 용량이 [0, ∞]인 간선.

언급된 방법에서, 와 사이에서 값의 흐름을 찾는 것은 F 항공편 집합에 대해 최대 명의 승무원으로 실행 가능한 스케줄을 찾는 것과 같다고 주장하고 증명된다.

항공사 스케줄링의 또 다른 버전은 모든 항공편을 수행하는 데 필요한 최소 승무원 수를 찾는 것이다. 이 문제에 대한 해답을 찾기 위해 이분 그래프 가 생성되는데, 여기서 각 항공편은 집합 A와 집합 B에 복사본을 가진다. 동일한 비행기가 항공편 i 다음에 항공편 j를 수행할 수 있다면, 는 에 연결된다. 에서의 매칭은 F에 대한 스케줄을 유도하며, 분명히 이 그래프에서의 최대 이분 매칭은 최소 승무원 수로 항공사 스케줄을 생성한다. 이 문서의 응용 부분에서 언급된 바와 같이, 최대 이분 매칭은 최대 흐름 문제의 응용이다.

순환-수요 문제
물건을 생산하는 공장과 물건을 배달해야 하는 마을이 있다. 이들은 도로 네트워크로 연결되어 있으며, 각 도로에는 최대 물건 흐름을 위한 용량 가 있다. 이 문제는 수요를 만족하는 순환이 존재하는지 찾는 것이다.
이 문제는 최대 흐름 문제로 변환될 수 있다.
 소스 노드 를 추가하고, 각 공장 노드 로 가는 간선을 추가하며, 용량은 ( 는 공장 의 생산율)이다.
 싱크 노드 를 추가하고, 모든 마을 에서 로 가는 간선을 추가하며, 용량은 ( 는 마을 의 수요율)이다.
이 새로운 네트워크를 라고 하자. 수요를 만족하는 순환은 다음 경우에만 존재한다:
 .
순환이 존재한다면, 최대 흐름 해를 통해 특정 도로에서 수요를 만족하기 위해 얼마만큼의 물건을 보내야 하는지에 대한 답을 얻을 수 있다.

일부 간선에 흐름의 하한을 추가하여 문제를 확장할 수 있다.

 이미지 분할 
thumb|크기 8x8의 원본 이미지.|alt=|left|110x110px
thumb|비트맵에서 구축된 네트워크. 소스는 왼쪽에, 싱크는 오른쪽에 있다. 간선이 어두울수록 용량이 크다. ai는 픽셀이 녹색일 때 높고, bi는 픽셀이 녹색이 아닐 때 높다. 페널티 pij는 모두 같다.
클라인베르크와 타르도스는 그들의 책에서 이미지를 분할하는 알고리즘을 제시한다. 그들은 이미지에서 배경과 전경을 찾는 알고리즘을 제시한다. 더 정확히 말하면, 이 알고리즘은 다음과 같이 모델링된 비트맵을 입력으로 받는다. 은 픽셀 i가 전경에 속할 가능성, 은 픽셀 i가 배경에 속할 가능성, 는 두 인접 픽셀 i와 j가 하나는 전경에, 다른 하나는 배경에 놓일 경우의 페널티이다. 목표는 다음 양을 최대화하는 픽셀 집합의 분할 (A, B)을 찾는 것이다.

,

실제로 A에 있는 픽셀(전경으로 간주)의 경우 를 얻고, B에 있는 모든 픽셀(배경으로 간주)의 경우 를 얻는다. 경계에서는 두 인접 픽셀 i와 j 사이에 를 잃는다. 이는 다음 양을 최소화하는 것과 동등하다.

왜냐하면

thumb|네트워크에 표시된 최소 컷(삼각형 대 원).

이제 노드가 픽셀인 네트워크에 소스와 싱크를 추가하여 구축한다(오른쪽 그림 참조). 소스에서 픽셀 i로 가중치 인 간선을 연결한다. 픽셀 i에서 싱크로 가중치 인 간선을 연결한다. 픽셀 i에서 픽셀 j로 가중치 인 간선을 연결한다. 이제 이 네트워크에서 최소 컷(또는 동등하게 최대 흐름)을 계산하는 것이 남았다. 마지막 그림은 최소 컷을 보여준다.

확장
1. 최소 비용 흐름 문제에서는 각 간선 (u,v)가 용량 외에 비용 계수 도 가진다. 간선을 통한 흐름이 이면, 총 비용은 이다. 주어진 크기 의 흐름을 최소 비용으로 찾는 것이 요구된다. 대부분의 변형에서 비용 계수는 양수 또는 음수일 수 있다. 이 문제에 대한 다양한 다항 시간 알고리즘이 존재한다.

2. 최대 흐름 문제는 선택적 제약으로 보강될 수 있다. 음의 선택적 제약은 특정 쌍의 간선이 동시에 0이 아닌 흐름을 가질 수 없음을 나타낸다. 양의 선택적 제약은 특정 쌍의 간선 중 적어도 하나는 0이 아닌 흐름을 가져야 함을 나타낸다. 음의 제약이 있는 경우, 문제는 단순한 네트워크에서도 강하게 NP-난해가 된다. 양의 제약이 있는 경우, 분수 흐름이 허용되면 문제는 다항식으로 풀리지만, 흐름이 정수여야 할 때는 강하게 NP-난해일 수 있다.

 각주 

 더 읽어보기 
 
 
 

분류:그래프 이론의 계산 문제