최소 컷 - Stoer-Wagner 알고리즘¶
문제 설명¶
정점 $n$개와 간선 $m$개를 가진 무방향 가중치 그래프 $G$가 주어집니다. 컷 $C$는 정점들의 공집합이 아닌 진부분집합입니다(사실상 컷은 정점들을 $C$에 속하는 정점들과 나머지 모든 정점들이라는, 공집합이 아닌 두 집합으로 분할한 것입니다). 컷의 가중치는 컷을 가로지르는 간선들, 즉 끝점 중 정확히 하나만 $C$에 속하는 간선들의 가중치 합입니다:
여기서 $E$는 그래프 $G$의 모든 간선의 집합을 나타내고, $c(v,u)$는 간선 $(v,u)$의 가중치입니다.
과제는 가중치가 최소인 컷을 찾는 것입니다.
이 문제는 때때로 "전역 최소 컷"이라고도 불립니다. 이는 소스 정점과 싱크 정점이 주어지고, 싱크는 포함하되 소스는 포함하지 않는 최소 컷 $C$를 찾아야 하는 문제와 대비되는 명칭입니다. 전역 최소 컷은 가능한 모든 소스-싱크 쌍에 대한 최소 비용 컷들 중 최솟값과 같습니다.
이 문제는 최대 흐름 알고리즘으로도 풀 수 있지만(가능한 모든 소스-싱크 쌍에 대해 $O(n^2)$번 실행하면 됩니다), 아래에서는 1994년에 Mechthild Stoer와 Frank Wagner가 제안한 훨씬 더 간단하고 빠른 알고리즘을 설명합니다.
일반적으로 루프와 다중 간선이 허용되지만, 루프는 명백히 결과에 아무런 영향도 주지 않으며, 다중 간선은 항상 그 가중치를 합친 하나의 간선으로 대체할 수 있습니다. 따라서 단순화를 위해 입력 그래프에 루프나 다중 간선이 없다고 가정하겠습니다.
알고리즘 설명¶
알고리즘의 기본 아이디어는 매우 간단합니다. 다음 과정을 반복합니다: 어떤 정점 쌍 $s$와 $t$ 사이의 최소 컷을 찾은 다음, 이 두 정점을 하나로 병합합니다(두 정점의 인접 리스트를 연결합니다). 결국 $n-1$번의 반복 후에 그래프는 하나의 정점으로 압축되고 과정이 종료됩니다. 그 후, 답은 찾아낸 $n-1$개의 컷 전체 중 최솟값입니다. 실제로 매 $i$번째 단계에서 정점 $s_i$와 $t_i$ 사이에서 찾은 최소 컷 $C_i$는 구하려는 전역 최소 컷이거나, 반대로 $s_i$와 $t_i$를 서로 다른 집합에 넣는 것이 불리한 경우이므로, 이 두 정점을 하나로 병합해도 아무것도 나빠지지 않습니다.
이렇게 하여 문제는 다음과 같이 축소되었습니다: 주어진 그래프에서 정점 $s$와 $t$로 이루어진 임의의 어떤 정점 쌍 사이의 최소 컷을 찾는 것입니다. 이 문제를 풀기 위해, 마찬가지로 반복적인 다음 과정이 제안되었습니다. 처음에 임의의 정점 하나만을 포함하는 정점 집합 $A$를 도입합니다. 매 단계마다 집합 $A$와 가장 강하게 연결된 정점, 즉 다음 값이 최대가 되는 정점 $v \not\in A$를 찾습니다:
(즉, 한쪽 끝점이 $v$이고 다른 쪽 끝점이 $A$에 속하는 간선들의 가중치 합이 최대가 되는 정점입니다).
이 과정 역시 $n-1$번의 반복 후, 모든 정점이 집합 $A$로 옮겨지면 종료됩니다(참고로 이 과정은 Prim 알고리즘과 매우 유사합니다). 그러면 Stoer-Wagner 정리에 따르면, $A$에 마지막으로 추가된 두 정점을 $s$와 $t$라고 할 때, 정점 $s$와 $t$ 사이의 최소 컷은 단일 정점 $t$로 이루어집니다. 이 정리의 증명은 다음 절에서 제시하겠습니다(흔히 그렇듯이, 증명 자체는 알고리즘을 이해하는 데 전혀 도움이 되지 않습니다).
따라서 Stoer-Wagner 알고리즘의 전체 구조는 다음과 같습니다. 알고리즘은 $n-1$개의 페이즈로 구성됩니다. 각 페이즈에서 집합 $A$는 처음에 어떤 정점 하나를 포함하도록 설정되고, 정점들의 초기 가중치 $w(v,A)$가 계산됩니다. 그다음 $n-1$번의 반복이 이어지며, 각 반복에서는 $w(v,A)$ 값이 가장 큰 정점 $u$를 선택하여 집합 $A$에 추가한 후 나머지 정점들의 $w$ 값을 다시 계산합니다(이를 위해서는 당연히 선택된 정점 $u$의 인접 리스트에 있는 모든 간선을 순회해야 합니다). 모든 반복을 수행한 후, 마지막으로 추가된 두 정점을 $s$와 $t$에 기록하며, 값 $w(t,A \setminus t)$를 $s$와 $t$ 사이에서 찾은 최소 컷의 비용으로 취할 수 있습니다. 그다음 찾은 최소 컷을 현재 답과 비교하여 더 작으면 답을 갱신하고, 다음 페이즈로 진행합니다.
복잡한 자료 구조를 사용하지 않는다면, 가장 중요한 부분은 $w$ 값이 가장 큰 정점을 찾는 것입니다. 이를 $O(n)$에 수행한다면, 각각 $n-1$번의 반복으로 이루어진 단계가 $n-1$개 있으므로 알고리즘의 전체 복잡도는 $O(n^3)$이 됩니다.
$w$ 값이 가장 큰 정점을 찾는 데 피보나치 힙(키 값을 분할 상환 $O(1)$에 증가시키고 최댓값을 분할 상환 $O(\log n)$에 추출할 수 있습니다)을 사용하면, 한 단계에서 집합 $A$와 관련된 모든 연산이 $O(m + n \log n)$에 수행됩니다. 이 경우 알고리즘의 전체 복잡도는 $O(n m + n^2 \log n)$입니다.
Stoer-Wagner 정리의 증명¶
이 정리의 내용을 다시 떠올려 봅시다. 모든 정점을 하나씩 집합 $A$에 추가하되 매번 이 집합과 가장 강하게 연결된 정점을 추가한다고 할 때, 끝에서 두 번째로 추가된 정점을 $s$, 마지막으로 추가된 정점을 $t$라고 합시다. 그러면 최소 $s$-$t$ 컷은 단일 정점 $t$로 이루어집니다.
이를 증명하기 위해 임의의 $s$-$t$ 컷 $C$를 생각하고, 그 가중치가 단일 정점 $t$로 이루어진 컷의 가중치보다 작을 수 없음을 보이겠습니다:
이를 위해 다음 사실을 증명합니다. 정점 $v$를 추가하기 직전의 집합 $A$의 상태를 $A_v$라고 합시다. 컷 $C$에 의해 유도되는 집합 $A_v \cup \{v\}$의 컷을 $C_v$라고 합시다(간단히 말해, $C_v$는 이 두 정점 집합의 교집합과 같습니다). 또한 정점 $v$와 그 직전에 추가된 정점이 컷 $C$의 서로 다른 부분에 속하면, 정점 $v$를 (컷 $C$에 대해) 활성 정점이라고 부릅니다. 그러면 임의의 활성 정점 $v$에 대해 다음 부등식이 성립한다고 주장합니다:
특히 $t$는 활성 정점이며(그 직전에 추가된 정점이 $s$였으므로), $v = t$일 때 이 부등식은 정리의 내용이 됩니다:
따라서 이 부등식을 수학적 귀납법으로 증명하겠습니다.
첫 번째 활성 정점 $v$에 대해서는 부등식이 성립합니다(나아가 등식이 됩니다). $A_v$의 모든 정점이 컷의 한쪽 부분에 속하고 $v$는 다른 쪽에 속하기 때문입니다.
이제 어떤 정점 $v$까지의 모든 활성 정점에 대해 이 부등식이 성립한다고 가정하고, 다음 활성 정점 $u$에 대해 이를 증명해 봅시다. 이를 위해 좌변을 변형합니다:
먼저 다음에 주목하십시오:
이는 집합 $A$가 $A_v$와 같았을 때 추가된 정점이 $u$가 아니라 바로 $v$였다는 사실, 즉 $v$의 $w$ 값이 가장 컸다는 사실로부터 따라옵니다.
또한 귀납법의 가설에 의해 $w(v,A_v) \le w(C_v)$이므로, 다음을 얻습니다.
이로부터 다음을 얻습니다:
이제 정점 $u$와 $A_u \setminus A_v$의 모든 정점은 컷 $C$의 서로 다른 부분에 있으므로, 값 $w(u,A_u \setminus A_v)$는 $w(C_u)$에는 포함되지만 $w(C_v)$에는 아직 포함되지 않은 간선들의 가중치 합을 나타냅니다. 이로부터 다음을 얻습니다:
이로써 원하는 결과를 얻었습니다.
관계식 $w(v,A_v) \le w(C_v)$를 증명하였으며, 앞서 언급했듯이 정리 전체가 이로부터 따라옵니다.
구현¶
가장 간단하고 명확한 구현($O(n^3)$ 복잡도)에서는 그래프를 인접 행렬로 표현합니다. 답은 변수 best_cost와 best_cut(최소 컷의 비용과 그 컷에 포함된 정점들)에 저장됩니다.
각 정점에 대해 배열 exist는 그 정점이 아직 존재하는지, 아니면 다른 정점과 병합되었는지를 저장합니다. 리스트 v[i]는 압축된 각 정점 $i$에 대해 이 정점 $i$로 압축된 원래 정점들의 번호를 저장합니다.
이 알고리즘은 $n-1$개의 단계(변수 ph에 대한 루프)로 구성됩니다. 각 단계에서 처음에는 모든 정점이 집합 $A$ 바깥에 있으므로 배열 in_a는 0으로 채워지고, 모든 정점의 연결도 $w$는 0입니다. $n-\mathrm{ph}$번의 반복 각각에서 $w$ 값이 가장 큰 정점 sel을 찾습니다. 이번이 마지막 반복이라면 필요한 경우 답을 갱신하고, 끝에서 두 번째로 선택된 정점 prev와 마지막으로 선택된 정점 sel을 하나로 병합합니다. 이번 반복이 마지막이 아니라면 sel을 집합 $A$에 추가한 뒤, 남은 모든 정점의 가중치를 다시 계산합니다.
이 알고리즘은 동작하는 동안 그래프 g를 "망가뜨린다"는 점에 유의하십시오. 따라서 나중에도 그래프가 필요하다면 함수를 호출하기 전에 사본을 저장해 두어야 합니다.
const int MAXN = 500;
int n;
long long g[MAXN][MAXN];
long long best_cost = (1LL << 62);
vector<int> best_cut;
void mincut() {
vector<int> v[MAXN];
for (int i = 0; i < n; ++i)
v[i].assign(1, i);
long long w[MAXN];
bool exist[MAXN], in_a[MAXN];
memset(exist, true, sizeof exist);
for (int ph = 0; ph < n - 1; ++ph) {
memset(in_a, false, sizeof in_a);
memset(w, 0, sizeof w);
for (int it = 0, prev; it < n - ph; ++it) {
int sel = -1;
for (int i = 0; i < n; ++i)
if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel]))
sel = i;
if (it == n - ph - 1) {
if (w[sel] < best_cost) {
best_cost = w[sel];
best_cut = v[sel];
}
v[prev].insert(v[prev].end(), v[sel].begin(), v[sel].end());
for (int i = 0; i < n; ++i)
g[prev][i] = g[i][prev] += g[sel][i];
exist[sel] = false;
} else {
in_a[sel] = true;
for (int i = 0; i < n; ++i)
w[i] += g[sel][i];
prev = sel;
}
}
}
}