12 min to read
유량 그래프 ①:포드-풀커슨 알고리즘
유량그래프의 정의와 최대유량 문제를 해결하는 포드-풀커슨 알고리즘, 그리고 그의 정당성까지 알아봅시다.
개요
그동안 많은 일들이 있었다는 핑계로 블로그에 먼지가 쌓이게 두고 있었습니다만, 다시 글을 써보려고 합니다. 잠수를 타고 있을 동안에, 알고리즘 공부도 하였고, 이제 그 공부한 내용을 가지고 또 글을 써보려고 합니다.
유량 그래프란?
유량 그래프는, 말 그대로 유량이 흐르는 그래프 입니다. 그래프가 현실의 많은 문제를 표현할 수 있듯, 유량 그래프도 현실의 많은 문제를 시뮬레이팅 하는데 사용됩니다.
논밭에 물을 공급하는 급수시설을 생각해 봅시다. 주변 강이나 호수에서 물을 끌어오는 수원지가 있고, 당연히 파이프의 끝에는 우리가 물을 대기를 원하는 논밭 등이 있겠습니다. 또 파이프의 둘레, 길이 그리고 재질 때문에 무한한 양의 물을 흘릴수는 없지요. 파이프의 유량 제한이 각각 다르다면, 최대로 흘릴 수 있는 유량의 한계는 너무나 당연하게도, 제한이 가장 빠듯한 파이프에 영향을 크게 받을 것입니다. 도로망에 관해서도 비슷한 생각을 할 수 있지요. 도로를 넓게 닦아서, 많은 차가 지나갈 수 있는 고속도로도 있지만, 차가 겨우 지나갈법한 너무나 좁은 도로도 있지요.
유량그래프는 이러한 급수시설이나 도로망과 닮은점이 참 많은 그래프 형태입니다. 명확하게 유량 그래프를 정의하겠습니다. 유량 그래프는 기존의 그래프의 간선에 용량(capacity) 이라는 속성을 추가한 방향 그래프라고 할 수 있습니다. 유량 그래프의 간선은 유량을 흘러보내는 파이프와 같은 역할을 합니다.
정점 \(u\)에서 \(v\)로 가는 간선의 용량을 \(c(u,v)\)라고 하고, 실제 흐르는 유량을 \(f(u,v)\)라고 하고, \(V\)를 전체 정점의 집합이라고 할 때, 유량 그래프가 만족해야 할 속성은 세가지가 있습니다.
- 용량 제한 속성 : \(f(u,v) \le c(u,v)\) : 정말로 자명한 속성입니다. 그래프의 한 간선에서 흐르는 유량은 용량을 초과할수 없지요. 이게 용량의 정의니까요
- 유량의 대칭성 : \(f(u,v) = -f(v,u)\) : 이건 좀 자명하지는 않습니다. \(u\)에서 \(v\)로 양수의 유량을 보낸다는 것은, \(v\)에서 \(u\)로 음수의 유량을 보내는 것으로 간주합니다. 있지도 않을 수도 있는 역방향 간선을 왜 다루게 되는지는 나중에 서술하겠습니다.
- 유량의 보존 : \(\sum_{v\in V}f(u,v)=0\) : 이 속성은 각 정점에 들어오는 유량과 나가는 유량의 양이 같아야 한다는 뜻입니다. 위 식만 가지고는 어떻게 이게 그 뜻이 되는지 한번에 와닫지 않을 수 있습니다. 하지만, 위의 2번에서 다룬 유량의 대칭성에서, 정점에 들어오는 양은 음수로 표현을 하니, (예를 들어 \((a,u)\)를 통해 유량이 \(u\)로 온다면, \(f(u,a)\)는 음수의 유량으로 표현됩니다) 위의 식은 \(v\)에서 들어오고 나가는 유량의 모든 합을 표현하므로, 0이 되어야 한다는 사실을 알 수 있습니다. 정점에 유량이 저장되는 경우는 유량 그래프에서 다루지 않습니다.
유량 그래프에는 특수한 정점 두개가 존재합니다. 바로 소스(source)와 싱크(sink)라는 것인데요, 위에서 급수시설에 빗대서 설명했을때의 수원지와 목적지에 각각 해당합니다. 소스는 유량이 시작되는 정점이고, 싱크는 유량이 끝나는 정점이기 때문에, 이 두가지 정점에 한해서 유량의 보존 성질이 성립하지가 않습니다.
유량 그래프에서 소스에서 싱크로 최대로 흐를 수 있는 유량을 구하는 문제를 네트워크 유량 문제 라고 합니다. 이 시리즈에서는 네트워크 유량 문제를 푸는 알고리즘과, 다양한 문제를 네트워크 유량 문제로 변환하는 방법을 알아보고자 합니다.
포드-풀커슨 알고리즘
네트워크 유량 문제를 푸는 가장 간단한 알고리즘 입니다. 이보다 더 빠른 알고리즘은 여럿 알려져 있지만, 구현이 더 복잡합니다. PS를 할때 왠만한 문제 난이도에서는 포드-풀커슨으로 힘든 문제는 그리 나오지 않습니다.(라고 종만북에서 그랬습니다.) 포드 풀커슨 알고리즘의 동작원리를 알아보도록 하겠습니다.
알고리즘의 동작원리
맨 처음의 유량 그래프에서의 모든 간선에서의 유량을 0으로 초기화 합니다. 소스에서 싱크로 유량을 보낼 수 있는 경로를 아무튼 찾아내서(이를 증가 경로(augmenting path) 라고 합니다), 그 경로에서 보낼 수 있는 최대의 유량을 흘려 보냅니다. 이를 더이상 증가 경로를 찾을 수 없을때까지 반복합니다.
경로를 따라서 유량을 보낼려면 너무나 당연한 말이지만, 경로에 있는 간선에 남은 유량이 있어야 겠지요. 남은 유량을 구하는 방법은 상식적으로 여러분이 생각하는 그 방법 그대로 입니다.
\(u\)에서 \(v\)로 보낼 수 있는 잔여 용량을 \(c(u,v)\) 라고 합시다. \(c(u,v)\)는 아래와 같이 정의됩니다.
\[r(u,v) = c(u,v)-f(u,v)\]너무나도 상식적입니다. 하지만 포드-풀커슨 알고리즘에 대한 설명은 아쉽게도 여기서 끝나지 않습니다. 그리고 한가지 의문을 우리는 위에서부터 가지고 있습니다.
\(u\)에서 \(v\)로 양수의 유량을 보낸다는 것은, \(v\)에서 \(u\)로 음수의 유량을 보내는 것으로 간주합니다. 있지도 않을 수도 있는 역방향 간선을 왜 다루게 되는지는 나중에 서술하겠습니다.
위에서 다뤘던 음수의 유량 이야기도 설명을 해야하고요. 이제 다음 부분에서 이와 관련된 이야기를 다루어 볼까 합니다.
실제로 있지도 않은 역방향 간선이 필요한 이유
포드-풀커슨 알고리즘을 처음 공부하면서 이것이 가장 궁금했었습니다. 역방향 간선은 실제로 존재 하지도 않는데, 여기로 막 유량을 보내기도 하고, 책에는 역방향 간선이 존재하지 않으면 올바른 정답이 나오지 않는다고 적어놨긴 했는데, 역방향 간선으로 유량을 보내는게 정확히 어떤 의미를 가지는지도 모르겠고… 하는 그러한 물음 때문에 많이 답답했었습니다. 그래서 이 포스팅에서는, 저의 이 질문을 명쾌하게 해결해준 한 블로그의 자료를 적극적으로 참고하면서 글을 써보려고 합니다.
유량 그래프 하나를 데려오겠습니다.
위와 같은 유량 그래프에서 최대 흐름을 찾기 위해서, 증가 경로를 하나 찾아보겠습니다. 위에서 아무튼 이라고 강조 표시까지 해놨는데, 이유는 포드-풀커슨 알고리즘은 우리가 경로를 어떻게 찾든 별 상관을 하지 않습니다. BFS건 DFS건, 심지어 그냥 랜덤으로 길이 있을때까지 아무렇게나 가는것도 상관 없습니다.
그렇기 때문에 수많은 경로가 생길 수 있지만, 이렇게 경로를 찾았다고 가정해 봅시다. 그리고, 이제 찾아낸 경로에 흘릴 수 있는 최대 유량을 알아내고, 알아낸 최대유량 만큼 우리가 찾은 경로에서 사용하는 간선에 표시해 둡시다.
아직 경로를 더 찾을 수 있습니다. 경로를 찾은 결과가 아래의 그림과 같다고 가정해 보겠습니다.
이제 이 그림에서는 더이상 유량을 소스에서 싱크로 보낼 수 없습니다. 바로 위의 그림에서, 소스에서 싱크로 가는 유량의 합을 계산해보면, \(3+2+4=9\) 가 됩니다. 하지만, 그림 1의 그래프를 직접 노트에 그려서 직접 최대 유량을 손으로 계산해보면, 이것보다 더 좋은 결과물이 나올 수 있음을 알 수 있습니다.
S → A → D → T 로 1 S → A → E → T 로 2 S → B → E → T 로 2 S → C → F → T 로 4 S → C → F → E → T 로 1
이렇게 유량을 보내면, 총 유량은 \(10\)으로, 위의 결과보다 더 나은 답을 도출할 수 있음을 알게 되죠. 알고리즘이 이러한 상황을 만나게 되면 어떻게 하면 좋을까요? 여러가지 아이디어가 있을 수 있지만, 이러한 아이디어도 있을 수 있습니다.
기존에 선택했던 경로를 취소하고, 새로운 경로를 만들 수 있으면 이런 상황에서 좀 더 개선된 답을 찾을 수 있지 않을까?
S → A → E → T 에서, A → E 로 가는 경로를 1만큼 취소하고, 그걸 A → D → T 로 흘리면 최적의 답이 되겠다.
이러한 아이디어를 알고리즘이 수행할수 있게 해주는 고마운 요소가 존재하지도 않는 역간선 입니다.
문제상황을 설명하면서 예시로 든 상태, 즉 그림 4 에서, A→E 간선으로 흐르는 유량 하나를 취소하고, A에서 남는 유량을 A → D → T 를 통해서 유량을 1 더 흐르게 하면 우리가 원하는 최대 유량을 찾아 낼 수 있습니다. 이렇게 취소 역할을 해주는 역방향 간선을 잘 이용하면, 앞서 찾은 경로 때문에 최대 유량을 구하지 못하는 사태를 예방할 수 있게 됩니다. 역방향 간선\((v,u)\)로 유량을 n 만큼 보내면,
- 유량의 대칭성 : \(f(u,v) = -f(v,u)\) : 이건 좀 자명하지는 않습니다. \(u\)에서 \(v\)로 양수의 유량을 보낸다는 것은, \(v\)에서 \(u\)로 음수의 유량을 보내는 것으로 간주합니다.
위에서 다루었던 유량의 대칭성에 의해서 \((u,v)\)로 -n 만큼의 유량을 보내는 것, 즉 n만큼의 유량을 취소하는 것과 같게 됩니다.
역방향 간선이 실제 알고리즘에서 어떻게 보이는지 간단하게 확인하고 다음 내용으로 넘어가려고 합니다. 위의 알고리즘 설명에서, 유량이 남아있는 간선을 통해서 유량을 보낸다고 하였고, 유량을 계산하는 공식은 \(r(u,v) = c(u,v)-f(u,v)\) 입니다. 한번도 사용하지 않아서 잔여유량이 용량과 같은 \((u,v)\)에 대해서 잠깐 생각해 봅시다. 증가 경로를 어찌저찌 해서 찾아서, \((u,v)\)에 \(n\)만큼의 유량을 보내기로 결정되었다고 합시다. 다음 증가경로를 찾을 때에는, 역방향 간선 \((v,u)\)도 유량이 남아있는 간선으로 취급됩니다. 이게 어떻게 되는지는 위에서 언급한 잔여 유량을 계산하는 식을 잠깐 확인해 보면 알 수 있습니다. \((v,u)\)는 존재하지도 않은 간선이기에 용량은 0입니다만, \((u,v)\)에 \(n\)만큼의 유량이 흐르고 있고, 유랑의 대칭성에 의해, \((v,u)\)에는 \(-n\)만큼의 유량이 흐르고 있어, \((v,u)\)의 잔여 유량은 \(0-(-n)=n\)이 됩니다. 이는, 최대 \(n\)만큼의 유량을 취소할 수 있다는 의미이기도 하죠.
여기까지 포드-풀커슨 알고리즘에서 역방향 간선이 하는 일에 대해서 알아보았습니다.
정당성 증명
포드-풀커슨 알고리즘의 동작 방법은 이제 대략적으로 이해를 했습니다. 하지만, 이 알고리즘이 과연 정당한지는 다루지 않았습니다. 포드-풀커슨 알고리즘의 정당성 증명은 최소컷 최대유량 정리라는 잘 알려진 정의를 통해서 증명합니다. 이 정리는 단순히 이 알고리즘의 정당성을 증명하는데만 쓰는것이 아니라, 다양한 그래프 관련 문제를 푸는데에 도움을 줄 수 있는 매우 유용한 정리이므로, 잘 숙지를 했으면 좋겠습니다.
최소 컷 최대유량 정리
최소 컷 최대유량 정리는, 최소 컷 문제가, 최대유량 문제와 밀접하게 연관되어 있다는 것을 보여주는 정리입니다. 최소 컷 문제를 설명하기 위해서, 컷(cut)이라는 개념을 소개하도록 하겠습니다.
컷(cut)은 단어 의미 그자체로, 그래프를 두개의 조각으로 토막낸것을 의미합니다. 마치 아래의 그림의 오렌지가 반으로 토막난것 처럼요.
유량 그래프에서의 컷은, 시작점인 소스와 종점인 싱크가 다른 집합에 속하도록 그래프를 쪼갠것을 의미합니다. 시작점이 포함된 부분 즉 소스가 있는 컷을 \(S\)라고 부르고, 싱크가 포함된 컷을 \(T\)라고 일반적으로 부릅니다. \(S\)에서 \(T\)로 가는 간선들의 용량 합을 컷 \(S,T\)의 용량 이라고 하고, \(S\)에서 \(T\)로 실제로 가는 유량을 컷 \(S,T\)의 유량이라고 합니다.
그림 5 : 한 유량그래프에서의 적당한 임의의 컷
위 그림은, 한 유량 그래프에서 컷\(S\)를 \(\{s,a,c\}\) 라고 하고, 컷\(T\)를 \(\{b,d,t\}\)라고 했을때의 그림입니다. 이 컷\(S,T\)에서의 용량과 유량을 구해봅시다.
컷의 용량 : \(S\)에서 \(T\)로 가는 간선의 용량을 모조리 합한것이 되므로, \((a,b)\)와 \((c,d)\)의 용량을 더하면 되니, \(3+9=12\)가 됩니다. 컷의 유량 : \(S\)에서 \(T\)로 가는 유량을 모두 다하면 됩니다. 위의 그림에서 보이는 \((a,b)\)와 \((c,d)\)만 더하는 것이 아닌, 위 그림에는 안보이지만, 역방향 간선인 \((c,b)\)의 유량 -2도 신경 써줘야 합니다. 즉 컷의 유량은 \(3+6+(-2)=7\)이 됩니다.
유량 그래프에서의 모든 컷과 유량에서는 다음과 같은 속성 두개가 항상 성립한다고 합니다.
- 컷의 유량은 소스에서 싱크로 가는 총 유량과 같습니다. 어떤 컷이건 상관 없습니다. 네트워크의 모든 유량은 \(S\)에 포함된 소스에서 흘러나와 \(T\)로 가는 싱크로 흘러들어가기 때문입니다. \(T\)에서 \(S\)로 흘러오는 유량은 음수로 계산됨을 알고 있으므로, 유량의 일부가 \(S\)와 \(T\)를 여러번 오가는 경우에도 컷의 유량에는 한번만 포함됩니다. 2.컷의 유량은 용량과 같거나 작습니다. 모든 간선에 대해 유량은 용량 이하의 값이기 때문입니다. 용량 제한 속성을 보면 알 수 있지요.
2번 속성은 용량 제한 속성 그자체기 때문에 이해하기가 정말로 간단합니다. 하지만 1번 속성은 그렇게 빠르게 와닫지가 않는군요.
1번 속성을 증명하기 위해서는 유량 보존 제약을 통해서 설명할 수 있습니다.
- 유량의 보존 : \(\sum_{v\in V}f(u,v)=0\) : 이 속성은 각 정점에 들어오는 유량과 나가는 유량의 양이 같아야 한다는 뜻입니다. 위 식만 가지고는 어떻게 이게 그 뜻이 되는지 한번에 와닫지 않을 수 있습니다. 하지만, 위의 2번에서 다룬 유량의 대칭성에서, 정점에 들어오는 양은 음수로 표현을 하니, (예를 들어 \((a,u)\)를 통해 유량이 \(u\)로 온다면, \(f(u,a)\)는 음수의 유량으로 표현됩니다) 위의 식은 \(v\)에서 들어오고 나가는 유량의 모든 합을 표현하므로, 0이 되어야 한다는 사실을 알 수 있습니다. 정점에 유량이 저장되는 경우는 유량 그래프에서 다루지 않습니다.
컷 \(S\)의 모든 정점에서, 흘러 나가는 양에서, 흘러 들어오는 양을 뺀 값을 생각해 봅시다. 특수한 정점 s를 제외한 모든 정점은 흘러나가는 양에서 흘러 들어오는 양을 빼면 0이 됩니다. 고로 남는 값은 s에서 나가는 유량의 양이 되고, 이는 유량의 양과 같게 됩니다.
모든 컷에서의 용량은 다를 수 있습니다. 하지만, 모든 컷에서의 용량은 모두 같음을 방금 우리는 증명하였습니다. 그렇다는 뜻은, 가장 작은 용량을 가진 컷에서도 같은 유량이 흐른다는 것입니다. 만약에 잔여 용량이 0인 컷을 찾을 수 있다면, 그 컷의 용량이 곧 컷의 유량이 될 것이고, 이를 통해서 최대유량을 찾을 수 있을거라는 추측을 할 수 있습니다.
이렇게 찾은 유량이 실제 최대유량인지 증명 해봅시다. 한 유량 그래프에서 컷\((S,V)\)는 여러 종류가 있을 수 있지요. 여기서, 최소 컷을 하나 콕 집어서, \((S^*,V^*)\)라고 하고, 이 컷에 흐르는 유량을 \(\|f\|\)라고 합시다. 그리고 또 임의의 컷 하나를 잡아서 \((S,V)\)라고 합시다.
최대 흐름의 크기를 \(\|f^*\|\) 라고 합시다. 위의 정보와 이때까지 알고 있는 정보들을 조합해서 아래와 같은 부등식을 하나 작성할 수 있습니다.
\[c(S) = \|f\| \le \|f^*\| \le c(S^*) \le c(S)\]이 식을 해석하면 \(\|f\|=\|f^*\|\)가 되므로, 최소컷의 유량은 최대유량임을 알 수 있습니다.
이제 최소 컷을 구함으로, 최대 유량을 확실히 구할 수 있음을 알게 되었습니다. 그런데, 최소컷을 확실하게 구할 수 있는 방법은 어떻게 될까요?
최소컷의 유량은 최대유량이고, 최소컷은 유량과 용량이 같은 컷임을 이용하면 됩니다. 더이상 증가경로를 찾을 수 없는 그래프에서 소스 \(s\)에서 출발해 용량이 남아있는 간선을 통해서 갈 수 있는 정점을 \(S\)에 넣고, 나머지를 \(T\)에 넣어 버립시다. 이렇게 분류하면, 소스 \(s\)는 컷 \(S\)에 반드시 들어가고, 싱크 \(t\)는 반드시 컷\(T\)에 들어가게 됩니다.
이 분류에서, \(S\)는 \(s\)에서 갈 수 있는 정점만을 모아둔 것이므로, \(S\)에서 \(T\)로 나가는 간선은 없습니다. 그런게 있다면, 분류 조건에 모순되니까요. \(T\)에서 \(S\)로 가는 간선에 대해서 이제 생각해 봅시다.
- 해당 간선이 정방향 간선일 때 : 해당 간선의 역방향 간선에 해당하는 간선에 남는 유량이 없습니다. 있다면, \(S\)에서 \(T\)로 가는 역방향 간선이 있다는 것인데, 이는 위에서 언급했듯 모순입니다. 여기서 \(T\)에서 \(S\)로 가는 정방향 간선의 유량은 0임을 알 수 있습니다.
- 해당 간선이 역방향 간선일 때 : 해당 간선의 정방향 간선이 원래 그래프에 있었을 것입니다. 하지만, 그런 간선은 이제 남아있지 않는것 같군요. 여기서 \(S\)에서 \(T\)로 가는 간선의 유량은 용량을 꽉 채워서 갔음을 알 수 있습니다.
이제 컷 \(S\)의 용량을 계산할 수 있습니다. \(S\)에서 \(T\)로 가는 간선들은 모두 용량을 꽉 채워서 유량을 보냅니다. 그리고 \(T\)에서 \(S\)로 가는 간선은 유량을 아예 보내지 않는군요. 이는 곧 컷의 용량이 유량과 같다는 뜻입니다. 이 방법을 사용하면 최소 컷을 구할 수 있음을 알 수 있습니다.
이상이 최소 컷 최대 유량 정리 입니다. 이제 이를 이용해서 어떻게 포드-풀커슨 알고리즘의 정당성을 알 수 있는지 알아 봅시다.
실제의 정당성 증명
포드-풀커슨 알고리즘은 s에서 t까지 증가경로가 없을때까지 계속 시도합니다. 즉, 알고리즘이 종료되면, 증가경로를 더이상 찾을 수 없다는 뜻이죠.
최대유량이 흐르는 그래프에서는, 더이상 증가경로를 찾을 수 없습니다. 하지만 이 역이 바로 성립한다고는 이 명제만으로는 말할 수 없습니다. 잘 아시겠지만, 본래 명제가 참이라고 해서, 역 명제가 참이 아닐수도 있기 때문이니까요.
우리가 최소 컷 최대 유량 정리를 설명하면서 읽어봤던 설명을 다시 한번 천천히 읽어봅시다. 포드-풀커슨 알고리즘이 종료되면, 더이상 증가경로를 찾을 수 없는 그래프가 됩니다. 이 상태의 그래프에서 최소 컷을 항상 구하는 방법이 있음을 위에서 설명 하였고, 최소 컷의 용량은 최대 유량의 크기라는것을 나타내 보였습니다. 즉, 더이상 증가경로를 찾을 수 없을때까지 증가경로를 찾아서, 더이상 증가경로를 찾을 수 없을때의 유량 그래프에 흐르는 유량을 반환하는 포드-풀커슨 알고리즘은 정당함을 알 수 있습니다.
마치며
이번 글에서는 유량 그래프와, 유량 그래프에서의 최대 유량을 구하는 최대유량 문제를 해결하는 포드-풀커슨 알고리즘, 그리고 그 알고리즘의 정당성을 증명하기 위해서, 최대-유량 최소-컷 정리까지 알아보았습니다. 다음 글에서는, 포드-풀커슨 알고리즘의 삽질(?)을 막아주는 에드몬드-카프 알고리즘에 대해서 알아보고, 그 알고리즘의 시간복잡도, 그리고 그 정당성 까지 알아보겠습니다.
읽어주셔서 감사합니다.
참고한 글들
-
프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(구종만 저)
-
https://gazelle-and-cs.tistory.com/82?category=875540 : 종만북에서 좀 부족하다 느껴졌던 증명 부분을 완성하는데 큰 도움을 준 블로그 글
