12.3 최대 유량

참조

자료

• 27. 네트워크 플로우(Network Flow) : 네이버 블로그
• 유량 관련 알고리즘 정리

영상

최대 유량

최대 유량(maximum flow) 문제에서는 두 개의 특별한 노드가 있는 방향 그래프를 다룬다. 소스(source) 는 들어오는 간선이 없는 노드이고, 싱크(sink) 는 나가는 간선이 없는 노드이다. 문제의 목적은 소스에서 싱크로 흐르는 유량을 최대한으로 만드는 것이다. 각각의 간선마다 흐를 수 있는 유량의 최대 용량이 정해져 있으며, 각각의 중간 노드로 들어오는 유량과 나가는 유량이 같아야 한다.

그림 17에 나와 있는 1번 노드가 소스이고 6번 노드가 싱크인 그래프를 예로 들어 생각해 보자. 이 그래프의 최대 유량은 그림 18에 나온 것과 같이 7이다. $v/k$ 표기는 용량이 $k$인 간선을 통해 $v$의 유량이 지난다는 뜻이다. 소스에서 나가는 유량이 $3+4$이고 싱크로 들어오는 유량이 $5+2$이기 때문에 유량이 7임을 알 수 있다. 싱크로 들어가는 간선의 용량 합이 7이기 때문에 이 값이 최댓값임을 알 수 있다.

최대 유량 문제는 다른 유형의 그래프 문제인 최소 컷(minimum cut) 문제로 연결될 수 있음이 알려져 있다. 최소 컷 문제는 간선 중 일부를 제거하여 소스에서 싱크로 가는 경로를 없애되, 그러면서 제거한 간선의 가중치 합을 최소로 만드는 문제이다.

예를 들어 그림 17의 그래프를 다시 생각해 보자. 이 그래프의 최소 컷은 7인데, 그림 19에 나온 것과 같이 간선 $2\to 3$과 간선 $4\to 5$를 제거하면 조건을 만족하기 때문이다. 간선을 제거하고 나면 소스에서 싱크로 가는 경로가 없어진다. 컷의 크기는 $6+1=7$이고, 가중치의 합이 7보다 작은 컷이 없기 때문에 이 값은 최소가 된다.

• 그림 17. 소스가 1번 노드이고 싱크가 6번 노드인 그래프
  • 
• 그림 18. 그래프의 최대 유량은 7이다.
  • 
• 그림 19. 그래프의 최소 컷은 7이다.
  • 

예제 그래프에 대한 최대 유량과 최소 컷이 같은 것은 우연이 아니다. 두 값이 항상 일치한다고 알려져 있으며, 두 가지 개념은 동전의 양면과 같다. 이제 그래프의 최대 유량과 최소 컷을 찾는 포드-풀커슨 알고리즘을 살펴볼 것이다. 이 알고리즘을 이해하면 왜 두 값이 같은지 알게 될 것이다.

• 12.3.1 포드-풀커슨 알고리즘

경로 찾기

앞에서 살펴본 포드-풀커슨 알고리즘에서 유량을 증가시키는 경로를 선택하는 기준이 따로 정해져 있지는 않았다. 어떤 방식으로 경로를 고르더라도, 시간의 차이는 있지만 알고리즘은 항상 종료하고 최대 유량을 올바르게 찾는다. 하지만 알고리즘의 효율성은 경로를 어떻게 선택하는지에 크게 영향을 받는다. 경로를 찾는 간단한 방법 하나는 깊이 우선 탐색을 이용하는 것이다. 이 방법은 대부분의 경우에 잘 동작하지만, 최악의 경우에는 경로를 선택할 때마다 유량이 1씩 증가하여 알고리즘이 매우 느려질 수 있다. 다행히도 다음에 소개할 여러 기법 중 하나를 사용하면 이러한 상황을 방지할 수 있다.

• 12.3.2 에드몬드-카프 알고리즘
• 12.3.3 디닉 알고리즘

최소 컷

포드-풀커슨 알고리즘을 이용하여 최대 유량을 찾았다면, 그 결과에서 최소 컷을 바로 찾을 수 있다. 알고리즘을 실행한 이후의 그래프에 대해, $A$를 소스에서 가중치가 양수인 간선을 이용하여 갈 수 있는 노드의 집합(잔여 그래프, residual graph)으로 정의하자. 최소 컷은 원래 그래프에서 $A$에 속한 노드에서 $A$에 속하지 않은 노드로 가는 간선으로 구성되며, 그러한 간선의 용량은 최대 유량을 구할 때 모두 사용되었다. 그림 22를 예로 들면 $A$는 1, 2, 4번 노드로 구성되고, 최소 컷에 속하는 간선은 $2\to 3$, $4\to 5$로 가중치의 합은 $6+1=7$이다.

• 그림 22. 1, 2, 4번 노드가 집합 $A$에 속한다.
  • 

알고리즘을 수행하여 찾은 유량이 최대이고 컷이 최소인 이유는 무엇일까? 그 이유는 그래프의 유량이 컷보다 클 수 없기 때문이다. 따라서 유량과 컷의 값이 같다면, 각각은 최대 유량과 최소 컷이 된다.

위의 성질이 왜 성립하는지를 알아보기 위해 다음과 같은 컷을 생각해 보자. 그래프의 노드를 두 집합으로 나누는데, 소스는 $A$에, 싱크는 $B$에 속하고, 두 집합의 노드를 잇는 간선은 컷이 된다(그림 23). 컷의 크기는 $A$에서 $B$로 가는 간선의 가중치 합이다. 이 값은 그래프의 유량의 상한이 되는데, 이는 흐름의 방향이 $A$에서 $B$로 가는 방향이기 때문이다. 즉, 최대 유량의 크기는 그래프의 어떤 컷의 크기보다도 항상 작거나 같다. 한편, 포드-풀커슨 알고리즘의 결과로 얻은 최대 유량은 그래프의 컷의 크기와 일치한다. 그러므로 이 결과는 최대 유량이면서 최소 컷이 된다.

• 그림 23. $A$와 $B$ 사이의 간선
  •