저번 글에서는 최대 흐름 문제(maximum flow problem)가 무엇인지 알아 보고 최대 흐름이 만족하는 성질들도 함께 확인해 보았습니다. 최대 흐름 문제가 무엇인지 잘 모르신다면 이전 포스트를 참조하시기 바랍니다.
2020/08/29 - [기초 강좌/Algorithm analysis] - 최대 흐름 문제 이해하기 (Maximum Flow Problem)
최대 흐름 문제 이해하기 (Maximum Flow Problem)
여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결
gazelle-and-cs.tistory.com
결론부터 말씀드리면 최대 흐름의 잔여 네트워크(residual network)에서 종점 \(t\)는 시점 \(s\)로부터 도달할 수 없다는 것이었습니다.
정리 1. 최대 흐름이 갖는 성질
최대 흐름의 잔여 네트워크 위에서는 시점에서 종점으로 향하는 경로가 존재하지 않는다.
글의 말미에는 다음과 같은 질문을 던졌죠. 과연 위 명제의 역은 참일까요? 다시 말해, 어떤 흐름의 잔여 네트워크에서 종점이 시점으로부터 도달 가능하지 않다면 해당 흐름은 최대 흐름일까요?
정답은 '역도 성립한다.'입니다. 그 말인 즉슨, 어떤 흐름이 최대 흐름일 필요 충분 조건은 그것의 잔여 네트워크 위에서 시점에서 종점으로 가는 경로가 존재하지 않는다는 것이죠. 그리고 이 관계의 기저에는 유명한 최대 흐름 최소 절단 정리(max-flow min-cut theorem)가 깔려 있습니다. 이번 포스트에서는 이에 대해서 심층적으로 분석해보도록 하겠습니다.
이 글은 다음 내용을 다룰 예정입니다.
- 간단한 복습
- 절단(cut)과 순 흐름(net flow)
- 최대 흐름 최소 절단 정리(max-flow min-cut theorem)
많은 내용을 참조하고 있을 뿐 아니라 용어나 기호도 이전 포스트를 공유하고 있다는 점을 알려드립니다.
간단한 복습
최대 흐름 문제는 다음과 같이 정의되었습니다. 우리에게는 어떤 방향 그래프(directed graph) \(G = (V, E) \)와 유한의 음이 아닌 용량(capacity) \(c : E \rightarrow \mathbb{R}_+\)로 이루어진 흐름 네트워크(flow network)가 주어집니다. 여기서 \(G\)에 루프, 평행 간선, 역평행 간선이 없어도 일반성을 잃지 않는다는 것을 저번 글에서 보였습니다. 이와 동시에 서로 다른 특별한 두 정점 \(s\)와 \(t\)가 주어지게 되죠. 이를 각각 시점(source)과 종점(sink)이라고 합니다. 우리의 목표는 용량 제약(capacity contraint)과 흐름 보존 제약(flow conservation constraint)을 모두 만족하는 \(G, c\) 위에서 \(s\)에서 \(t\)로 흐르는 흐름 \(f : E \rightarrow \mathbb{R}_+ \) 중에서 흐름양(value of flow)
\[ |f| := \sum_{e \text{ out of } s} f(e) - \sum_{e \text{ into } s} f(e) \]
가 가장 큰 것을 찾는 것이죠.
어떤 흐름 \(f\)가 주어졌을 때, 본래 네트워크의 어떤 간선에는 얼마큼의 물을 더 흘릴 수 있으며, 어떤 간선에는 반대로 얼마나 많은 양의 물을 취소할 수 있는지에 대한 정보를 가지는 보조 네트워크를 \(f\)에 대한 잔여 네트워크(residual network) \(G_f = (V, E_f), c_f\)라고 정의하였습니다. 이 네트워크는 아직 가득 차지 않아서 해당 간선으로 얼마큼 더 흘러 넣을 수 있는지 알려주는 전진 간선(forward edge)과 어떤 간선에 물이 어느 정도 있어서 이를 취소할 수 있다는 것을 알려주는 후진 간선(backward edge)로 이루어져 있습니다. 각각의 간선의 성질에 맞게 용량 \(c_f\)도 알맞게 정의되었습니다.
\(G\)에 루프, 평행 간선, 역평행 간선이 존재하지 않는다는 가정 덕분에 우리는 다음과 같은 요긴한 정리를 얻을 수 있었습니다.
정리 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 \) 중 정확히 하나가 있어야 한다.
이를 활용하면 다음을 증명할 수 있으며, 이는 이번 글의 주요 목표인 최대 흐름 최소 절단 정리를 증명하는데 중요하게 사용됩니다.
정리 3. 가득 찬 간선과 빈 간선
어떤 흐름 네트워크 \(G = (V, E), c\) 상에서 흐르는 흐름 \(f\)가 주어졌을 때, 임의의 \( \langle u, v \rangle \in E \)에 대해 만약 \( \langle u, v \rangle \notin E_f \)라면 \( f(u, v) = c(u, v) \)이다. 반대로 \( \langle v, u \rangle \notin E_f \)라면 \( f(u, v) = 0 \)이다.
[증명] 정리 2를 통해, \( \langle u, v \rangle \in E \)에 대해, \(G_f\)에는 \( \langle u, v \rangle \)가 전진 간선으로, \( \langle v, u \rangle \)가 후진 간선으로 들어갈 수 있고, 반대로 \( G_f \)의 두 간선은 반드시 \( \langle u, v \rangle \)에 의해서만 결정됩니다. 만약 전진 간선이 없다면 이는 \(E_f\)의 정의에 의해 \( f(u, v) = c(u, v) \)인 상황이고, 후진 간선이 없다면 \( f(u, v) = 0 \)인 상황입니다. □
절단(Cut)과 순 흐름(Net Flow)
최대 흐름 최소 절단 정리를 보이려면 일단 '절단'이라는 게 무엇인지부터 알아야 합니다. 필요한 개념을 하나씩 정의해 보도록 하겠습니다. 가장 중요한 개념은 제목에서도 알 수 있다시피 바로 절단(cut)입니다. 이름에서 어느 정도 유추할 수 있듯이 절단은 네트워크를 정확히 두 개로 쪼개는 것을 의미합니다. 문제의 입력으로 시점 \(s\)와 종점 \(t\)가 들어오기 때문에, 우리는 둘로 쪼개는 여러 방법 중에서 한 쪽에는 \(s\)가 속하고 다른 쪽에는 \(t\)가 속하도록 하는 절단만을 고려할 것입니다. 이를 밝혀서 적기 위해 \(s\)-\(t\) 절단(\(s\)-\(t\) cut)이라고 부르기도 하지만, 이 글에서는 그렇지 않은 절단을 고려하지 않아서 그냥 절단이 해당 절단을 가리킨다고 하겠습니다.
엄밀하게 정의하도록 하죠. 어떤 정점의 부분집합 \(S \subset V\)에 대해 \(s \in S\)이고 \(t \in V \setminus S\)일 때, \( (S, V \setminus S) \)를 절단이라고 부릅니다. 입력으로 주어지는 흐름 네트워크의 방향 그래프 \(G = (V,E)\)에 대해 어떤 절단 \((S, V \setminus S)\)가 주어졌을 때, \(S\)의 한 정점에서 시작하여 \(V \setminus S\)의 한 정점으로 향하는 간선들의 집합을 \( \delta^+(S) \subseteq E \), 반대로 \( V \setminus S \)의 한 정점에서 \(S\)의 한 정점으로 들어오는 간선들의 집합을 \( \delta^-(S) \subseteq E \)라고 쓰겠습니다.
비슷하게, 흐름 \(f\)에 의해 잔여 네트워크 \( G_f = (V, E_f) \)가 주어졌을 때에도 절단 \( (S, V \setminus S) \)에 대해 \(S\)에서 \(V \setminus S\)로 나가는 간선들의 집합을 \( \delta^+_f(S) \subseteq E_f \), 반대로 들어오는 간선들은 \( \delta^-_f(S) \subseteq E_f \)로 정의하겠습니다.
어떤 절단 \( (S, V \setminus S) \)가 주어졌을 때, 과연 \(S\)에서 \(V \setminus S\)로 얼마큼의 물을 흘려줄 수 있을까요? 우리는 \(s\)에서 \(t\)로 향하는 흐름만 생각할 것이므로 \(\delta^+(S)\)의 간선을 최대로 사용하면 될 것입니다. 반대로 \( \delta^-(S) \)의 간선은 사용했다가는 손해만 보게 되겠죠. 다시 말해, 최대
\[ c(S) = \sum_{e \in \delta^+(S)} c(e) \]
만큼 \(s\)에서 \(t\)로 흘려줄 수 있을 것입니다. 이를 절단 \( (S, V \setminus S) \)의 절단 용량(cut capacity)이라고 부릅니다. 기호로는 \(c(S)\)로 쓰도록 하겠습니다.
그러면 어떤 흐름 \(f\)가 주어졌을 때, 어떤 절단 \( (S, V \setminus S) \)를 기준으로는 얼마큼이 흘러 나가고 흘러 들어오고 있을까요? 네, \( \delta^+(S)\)의 간선을 통해 흘러 나갈 것이고, \(\delta^-(S)\)의 간선을 사용하여 흘러 들어올 겁니다. 따라서 \(S\)에서 \(V \setminus S\)로 도합
\[ f(S) = \sum_{e \in \delta^+(S)} f(e) - \sum_{e \in \delta^-(S)} f(e)\]
만큼의 양이 나가고 있다는 뜻이죠. 만약 이 값이 음수라면 \(S\)로 그 절댓값만큼 들어오고 있다는 뜻이 됩니다. 이를 우리는 흐름 \(f\)의 절단 \( (S, V \setminus S) \)에 대한 순 흐름양(net flow value)이라고 하고, 이 글에서는 이를 \(f(S)\)로 표기하도록 하겠습니다.
절단 용량과 순 흐름양의 개념을 통해 바로 유추할 수 있는 사실은 순 흐름양이 절단 용량을 넘지는 못할 거라는 점입니다.
정리 4. 순 흐름양과 절단 용량의 관계
어떤 절단 \( (S, V \setminus S) \)와 임의의 흐름 \(f\)에 대해서 \( f(S) \leq c(S) \)를 항상 만족한다.
[증명] 증명은 간단합니다. 흐름의 용량 제약에 의해 임의의 간선 \(e \in E\)에 대해 \(0 \leq f(e) \leq c(e)\)를 항상 만족합니다. 따라서, \[ f(S) = \sum_{e \in \delta^+(S)} f(e) - \sum_{e \in \delta^-(S)} f(e) \leq \sum_{e \in \delta^+(S)} c(e) - \sum_{e \in \delta^-(S)} 0 = c(S) \]가 성립합니다. □
다음 정리는 어떤 절단의 순 흐름양이든 그 값은 원래 흐름의 양과 항상 동일하다는 것입니다. 먼저 직관적인 설명을 해보자면, 흐름 네트워크에서 물은 항상 시점 \(s\)에서만 생성되고 \(t\)에서 소비됩니다. 따라서 네트워크를 어떻게 절단하더라도 그 절단면을 따라 나가고 들어오는 순 흐름양은 시점에서 생성되는 양과 동일하다는 것이죠. 엄밀한 증명은 다음과 같습니다.
정리 5. 순 흐름양의 동일성
임의의 흐름 \(f\)에 대해, 어떤 절단 \((S, V \setminus S)\)이든 항상 \( f(S) = |f| \)를 만족한다.
[증명] 이는 흐름 보존 제약을 활용하여 증명할 수 있습니다. \(S\)의 각 정점에서 흘러 나가는 양에서 흘러 들어오는 양을 제한 값을 모두 더해 보겠습니다. 다시 말해,
\[ \sum_{v \in S} \left[ \sum_{e \text{ out of } v} f(e) - \sum_{e \text{ into } v} f(e) \right] \tag{1} \]
를 고려하겠습니다. 쉽게 알 수 있는 것은 흐름 보존 제약에 의해서 \(s\)를 제외한 나머지 정점들은 대괄호 내부가 \(0\)이 되어 위 식이 정확히
\[ \sum_{e \text{ out of } s} f(e) - \sum_{e \text{ into } s} f(e) = |f| \]
와 동일하다는 것을 알 수 있습니다. 위 식의 등호는 흐름양의 정의에서 그대로 왔습니다.
따라서 식 1이 \(f(S)\)와 동일하다는 것을 보이면 증명이 모두 완성됩니다. 이 식을 간선의 입장에서 생각해 보겠습니다. 어떤 간선 \( \langle u, v \rangle \in E\)에 대해서 \(u, v \in S\)라면, \(u\)에서 \(f(u, v)\)의 값이 더해지나 \(v\)에 의해 \(f(u, v)\)의 값이 빼지게 됩니다. 반대로 \( u \)만 \(S\)에 있다면 \(f(u, v)\)만 식에 남아 있을 것이고, \( v \)만 있는 경우에는 \( -f(u, v) \)의 부분만 식에 남아 있을 겁니다. 따라서, 식 1을 다시 적으면 정확히
\[ \sum_{e \in \delta^+(S)} f(e) - \sum_{e \in \delta^-(S)} f(e) = f(S) \]
가 됩니다. 등호는 순 흐름양의 정의로부터 얻을 수 있습니다. □
최대 흐름 최소 절단 정리(Max-Flow Min-Cut Theorem)
위 절에서 우리는 절단과 순 흐름양에 대해서 정의하고 그것들이 가지는 간단한 성질들을 몇 가지 정리하였습니다. 특히 정리 4와 5를 통해 우리는 어떤 흐름도 절단 용량의 최솟값보다 많은 양을 흘릴 수는 없다는 사실을 알 수 있습니다. 따라서 어떤 네트워크에서든 절단 용량은 흐름양의 상한을 이룹니다. 그러므로, 만약 우리가 용량이 가장 작은 절단을 찾는다면, 이는 흐름양의 최댓값을 구하는 데 큰 도움이 될 것입니다.
정리 6. 순 흐름양과 절단 용량의 약한 쌍대성(weak duality)
흐름 네트워크의 절단 중 가장 용량이 작은 것을 \( (S^\star, V \setminus S^\star) \)라고 하자. 그러면 임의의 흐름 \(f\)에 대해, \( |f| \leq c(S^\star) \)를 항상 만족한다.
또한, 어떤 흐름 \(f\)와 어떤 절단 \( (S, V \setminus S) \)가 \(|f| = c(S)\)를 만족한다면 \(f\)는 최대 흐름이고 \( (S, V \setminus S) \)는 최소 절단이다.
[증명] 첫 번째 명제는 정리 4와 5를 적용하면 \( |f| = f(S^\star) \leq c(S^\star) \)가 되어 쉽게 이끌어낼 수 있습니다.
어떤 최대 흐름 \(f^\star\)에 대해서, 만약 두 번째 명제의 조건과 같은 \(f\)와 \( (S, V \setminus S) \)가 주어진다면,
\[ c(S) = |f| \leq |f^\star| \leq c(S^\star) \leq c(S) \]
가 되어 모든 부등식이 등식이 됩니다. 따라서 \(f\)와 \( (S, V \setminus S) \)가 각각 최대 흐름, 최소 절단이 되겠습니다. □
정리 6을 통해 알 수 있는 것은 만약 우리가 어떤 흐름 \(f\)와 절단 \( (S, V \setminus S) \)를 갖고 있는데 그 흐름의 양 \(|f|\)와 해당 절단의 용량 \(c(S)\)가 동일하다면 각각이 바로 최대 흐름, 최소 절단이 된다는 사실입니다. 그리고 놀랍게도, \(G_f\) 위에서 \(s\)에서 \(t\)로 가는 경로가 존재하지 않는다면 그러한 \(S\)가 항상 존재하게 됩니다. 따라서 정리 6과 함께 \(f\)는 최대 흐름이 되게 됩니다. 이는 서두에서 던진 '역도 성립하는가?'에 대한 답이 됩니다.
정리 7. 잔여 네트워크 상 종점이 도달 불가능할 때의 성질
어떤 흐름 네트워크 \(G = (V, E), c\) 위의 시점 \(s\)에서 종점 \(t\)로 흐르는 어떤 흐름 \(f\)에 대해 \(f\)의 잔여 네트워크 \(G_f = (V, E_f), c_f\) 위에서 \(t\)가 \(s\)로부터 도달할 수 없다고 하자. 이때, \(G_f\) 위에서 \(s\)에서 도달할 수 있는 모든 정점을 \(S \subset V \)라고 하면, \( |f| = c(S) \)를 만족한다.
[증명] \(S\)는 \( s \)에서 도달할 수 있는 모든 정점이므로 \(G_f\) 위에서 \(S\)에서 \( V \setminus S \)로 나가는 간선은 없습니다. 따라서 \( V \setminus S \)에서 \(S\)로 들어오는 간선만 고려해주면 됩니다.
어떤 간선 \( \langle v, u \rangle \in \delta^-_f(S) \)에 대해 (단, \( u \in S, v \notin S \)), 만약 이 간선이 후진 간선이라면 정리 2에 의해 원래 네트워크에는 \( \langle u, v \rangle \in E \)가 존재했을 것입니다. 이는 \( \delta^+(S) \)에 속한 간선이죠. 하지만, 이 간선의 전진 간선에 해당하는 \( \langle u, v \rangle \)이 \(G_f\)에 없는 것으로 보아, 정리 3에 의해 \( f(u, v) = c(u, v) \)임을 알 수 있습니다.
반대로 \( \langle v, u \rangle\)가 전진 간선이라면, 원래 네트워크에는 정리 2에 의해 \( \langle v, u \rangle \in E \)가 있었을 겁니다. 하지만 이것의 후진 간선에 해당하는 \( \langle u, v \rangle \)가 \(G_f\)에 없으므로 똑같이 정리 3을 통해 \( f(v, u) = 0 \)이라는 사실을 알 수 있습니다.
따라서 \( \delta^-_f(S) \)의 후진 간선은 모두 \( \delta^+(S) \)의 간선에 대응하며 이들은 모두 용량 가득 흘러가는 상태이고, 반대로 전진 간선은 모두 \( \delta^-(S) \)에 대응하면서 흐름이 전혀 없는 상태입니다. 따라서,
\[ |f| = f(S) = \sum_{e \in \delta^+(S)} f(e) - \sum_{e \in \delta^-(S)} f(e) = \sum_{e \in \delta^+(S)} c(e) - \sum_{e \in \delta^-(S)} 0 = c(S) \]
를 만족하게 됩니다. □
이제 최대 흐름 최소 절단 정리를 증명할 수 있습니다.
정리 8. 최대 흐름 최소 절단 정리
어떤 흐름 네트워크든 최대 흐름의 양은 항상 최소 절단의 용량과 항상 동일하다.
[증명] 정리 1에 의해 어떤 최대 흐름의 잔여 네트워크 위에서는 \(t\)가 \(s\)로부터 도달할 수 없습니다. 이는 정확히 정리 7의 조건을 만족하며, 따라서 정리 7에서 찾은 \(S\)의 용량은 최대 흐름의 양과 동일합니다. 정리 6에 의해 \(S\)도 자연스럽게 최소 절단이 됩니다. □
마치며
이것으로 유명한 최대 흐름 최소 절단 정리의 증명을 모두 마치겠습니다. 위에서 다룬 내용을 간단히 정리해 보자면, 다음과 같습니다.
- 절단 \( (S, V \setminus S) \)는 정점을 둘로 쪼갠 것으로 그것의 용량은 \(S\)에서 \( V \setminus S \)로 향하는 간선들의 용량의 합으로 정의됩니다. 어떤 흐름이 주어졌을 때 이 절단에서의 순 흐름양은 \(S\)에서 \(V \setminus S\)로 흘러 나가는 흐름의 양에서 \( V \setminus S \) 에서 \(S\)로 흘러 들어오는 흐름의 양을 뺀 것으로 정의됩니다.
- 절단 용량은 흐름양의 상한을 이루며 최대 흐름 최소 절단 정리에 의해 최대 흐름양과 최소 절단 용량의 값은 어떤 네트워크에서든지 동일합니다.
지금까지 최대 흐름 문제에서 최대 흐름이 갖는 여러 성질들을 알아 보았으며, 유명한 최대 흐름 최소 절단 정리도 증명하였습니다. 다음부터는 실지로 이를 활용하여 네트워크에서 최대 흐름을 찾아 보도록 해보죠.
혹시 잘못된 점이 있거나 궁금하신 점이 있으시면 제게 알려 주시기 바랍니다. 고맙습니다. :)
참조
[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 |
| 최대 흐름 문제 이해하기 (Maximum Flow Problem) (13) | 2020.08.29 |
