여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결된 수도관을 따라 흘려주는 것입니다. 해당 지역에는 사람도 많고 공단도 있어서 최대한 많은 물을 공급받고 싶어합니다. 만약 두 지점 사이를 잇는 수도관이 딱 하나 있다면 쉽게 해결되겠지만, 문제는 이보다 더 복잡합니다. 바로 수도관이 여러 사정에 의해 매우 얼기설기 설치되어 있기 때문입니다. 게다가 수도관마다 연식이나 제원도 달라서 수도관마다 견딜 수 있는 수압이나 용량도 정해져 있습니다. 과연 물을 어떻게 흘려야 수도관에 무리를 주지 않고 해당 지역으로 최대한 많은 물을 보내줄 수 있을까요?
이 문제는 유명한 최적화 문제인 최대 흐름 문제(maximum flow problem)를 나타낸 것입니다. 예제에서도 쉽게 유추할 수 있듯이 이 문제는 이론적으로 흥미로울 뿐 아니라 여러 분야에서 응용될 수 있기 때문에 예전부터 깊이 탐구되었습니다. 특히, 이 문제가 널리 알려지고 많이 발전하게 된 때는 미국과 소련이 경쟁하던 냉전 시대인데, 그 이유는 이 문제가 군사적으로도 매우 요긴하였기 때문이라고 알고 있습니다. 이 문제에 관한 기본적인 내용들은 모두 그 당시에 정립된 것이라고 생각하셔도 무방하답니다.
이번 포스트에서는 최대 흐름 문제를 알아 보도록 하겠습니다. 특히, 아래에서는 다음 내용들을 차례대로 다룰 예정입니다.
- 문제 정의
- 평행 간선(parallel edge)과 역평행 간선(anti-parallel edge)
- 잔여 네트워크(residual network)
- 증가 경로(augmenting path)
이 글에서 용어의 번역은 최대한 다른 사이트나 블로그의 번역들과 동일하게 맞추려고 노력하였습니다. 이 글 저 글 읽어 보시며 본인에게 맞는 내용의 글을 찾는 동안 혹여나 용어 때문에 헷갈리는 것을 방지하고자 함입니다.
문제 정의
이 절에서는 최대 흐름 문제가 무엇인지 엄밀히 정의해 보도록 하겠습니다. 이 문제에서는 어떤 방향이 있는 그래프(directed graph) \(G = (V, E)\)와 함께 각 간선마다 용량(capacity) \(c : E \rightarrow \mathbb{R}_+\)이 주어집니다. 음수의 용량을 가지는 것은 상상하기 힘드므로, 용량은 항상 음이 아닌 수로 가정하도록 하겠습니다. 또한 모든 용량은 유한하다고 하겠습니다. 어떤 간선 \( \langle u, v \rangle \in E \)에 대해 편의 상 \( c( \langle u, v \rangle ) \)를 \( c(u, v) \)로 표현하도록 하겠습니다.(이는 아래 정의되는 비슷한 것들에 공통적으로 적용됩니다.) 이렇게 주어지는 방향 그래프와 용량을 통칭하여 흐름 네트워크(flow network)라고 부르기도 합니다.
흐름 네트워크와 함께 특별한 두 정점 \(s, t \in V\)가 주어집니다. 여기서 \(s\)는 시점(source)이라 부르고, \(t\)는 종점(sink)이라고 부릅니다. 시점과 종점은 항상 다르다고 가정하겠습니다. 네트워크에서 흐르는 유체는 무엇이든 될 수 있겠지만, 이 글에서는 편의 상 '물'이라고 하겠습니다.
이 문제에서 우리가 구해야 하는 것은 \(s\)에서 \(t\)로 흐르는 어떤 흐름(flow)입니다. 참고로 \(s\)에서 \(t\)로 흐른다는 것을 강조하기 위하여 \(s\)-\(t\) 흐름(\(s\)-\(t\) flow)라고 부르기도 합니다만, 이 글에서는 애매한 부분이 없으니 흐름이라고만 부르겠습니다. 흐름은 다음을 만족하는 어떤 함수 \(f : E \rightarrow \mathbb{R}_+\)로 정의됩니다.
- 용량 제약(capacity constraint) : 임의의 간선에 흐르는 양은 항상 \(0\)보다 크거나 같고, 해당 간선의 용량을 초과하지 못한다. 다시 말해, 모든 간선 \(e \in E\)에 대해, \( 0 \leq f(e) \leq c(e) \)이다.
- 흐름 보존 제약(flow conservation constraint) : 시점이나 종점이 아닌 모든 정점에 대해, 그 정점에서 흘러 나가는 양과 그 정점으로 흘러 들어오는 양은 동일하다. 다시 말해, 임의의 \(v \in V \setminus \{ s, t \}\)에 대해, \[ \sum_{e \text{ out of } v} f(e) = \sum_{e \text{ into } v} f(e) \tag{1} \]를 만족한다.
이 조건들이 흐름을 잘 표현하고 있다는 것을 알아 봅시다. 어떤 흐름이든 \(0\)보다 적게 흐를 수 없고 임의의 간선에 대해 정해진 용량을 넘을 수는 없으므로 첫 번째 제약 조건은 반드시 필요합니다. 또한, 시점 \(s\)에서만 물이 생성되고 종점 \(t\)에서만 소비되기 때문에 나머지 분기점들에 대해서는 반드시 들어온 양과 나간 양의 합이 동일해야 합니다. 따라서 두 번째 제약 조건도 합리적입니다.
컴퓨터 과학에서는 항상 무언가를 최적화하려고 노력합니다. 여기서는 무엇을 최적화할까요? 어떤 네트워크에 적게 흘리는 방법은 쉽게 구할 수 있습니다. 아무것도 흘리지 않으면 되기 때문이죠. 따라서 우리의 목표는 최대한 많이 흘리는 것이 됩니다. 물이 생성되는 지점은 시점뿐이므로 그 양은 시점에서 흘러 나가는 양에서 흘러 들어오는 양을 제외한 값으로 정의할 수 있습니다. 다시 말해,
\[ |f| := \sum_{e \text{ out of } s} f(e) - \sum_{e \text{ into } s} f(e) \tag{2} \]
로 쓸 수 있겠죠. 아래서는 이를 흐름양(value of flow)이라고 부르며, 간단히 \( |f| \)로 표기하도록 하겠습니다.
드디어 최대 흐름 문제를 정의할 수 있게 되었습니다.
최대 흐름 문제 (Maximum flow problem)
어떤 흐름 네트워크와 특정 시점과 종점이 주어졌을 때, 이 네트워크에서 시점에서 시작해 종점으로 향하는 흐름 중에서 그 양이 가장 큰 것을 찾으시오.
평행 간선(Parallel Edge)과 역평행 간선(Anti-Parallel Edge)
위 정의에서는 흐름 네트워크의 방향 그래프에 아무런 제약을 달지 않았습니다. 하지만 방향 그래프에 몇 가지 제약을 추가해도 일반성을 잃지 않는다는 사실을 쉽게 보일 수 있습니다.
첫 번째는 루프(loop)입니다. 방향 그래프에서 루프는 한 정점에서 출발해 다시 자기 자신으로 돌아오는 간선을 의미합니다. 잘 생각해 보면 루프는 흐름 네트워크 상에서 아무런 도움이 되지 않습니다. 루프를 통해 나간 만큼 다시 자기 자신으로 돌아오기 때문이죠. 따라서 네트워크에 루프가 없다고 가정해도 괜찮습니다.
다음은 평행 간선(parallel edge)입니다. 방향 그래프에서 서로 다른 두 간선 \(e_1\)과 \(e_2\)에 대해 두 간선이 동일한 머리(head)와 꼬리(tail)를 갖는다면 (즉, 두 간선의 방향이 동일하면) 우리는 두 간선이 평행하다고 말합니다. 하지만 어차피 우리의 목적은 최대 흐름을 찾는 것이므로 이러한 평행 간선들은 하나로 통합할 수 있습니다. 다시 말해, 평행한 \(e_1\), \(e_2\)가 있을 때 \(e_2\)를 그래프에서 지우고 대신 \(e_1\)의 용량을 \( c(e_1) + c(e_2) \)로 늘려버리는 것이죠. 이 작업을 평행한 간선이 없어질 때까지 반복해 주면 되겠습니다.
이렇게 용량을 합쳐도 괜찮다는 것은 쉽게 보일 수 있습니다. 바로 기존의 네트워크에서의 어떤 흐름을 가지고 와도 그와 동일한 양을 갖는 흐름이 새로 만들어진 네트워크에서도 흐를 수 있음을 보일 수 있기 때문입니다. 방법은 간단합니다. 만약 평행한 간선 \(e_1, e_2\)에 \(f(e_1), f(e_2)\)씩 흐르고 있다면, 둘을 합해서 흘려주면 됩니다. (엄밀히는 그 역도 보여야 두 네트워크가 동치라는 것을 증명하게 됩니다. 그 역은 무엇이며 어떻게 증명할 수 있을까요?)
이것으로 네트워크에 평행 간선이 없어도 무방하다는 것을 보였습니다만, 아직 눈에 거슬리는 비슷한 종류의 간선이 남아있습니다. 바로 역평행 간선(anti-parallel edge)인데요. 한 간선 \(e_1 = \langle u, v \rangle \)이 다른 간선 \(e_2 = \langle v, u \rangle \)과 끝점(endpoint)을 모두 공유하지만 정확히 반대의 방향을 가리킬 때 우리는 두 간선이 역평행하다고 부릅니다.
이러한 간선은 정점을 하나 추가함으로써 해소할 수 있습니다. 위와 같은 \(e_2 = \langle v, u \rangle\)에 대해 새로운 정점 \(w\)를 추가하고 \(e_2^\prime = \langle v, w \rangle \), \( e_2^{\prime\prime} = \langle w, u \rangle \)도 만들어 주고 대신에 \(e_2\)를 지우는 것이죠. 이때, 새로 만든 간선의 용량은 둘 다 \( c(e_2^\prime) = c(e_2^{\prime\prime}) = c(e_2) \)로 두면 됩니다. 이 작업을 모든 역평행 간선에 대해서 하면 되겠습니다.
역평행 간선을 지운 네트워크도 기존의 네트워크와 동치라는 것을 쉽게 보일 수 있습니다. 새로 만들어진 간선들에다 원래 흐르던 유량을 그대로 흘려주면 되기 때문입니다. (역도 생각해 보세요.)
다만 여기서 주의할 점은 역평행 간선을 제거할 시 새로운 네트워크에 새로운 정점과 간선이 추가된다는 점입니다. 그러나 정점의 개수나 간선의 개수가 각각 최대 \( \frac{|E|}{2} \) 정도 증가하는 것뿐이므로 본래 입력에 비해 그렇게 커지지는 않습니다. (자세히는 기존 입력의 최대 두 배 정도 증가하게 됩니다.) 따라서 우리는 다음과 같은 정리를 유도할 수 있습니다.
정리 1. 평행 간선과 역평행 간선이 없는 네트워크의 일반성
최대 흐름 문제를 풀 때, 우리는 일반성을 잃지 않고 흐름 네트워크에 루프, 평행 간선, 역평행 간선이 존재하지 않는다고 가정할 수 있다.
실제로 문제를 풀 때는 루프, 평행 간선만 없고 역평행 간선은 있을 수 있는 네트워크를 가정하는 경우가 훨씬 많습니다. 평행 간선은 간선이 없어지기만 할 뿐이어서 여러모로 도움이 되지만, 역평행 간선을 지우면 정점과 간선의 수가 늘어나므로 수행 시간에 손해를 주기 때문입니다. 다행히 앞으로 소개할 알고리즘들 모두 역평행 간선이 있는 경우에도 문제 없이 수행됩니다. 그럼에도 역평행 간선을 지운 이유는 분석이 훨씬 간단해지기 때문입니다. 따라서 아래 절에서는 평행 간선뿐 아니라 역평행 간선도 없는 네트워크를 가정하도록 하겠습니다.
잔여 네트워크(Residual Network)
어려운 개념을 공부하기 전에, 간단한 예시를 먼저 살펴 보도록 하죠. 다음 그림과 같은 흐름 네트워크가 주어졌다고 하겠습니다.
우리의 목표는 시점 \(s\)에서 종점 \(t\)까지 물을 흘리는 것입니다. 그러니 일단 다음과 같이 아무렇게나 흘려보도록 하겠습니다.
위 그림에서 빨간색 경로를 따라서 물을 흘린다면 최대 얼마큼 흘릴 수 있을까요? 간선 \( \langle s, a \rangle \)와 \( \langle b, t \rangle \)는 최대 \(2\)만큼의 양을 감당할 수 있습니다만, 간선 \( \langle a, b \rangle \)는 최대 \(1\)만 감당할 수 있습니다. 따라서 이 경로를 따라 \(1\)의 물을 흘려주도록 하겠습니다. 그러면 다음과 같은 흐름을 얻을 수 있습니다.
아직 우리는 네트워크에 \(s\)에서 \(t\)까지 더 많은 물을 흘릴 수 있습니다. 이번에는 다음과 같이 흘려 보도록 하죠.
동시에 두 경로를 따라서 물을 흘린다고 생각하셔도 무방하고, 하나씩 흘린다고 보셔도 괜찮습니다. 두 경로를 따라서 흘릴 수 있는 물의 양은 얼마인가요? 두 경로 각각 최대 \(1\)의 양을 흘릴 수 있습니다. 위의 경로는 \( \langle s, a \rangle \)에 이미 \(1\)만큼의 흐름이 있기 때문이고, 반대로 아래의 경로는 \( \langle b, t \rangle \)에 이미 \(1\)만큼 흘러가고 있어서 그렇습니다. 따라서 두 경로를 따라 최대로 흘려주면 다음과 같은 흐름을 얻게 됩니다.
이 흐름의 양은 얼마인가요? 시점 \(s\)에서 \(a\)로 \(2\)의 양이, \(b\)로 \(1\)의 양이 흘러 나가고 있고, \(s\)로 들어오는 흐름은 없으므로 흐름양은 \(3\)이 됩니다. 이제 이 흐름을 보존하면서 물을 더 흘리는 방법을 찾아 봅시다. 음, 눈을 씻고 찾아 봐도 그러한 방법은 보이지 않습니다. 현재 \(s\)에서 나가는 간선 중 여유가 있는 간선은 \( \langle s, b \rangle \)입니다. 하지만 우리가 이 간선으로 물을 조금이라도 흘린다면, 흐름 보존 제약에 의해 \(b\)에서는 그만큼 또 물을 내보내야 합니다. 하지만 \(b\)에는 그럴 여력이 있는 간선이 없습니다. 따라서 이 흐름을 그대로 두면서 더 이상 물을 흘리는 방법은 없습니다.
그럼 이 흐름이 네트워크에서의 최대 흐름일까요? 아니죠. 다음 그림과 같이 간선 \( \langle a, b \rangle \)로 물을 보내지 말고 두 경로를 따라 곧장 \(2\)의 양을 흘려주면 우리는 흐름양이 \(4\)인 흐름을 얻을 수 있습니다. 그리고 이 흐름이 위 네트워크의 최대 흐름이 된다는 사실도 어렵지 않게 보일 수 있습니다. \(s\)에서 나가는 간선의 용량을 모두 소진했기 때문이죠.
어째서 이러한 결과가 나왔을까요? 네, 처음에 택한 경로 자체가 이상했기 때문입니다. 거기서 \( \langle a, b \rangle \)를 쓰지 말았어야 했습니다. 처음에 굳이 그 간선을 지나는 경로를 선택한 것에 의아하셨을 분도 계시리라 생각합니다. 위 네트워크는 크기도 작고 최대 흐름이 어떤 식으로 흐를지도 쉽게 보이기 때문이죠. 물론 예시를 위해 의도적으로 정한 것이기는 합니다만, 만약 훨씬 크고 복잡한 네트워크가 입력으로 주어진 경우에는 어떨지 상상해 보시기 바랍니다. 어떤 식으로 흘려야 할지 감이 잡히지 않을 테고 지금 유지하고 있는 흐름이 최대 흐름으로 가는 길목에 있는지도 알기 어려울 것입니다.
본론으로 돌아와서, 비록 "잘못된" 경로를 통해 물을 흘렸다고 할지라도 현재의 흐름을 수정하여 최대 흐름으로 만드는 방법은 없을까요? 만약 그런 방법이 전혀 불가능하다면 아무래도 문제 자체가 너무 어려워질 겁니다. 완전히 처음부터 모든 것을 생각해야 할테니 말이죠. 다행히도 현재 흐름에서 수정하는 방법이 존재합니다. 바로 다음 그림처럼 흐름을 '취소'하는 것이죠.
이 그림은 다음과 같이 해석할 수 있겠습니다. 일단 \(s\)에서 \(b\)까지 \(1\)의 양을 흘릴 수 있으니 흘려 줍니다. 그러면 \(b\)의 입장에서는 \(1\)만큼의 초과분이 발생합니다. 이를 원래 \( \langle a, b \rangle \)을 통해 흐르던 \(1\)의 양을 취소함으로써 해결하는 것이죠. 이를 그림 11에서는 파란색 점선의 역방향 간선으로 표현하였습니다. 취소로 인하여 이번에는 정점 \(a\)에서 \(1\)만큼의 미달분이 발생합니다. 이는 \( \langle a, t \rangle \)로 \(1\)을 흘려줘서 해결해 줍니다. 그러면 모든 제약 조건을 만족하면서 기존보다 \(1\)의 양이 더 흐르는 흐름을 만들 수 있습니다.
위 논의를 정리하면 다음과 같습니다. 일단 시점에서 종점까지 흘릴 수 있는대로 흘려보는 방법을 생각해 봅니다. 안타깝게도 그 방법은 그림 9에서 확인하였듯 최대 흐름을 얻지 못할 수 있습니다. 이를 해결하기 위해서는 과거에 잘못 흘린 부분을 번복할 필요도 있습니다. 이를 적절히 활용한다면 아마도 최대 흐름을 구할 수 있을 겁니다. 그러기 위해서는 네트워크의 간선마다 얼마큼의 물을 더 흘릴 수 있고, 반대로 얼마큼의 물을 취소할 수 있는지를 알려주는 무언가가 필요합니다.
그 개념을 정형화시킨 것이 바로 잔여 네트워크(residual network)입니다. 이를 정의하기 위해서는 몇 가지 준비물이 필요합니다. 첫 번째로는 잔여 네트워크에서 사용할 간선들입니다. 곰곰이 생각해 보면, 만약 어떤 간선에 흐름이 용량 가득 흐르고 있다면 더 이상 이 간선으로는 무언가를 흘릴 수 없을 것입니다. 반대로 어떤 간선에 아무것도 흐르고 있지 않다면, 이 간선에는 번복할 흐름이 없습니다. 따라서 어떤 흐름 네트워크 \(G = (V, E), c\)와 그 위의 가능한 흐름 \(f\)가 주어졌을 때 나중에 사용할 간선들을
\[ E_f := \{ \langle u, v \rangle : \langle u, v \rangle \in E, f(u, v) < c(u, v) \} \cup \{ \langle v, u \rangle : \langle u, v \rangle \in E, f(u, v) > 0 \} \]
으로 정의하겠습니다. 첫 번째 집합에 속한 간선들은 바로 아직 여유분이 있어 해당 간선의 방향으로 흐름을 더 보낼 수 있는 간선들입니다. 반대로 두 번째 집합은 해당 간선으로 얼마큼의 흐름이 흐르고 있어서 그 역방향으로 이를 취소할 수 있는 것을 나타낸 것입니다. 첫 번째 종류의 간선을 전진 간선(forward edge), 두 번째는 후진 간선(backward edge)이라고 부릅니다.
앞에서 우리는 정리 1을 통해 입력되는 흐름 네트워크에 루프, 평행 간선, 역평행 간선이 없다고 가정하였습니다. 이렇게 가정한 게 여기서 드디어 빛을 발합니다. 바로 잔여 네트워크의 간선들이 원래 네트워크의 하나의 간선에 대응이 되기 때문입니다. 다음 정리를 보시죠.
정리 2. 원래 네트워크와 잔여 네트워크의 대응 관계
\(E\)에 루프, 평행 간선, 역평행 간선이 없다면 \(E_f\)는 다음을 만족한다.
- \(E_f\)에도 루프와 평행 간선은 존재하지 않는다.
- \(E_f\)의 모든 간선은 정확히 하나의 \(E\)에 있는 간선으로부터 정의된다.
- 만약 \( \langle u, v \rangle \in E_f \)라면, \(E\)에는 반드시 \( \langle u, v \rangle \)나 \( \langle v, u \rangle \) 중 정확히 하나가 있어야 한다.
[증명] 명제 1이 거짓이 되기 위해서는 \(E\)에 루프나 평행 간선이 존재해야 합니다.
명제 2가 거짓이 되기 위해서는 \(E\)의 서로 다른 두 간선 \(e_1, e_2\)의 전진 혹은 후진 간선이 \(E_f\)의 어떤 한 간선이 되어야 합니다. 그러기 위해서는 \(e_1\)과 \(e_2\)가 동일한 끝점을 가지고 있어야 합니다. 하지만 \(E\)에는 루프, 평행 간선, 역평행 간선 모두 없으므로 이는 불가능합니다.
마지막으로 \( \langle u, v \rangle \)이 \(E_f\)에 정의되었다는 뜻은 \( \langle u, v \rangle \in E \)의 전진 간선 조건이 만족하거나 \( \langle v, u \rangle \in E\)의 후진 간선 조건이 만족했다는 뜻입니다. 역평행한 간선은 존재하지 않으므로 둘 중 정확히 하나만 존재할 수 있습니다. □
잔여 네트워크도 일종의 흐름 네트워크이고 따라서 용량도 정의해 주어야 합니다. 그 용량을 \(c_f : E_f \rightarrow \mathbb{R}_+\)이라고 부르겠습니다. 이는 전진 간선이냐 후진 간선이냐에 따라 다르게 정의됩니다. 임의의 전진 간선 \( \langle u, v \rangle \in E_f \cap E \)에 대해, \[ c_f(u, v) := c(u, v) - f(u, v) \]로 정의하겠습니다. 이는 해당 간선으로 현재 \(f\)에 의해 \( f(u, v) \)만큼이 흐르고 있으니 용량에서 그 값을 제외한 만큼 더 흘릴 수 있다는 것을 나타냅니다. 정리 2의 명제 2에 의해서 \( c(u, v) \)와 \(f(u, v)\)는 모호하지 않습니다.
반대로 모든 후진 간선 \( \langle v, u \rangle \in E_f \setminus E \)에 대해서는 \[ c_f(v, u) := f(u, v) \]로 정의합니다. 이 값은 현재 \( \langle u, v \rangle \)로 \(f(u, v)\)만큼이 흐르고 있으니 역방향으로 최대 그만큼 취소할 수 있다는 것을 알려줍니다. 똑같이 정리 2에 의해 \(f(u, v)\)는 애매하지 않으므로 잘 정의가 됩니다.
이제 잔여 네트워크를 정의할 수 있습니다. 임의의 흐름 네트워크 \(G = (V, E), c\)와 그 위에서 가능한 어떤 흐름 \(f\)가 주어졌을 때, 동일한 정점에 \(E_f\)의 간선을 갖는 방향 그래프 \(G_f = (V, E_f)\)와 함께 \(c_f\)를 용량으로 갖는 흐름 네트워크를 흐름 \(f\)에 대한 잔여 네트워크라고 합니다.
이렇게 만든 잔여 네트워크는 다음과 같은 흥미로운 성질을 갖고 있습니다. 이는 다음 절에서 요긴하게 사용됩니다.
정리 3. 잔여 네트워크 용량의 양수성
흐름 \(f\)의 잔여 네트워크 \(G_f, c_f\)에서 임의의 간선의 용량은 항상 \(0\)보다 크다. 다시 말해, \(e \in E_f\)에 대해 \( c_f(e) > 0 \)을 만족한다.
[증명] 어떤 간선 \( \langle u, v \rangle \in E_f \)가 전진 간선으로 있기 위해서는 \( f(u, v) < c(u, v) \)여야 합니다. 따라서 \( c_f(u, v) = c(u, v) - f(u, v) > 0 \)임을 알 수 있습니다. 반대로 \( \langle v, u \rangle \in E_f \)가 후진 간선으로 존재하려면 \( f(u, v) > 0 \)이어야 하고, 따라서 \( c_f(v, u) = f(u, v) > 0 \)을 만족합니다. □
증가 경로(Augmenting Path)
위 절에서 우리는 임의의 흐름이 네트워크에 흐르고 있을 때 어떤 간선에는 얼마나 더 물을 흘려 넣을 수 있고, 어떤 간선에는 역으로 얼마큼 많은 양의 물을 취소할 수 있는지에 대한 정보를 담고 있는 잔여 네트워크에 대해서 알아 보았습니다. 우리가 이를 고안한 가장 큰 이유는 어떤 흐름을 유지하고 있을 때, 이를 기반으로 현재의 흐름보다 더 많은 양의 물을 흘려 넣는 방법을 만들기 위해서입니다.
이제 앞에서 정의한 잔여 네트워크가 우리가 의도한 대로 동작하는지를 따져볼 차례입니다. 잔여 네트워크에서 \(s\)에서 \(t\)로 물을 더 흘려 넣거나 취소하는 여러 방법들이 있겠지만, 우리는 그중에서도 가장 간단한 것을 가지고 놀아 볼까 합니다. 바로 \(s\)에서 \(t\)로 향하는 단순 경로입니다.(단순 경로는 순환(cycle)이 없는 경로를 뜻합니다.) 그러한 경로가 존재한다면, 해당 경로를 따라 물을 넣거나 뺄 수 있을 것입니다.
이 생각을 정형화 해보죠. 어떤 흐름 \(f\)에 대한 잔여 네트워크 \(G_f, c_f\)를 가지고 옵시다. 여기서 \(s\)와 \(t\)를 잇는 임의의 단순 경로 \(P \subseteq E_f \)를 하나 생각합시다. 이제 잔여 네트워크 상의 어떤 흐름 \(f_P : E_f \rightarrow \mathbb{R}_+\)를 다음과 같이 정의하도록 하겠습니다:
\[ f_P(e) := \left\{ \begin{array}{ll} \min \{ c_f(e) : e \in P \}, & \text{if } e \in P, \\ 0, & \text{otherwise.} \end{array} \right. \]
말인 즉슨, \(P\)의 간선 용량 중 가장 작은 양을 정확히 \(P\)의 경로를 따라 흐르는 흐름을 의미합니다. 마지막으로 \( f \)에 \(f_P\)를 다음과 같이 적용한 것을 \( f \uparrow f_P : E \rightarrow \mathbb{R}_+ \)라고 하겠습니다:
\[ f \uparrow f_P (u, v) := \left\{ \begin{array}{ll} f(u, v) + f_P(u, v), & \text{if } \langle u, v \rangle \in P, \\ f(u, v) - f_P(v, u), & \text{if } \langle v, u \rangle \in P, \\ f(u, v), & \text{otherwise.} \end{array} \right. \]
이는 \(f\)에 대해 \(P\)의 각 간선을 따라 가면서 만약 전진 간선이면 \( |f_P| \)를 더해주고, 후진 간선이면 그만큼 빼주는 것을 의미합니다.
지금까지 우리가 하고자 하는 것을 수학적인 기호로 표현해 보았으니 남은 것은 실제로 우리가 의도한 대로 주어진 흐름에서 해당 경로를 따라 물을 더 흘려주는 방법을 찾을 수 있는지 검증하는 것입니다. 이를 위해서 몇 가지 재미있는 정리들을 증명하도록 하겠습니다. 첫 번째 정리는 잔여 네트워크에서 이 경로를 따라 흐르는 양은 양수라는 점입니다.
정리 4. 증가 경로 흐름의 양수성
어떤 흐름 \(f\)에 대한 잔여 네트워크 \(G_f, c_f\)에 \(s\)에서 \(t\)로 향하는 단순 경로 \(P \subseteq E_f\)가 있을 때, \( |f_P| > 0 \)이다.
[증명] 정리 3에서 임의의 \(e \in E_f\)에 대해 \( c_f(e) > 0 \)임을 보였습니다. 따라서 \( \min \{ c_f(e) : e \in P \} > 0 \)임은 쉽게 알 수 있습니다. □
다음 정리는 이번 글에서 가장 중요한 정리로, \( f \uparrow f_P \)도 원래 네트워크에서 흐를 수 있는 흐름이며, 그 양이 \(f\)에 비해 \( |f_P| \)만큼 증가한다는 것입니다. 따라서 실지로 \( f \)에다 \( P \)를 따라서 물을 더 흘려주는 방법이 있다는 것을 보여주게 되죠. 이러한 성질 덕분에 \(P\)를 증가 경로(augmenting path)라고 부르기도 합니다.
정리 5. 증가 경로 적용하는 방법
어떤 흐름 \(f\)에 대한 잔여 네트워크 \(G_f, c_f\)에 \(s\)에서 \(t\)로 향하는 단순 경로 \(P \subseteq E_f\)가 있다고 하자. 그러면 \(f \uparrow f_P\)는 원래의 흐름 네트워크 \(G, c\) 상 \(s\)에서 \(t\)로 흐를 수 있는 흐름이며 그 양은 정확히 \( |f| + |f_P| \)이다.
[증명] 먼저 \( f \uparrow f_P \)가 가능한 흐름인지를 보이겠습니다. 이는 원래 네트워크에서 흐름의 두 제약 조건인 용량 제약과 흐름 보존 제약을 만족하는지를 통해 증명할 수 있습니다.
ㄱ. 용량 제약. 임의의 \(\langle u, v \rangle \in E\)에 대해서 모두 용량 제약을 만족하는지 따져 보겠습니다. 만약 \( \langle u, v \rangle \notin P \)이고 \( \langle v, u \rangle \notin P \)인 경우에는 원래의 \(f(u, v)\)를 그대로 갖고 있으므로 용량 제약은 자연스럽게 만족하게 됩니다.
다음은 \( \langle u, v \rangle \in P \)인 경우(즉, 전진 간선의 경우)입니다. 이때는 해당 간선을 따라 흐르는 양이 증가하기만 하므로 용량을 초과하지 않는지 따지기만 하면 됩니다. 이 경우는 \( \langle u, v \rangle \)가 \(G_f\)에 전진 간선으로 존재한 상황입니다. 따라서 정의에 의해 \[ c_f(u, v) = c(u, v) - f(u, v) \Rightarrow c(u, v) = f(u, v) + c_f(u, v) \]임을 알 수 있습니다. 이때, \( |f_P| \)는 \(P\) 위의 간선의 용량 중 가장 작은 값이므로, \[ c(u, v) = f(u, v) + c_f(u, v) \geq f(u, v) + |f_P| = f(u, v) + f_P(u, v) = f \uparrow f_P (u, v) \]를 이끌어낼 수 있습니다.
마지막으로 \( \langle v, u \rangle \in P \)인 경우(즉, 후진 간선의 경우)에는 흐르는 양이 감소하기 때문에 \(0\)보다 크거나 같은 양이 흐르는지를 살펴보면 됩니다. 이는 \( \langle v, u \rangle \)가 \(G_f\)의 후진 간선이었다는 뜻이고, 따라서 원래 네트워크의 \( \langle u, v \rangle \)에서 일정 값을 빼주는 상황인 겁니다. 정의에 의해 \[ c_f(v, u) = f(u, v) \]이며 위에서와 똑같이 \( |f_P| \)가 \( P \) 위의 간선 용량 중 가장 작은 값이어서, \[ f \uparrow f_P (u, v) = f(u, v) - f_P(u, v) = f(u, v) - |f_P| \geq f(u, v) - c_f(v, u) = 0 \]을 만족한다는 것을 알 수 있습니다. 이것으로 \( f \uparrow f_P \)가 원래 네트워크의 각 간선의 용량 제약을 모두 만족한다는 것을 증명하였습니다.
ㄴ. 흐름 보존 제약. \(P\)가 지나가지 않는 정점들은 흐름의 변화가 없으므로 원래 \(f\)가 흐름이었다는 사실에서 흐름 보존 제약이 그대로 만족하게 됩니다. 만약 \(P\)가 \(s, t\)가 아닌 어떤 \(v\)를 지나간다고 한다면, \(P\) 상에서 \(v\)의 바로 앞에 위치한 \(u\)와 바로 뒤에 위치한 \(w\)가 반드시 있을 것입니다. \(P\)가 단순 경로이므로 \(u\)와 \(w\)는 정확히 하나로 결정됩니다. 다시 말해,
\[P = \langle s, \cdots, u, v, w, \cdots, t \rangle \]
로 쓸 수 있습니다. \(f \uparrow f_P\)에서 \(v\)로 들어오는 양과 \(v\)에서 나가는 양이 어떻게 변화하는지 따져봅시다.
만약 \( \langle u, v \rangle \)와 \( \langle v, w \rangle \)가 모두 전진 간선이라면, 원래 네트워크에서 정확히 두 간선의 흐름이 \( |f_P| \)씩 증가하게 됩니다. 근데 \( \langle u, v \rangle \)는 \(v\)로 들어오는 간선이고, 반대로 \( \langle v, w \rangle \)는 나가는 간선이므로 식 1의 양 변이 \( |f_P| \)씩 증가하게 되어 흐름 보존 제약이 성립하게 됩니다. \( \langle u, v \rangle \)와 \( \langle v, w \rangle \)가 둘 다 후진 간선인 경우에도 비슷한 방식으로 증명해 줄 수 있습니다.
반대로 \( \langle u, v \rangle \)는 전진 간선이나 \( \langle v, w \rangle \)가 후진 간선인 경우에는 원래 네트워크에서 \( \langle u, v \rangle \)를 따라 \( |f_P| \)가 증가하나 \( \langle w, v \rangle \)를 따라서는 \( |f_P| \)가 감소하게 됩니다. 따라서 비록 두 간선 모두 \(v\)로 들어오는 간선이나 들어오는 양의 변화는 없기 때문에 여전히 흐름 보존 제약을 만족합니다. 나머지 \( \langle u, v \rangle \)가 후진 간선이고 \( \langle v, w \rangle \)가 전진 간선인 경우에도 비슷한 방식으로 증명해 주면 되겠습니다. 이것으로 모든 경우에 대해 흐름 보존 제약이 성립함을 보였고, 자연스럽게 우리는 \( f \uparrow f_P \)는 원래 네트워크에서도 가능한 흐름이라는 것을 알 수 있게 됩니다.
ㄷ. 흐름양의 증가. \( |f \uparrow f_P| = |f| + |f_P| \)임을 증명해 봅시다. \(P\)가 단순 경로이므로 \(P\)에는 순환이 존재하지 않습니다. 따라서 \(s\)와 연결된 간선은 \(P\)의 첫 번째 간선 뿐입니다. 이 간선을 \( \langle s, x \rangle \)라고 부르겠습니다. 만약 \( \langle s, x \rangle \)가 전진 간선이라면, 원래 네트워크에도 \(s\)에서 나가는 방향의 간선 \( \langle s, x \rangle \)가 있었을 것입니다. 그 방향으로 \( |f_P| \)만큼 더 흘려주는 것이므로 흐름양의 정의(식 2)에 의해 식이 성립하게 됩니다. 반대로 후진 간선이라면 원래 네트워크에는 \( \langle x, s \rangle \)가 있었을 것이고, 따라서 \(f\)에서 \(s\)로 들어오는 양이 \( |f_P| \)만큼 빠지게 되어 결과적으로 흐름양은 그만큼 증가하게 됩니다. □
정리 5를 통해 우리는 최대 흐름이라면 다음과 같은 성질을 만족한다는 것을 보일 수 있습니다.
정리 6. 최대 흐름이 갖는 성질
만약 \(f\)가 최대 흐름이라면 \(G_f\)에는 \(s\)에서 \(t\)로 도달할 수 없다.
[증명] 그렇지 않다면 \(s\)에서 \(t\)로 향하는 단순 경로 \(P\)가 존재할 것입니다. 정리 5에 의해 \( f \uparrow f_P \)는 원래 네트워크에 흐를 수 있는 흐름이며 흐름양은 \( |f| + |f_P| \)입니다. 정리 4에 의해서 이는 \( |f| \)보다 크기 때문에 \( f \)가 최대 흐름이라는 사실에 모순이 됩니다. □
마치며
이것으로 최대 흐름 문제가 어떤 문제이고 최대 흐름은 어떤 특징을 갖고 있는지에 대해서 알아 보았습니다. 위 내용을 가볍게 정리하면 다음과 같습니다.
- 최대 흐름 문제는 어떤 흐름 네트워크가 주어졌을 때 용량 제약과 흐름 보존 제약을 만족하면서 미리 정해지는 시점에서 종점으로 최대한 많은 양의 물을 흘려 보내는 방법을 찾는 문제입니다.
- 일반성을 잃지 않고 흐름 네트워크에는 루프, 평행 간선, 역평행 간선이 존재하지 않는다고 가정할 수 있습니다.
- 어떤 흐름 네트워크 위에서 흐를 수 있는 흐름이 하나 주어졌을 때, 그 흐름을 기준으로 어떤 간선에는 물을 얼마큼 더 흘려줄 수 있고 어느 간선에는 물을 얼마나 취소할 수 있는지에 대한 정보를 갖는 보조 네트워크를 해당 흐름의 잔여 네트워크라고 부릅니다.
- 잔여 네트워크 위에서 \(s\)에서 \(t\)로 향하는 단순 경로가 존재한다면, 이를 활용하여 현재의 흐름보다 더 많은 양의 물이 흐르는 흐름을 만들 수 있습니다. 따라서, 최대 흐름에는 그것의 잔여 네트워크 위에 \(s\)에서 \(t\)로 도달할 수 없습니다.
정리하고 보니 무겁군요. 그만큼 깊이 연구된 분야라서 그렇다고 생각합니다.
정리 6은 최대 흐름에 대한 잔여 네트워크에서는 \(t\)가 \(s\)에 도달할 수 없다는 사실을 알려 줍니다. 그렇다면 과연 역은 어떻게 될까요? 다시 말해, 어떤 흐름 \(f\)가 주어졌을 때, \(G_f\)를 살펴 봤더니 \(t\)가 \(s\)로부터 도달할 수 없다면, \( f \)는 최대 흐름이 될까요? 아니면 꼭 그렇지는 않을까요? 놀랍게도 이 성질은 최대 흐름을 결정하는 필요충분조건이 됩니다. 이는 다음 글에서 같이 알아 보도록 하겠습니다.
또한, 위에서 네트워크의 용량은 모두 유한하다고 가정하였습니다. 하지만 경우에 따라서는 어떤 간선의 용량이 무한하다고 가정할 필요가 있을 수도 있습니다. 이 경우에는 최대 흐름 문제를 해결하지 못하는 걸까요? 그렇지 않습니다. 다만, 무한의 용량을 갖는 간선들을 잘 다루어 주어야 합니다. 이와 관련해서도 다음에 포스트해 보도록 하겠습니다.
긴 글을 모두 읽어 주셔서 고맙습니다. 혹시 잘못된 점이 있거나 궁금하신 점이 있으시면, 알려 주시기 바랍니다.
참조
[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. (a.k.a. CLRS)
'조합론적 최적화 > Flow & Circulation' 카테고리의 다른 글
| 서큘레이션 (Circulation) (0) | 2023.12.23 |
|---|---|
| 디니츠의 알고리즘 (Dinitz' Algorithm) (6) | 2021.02.27 |
| 에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm) (6) | 2021.02.21 |
| 포드-풀커슨 방법 (Ford-Fulkerson Method) (0) | 2020.08.30 |
| 최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem) (7) | 2020.08.29 |
