139. Ford-Fulkerson Method

포드-풀커슨 방법(Ford-Fulkerson Method)은 일반적인 방향 그래프에서 최대 유량을 구하는 가장 간단한 방법이다. 최대 유량은 일반적으로 소스에서 간선들을 따라서 싱크로 흘려보낼 수 있는 유량의 최댓값을 의미한다. 이 방법은 다음과 같이 작동한다.

 

1. 모든 간선의 유량을 $0$으로 초기화한다.
2. 소스에서 싱크로 데이터를 보낼 수 있는 경로를 찾는다. 이 경로를 증가 경로(Augmenting Path)라고 한다.
3. 증가 경로 중 더 보낼 수 있는 데이터의 양이 가장 작은 간선을 찾는다. 이 간선에 더 보낼 수 있는 데이터의 양을 $w$라고 하자.
4. 찾은 증가 경로를 통해 $w$의 데이터를 보낸다. 증가 경로에 포함된 모든 간선의 유량이 $w$만큼 증가하고, 그 간선들에 대응하는 역방향 간선의 유량은 $w$만큼 감소한다.
5. 위 과정을 반복하다가 그래프에 증가 경로가 없는 경우 실행을 종료한다.

 

아래 그래프를 예시로 들어 살펴보자. 소스가 $\text{S}$, 싱크가 $\text{T}$이다. 각 간선에 표기된 수들은 유량/용량을 나타낸다.

먼저 증가 경로를 아무거나 하나 찾는다. $\text{S}$ - $\text{C}$ - $\text{B}$ - $\text{T}$ 경로가 선택되었다면, 더 흘려보낼 수 있는 유량이 $4$이므로 이 경로로 $4$의 유량을 흘려보낸다.

다시 증가 경로를 찾는다. $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{T}$ 경로가 선택되었다면, 더 흘려보낼 수 있는 유량이 $4$이므로 이 경로로 $4$의 유량을 흘려보낸다.

이제 이 그래프에는 증가 경로가 없는 것처럼 보인다. 하지만 역방향 간선을 고려하면 상황이 달라진다.

역방향 간선의 유량과 용량은 위와 같다. 그렇다면 이 그래프에는 $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{C}$ - $\text{D}$ - $\text{T}$라는 증가 경로가 있는 것이 된다. 이 경로로 $1$의 유량을 흘려보낸다.

이제 역방향 간선까지 고려해도 증가 경로를 찾을 수 없다. 따라서 실행을 종료한다. 소스에서 싱크로 흘려보낸 유량은 $9$이다.

 

위 과정에서 역방향 간선으로 유량을 흘려보내는 것은 정방향 간선으로 흘려보낸 유량을 상쇄하는 의미로 이해하면 된다. 어떤 경우는 역방향 간선으로 유량을 흘려보내는 상황이 발생하지 않을 수도 있다.

---

포드-풀커슨 방법은 그래프에서 최대 유량을 쉽게 구할 수 있는 방법이지만, 한 가지 큰 문제점이 있다. 증가 경로를 어떤 방식으로 찾는지가 정의되어 있지 않다는 것이다. (이 때문에 '포드-풀커슨 알고리즘'이 아니라 '포드-풀커슨 방법'으로 불리는 경우가 많고, 이 글의 제목도 '포드-풀커슨 방법'으로 했다.) 단순히 DFS로 증가 경로를 찾으면 일부 그래프에서 성능 저하가 발생해 사용하지 못하게 되기도 하는데, 이런 애매함을 해결해서 모든 그래프에 대해 충분히 빠르게 작동한다고 알려진 방법이 다음에 소개할 에드몬드-카프 알고리즘이다.