최소 절단 그래프 모델링
서론
최소 절단(Minimum Cut) 문제는 다음과 같은 문제입니다.
유향 가중치 그래프 $G$가 있습니다. 그래프의 정점을 두 개의 집합 $S$와 $T$로 나눌 것인데, 다음 조건을 만족해야 합니다.
- 주어진 정점 $s$에 대해 $s \in S$여야 합니다.
- 주어진 정점 $t$에 대해 $t \in T$여야 합니다.
- 절단된 간선의 가중치 합을 최소화 해야합니다.
- 모든 간선 $u \xrightarrow{w} v$에 대해 $u \in S$이고 $v \in T$인 경우, 해당 간선은 절단되었다고 합니다.
이 문제에 대한 답을 $s-t$ 최소 절단이라고 합니다.
최대유랑 - 최소절단 정리
이 문제는 최대 유량(Maximum Flow)를 이용하여 해결할 수 있습니다. 이를 위해서는 다음과 같은 정리가 필요합니다.
Max-flow min-cut theorem (Ford-Fulkerson, 1962)
$G$에서의 $s-t$ 최대 유량과 $s-t$ 최소 절단은 같다.
증명
- $s-t$ 최소 절단은 $s-t$ 최대 유량 이상이다.
- 어떤 두 집합 $S$와 $T$가 최소 절단의 조건을 만족한다고 합시다. 이 때, $S$에서 나가는 간선 가중치의 합이 $s-t$ 최소 절단입니다. $s$에서 $t$로 가는 모든 유량은 $S$와 $T$ 사이를 지나기 때문에, 최대 유량은 최소 절단을 넘을 수 없습니다.
- $s-t$ 최대 유량은 $s-t$ 최소 절단 이상이다.
- $G$ 그래프에서 최대 유량을 흘리게 되면, 더 이상 Augment할 수 있는 경로가 존재하지 않습니다. 이 때, 남은 간선과 Back edge들을 이용해서 $s$에서 도달 가능한 정점의 집합을 $S$라고 합시다. 앞서 설명한 대로 $S$에서 나가는 간선 가중치의 합은 최대 유량과 같기 때문에, $s-t$ 최대 유량에 해당하는 $s-t$ 절단이 존재합니다.
그렇기 때문에 최소 절단 문제를 해결할 때는 최대 유량 문제로 바꿔서 해결하면 되고, 실제 집합 $S$와 $T$를 찾는 것도 위 방법을 사용하면 되기 때문에 어렵지 않습니다.
최소 절단 모델링
문제를 풀다 보면 $N$개의 boolean 변수 $v_1, v_2, \cdots, v_N$을 정해서 비용을 최소화하는 문제들이 있습니다. 비용이 다음 형태와 같은 경우에는 문제를 푸는 강력한 방법이 존재합니다.
- $v_i$가 true 혹은 false일 때 특정 비용이 발생합니다.
- $v_i$가 true이고 $v_j$가 false이면 비용이 발생합니다.
- $v_i \ne v_j$이면 비용이 발생합니다.
- $v_i$가 true이면 $v_j$가 true여야 합니다.
- $v_i$가 false이면 $v_j$가 false여야 합니다.
정점이 $N+2$개 있는 유향 가중치 그래프를 생각합시다. 정점에는 $1, \cdots, N$의 번호가 붙어있는 정점 $N$개와 true, false정점이 존재합니다. 이 정점을 두 개의 집합 $T$, $F$로 나눌 것입니다. $T$ 집합에 있는 정점들은 true를, $F$ 집합에 있는 정점들은 false를 할당하도록 합니다. true 정점은 항상 $T$, false 정점은 항상 $F$에 들어있도록 합니다. 이 때, 위 문제를 최소 절단으로 해결하기 위해서는 다음과 같은 규칙에 따라 간선을 그어주면 됩니다.
- $v_i$가 true일 때 비용이 발생하는 경우는 $i$에서 false로 간선을 그어줍니다. $v_i$가 false일 때 비용이 발생하는 경우는 true에서 $i$로 비용에 해당하는 가중치를 가진 간선을 그어줍니다.
- $v_i$가 $T$ 집합에 있고, $v_j$가 $F$ 집합에 있을 경우 비용이 발생하므로, $i$에서 $j$로 비용에 해당하는 가중치를 가진 간선을 그어줍니다.
- 2번 경우를 양방향으로 적용한 경우입니다. $i$와 $j$ 사이에 비용에 해당하는 가중치를 가진 간선을 각 방향으로 두 개 만들어줍니다.
- $v_i$가 true이고 $v_j$가 false일 때의 비용을 $\infty$로 생각하면 됩니다. $i$에서 $j$로 가중치 $\infty$의 간선을 그어줍니다.
- 4번 경우의 대우명제입니다. $j$에서 $i$로 가중치 $\infty$의 간선을 그어줍니다.
이후, true-false 최소 절단을 사용하면 문제를 해결할 수 있습니다.
예시
다음은 이를 이용하여 해결할 수 있는 문제입니다.
[SWERC2015 F/BOJ 11682] Landscaping
1, 3 조건을 이용한 모델링으로 문제를 해결할 수 있습니다.
다음과 같은 보조정리를 사용합니다.
${1, \cdots, N}$의 부분집합 $S$에 대해 다음 두 명제는 동치이다.
- 문제의 연산을 통해 $S$에 해당하는 돌만 파괴할 수 있다.
- $x \in S$이면 모든 $x$의 배수가 $S$에 들어있어야 한다.
증명
-
$1 \Rightarrow 2$: 수 $a$를 말해서 $x$가 파괴된 경우 모든 $x$의 배수는 $a$의 배수이므로 같이 파괴됩니다.
-
$2 \Rightarrow 1$: 집합 $S$의 각 원소 $x$에 대해 해당 연산을 진행해서 돌을 모두 파괴합시다. $y \not \in S$이면 $y$의 모든 약수가 $S$에 들어있지 않으므로, 집합 $S$에 해당하는 돌만 파괴합니다.
이제 1, 4 조건을 이용한 모델링으로 문제를 해결할 수 있습니다. 이 문제의 1 조건은 false인 경우 이득이 발생하는 경우가 있습니다. 이는 일단 이득을 답에 우선 더한 뒤, true인 경우 비용이 발생해서 삭감하는 식으로 구현을 할 수 있습니다.
[GCJ2015 R2C/BOJ 12144] 영어와 프랑스어
각 문장과 단어를 나타내는 boolean 변수를 만들어 봅시다.
문장은 영어 혹은 프랑스어이기 때문에 하나의 변수로 표현하면 되지만, 단어는 영어이면서 동시에 프랑스어일 수 있기 때문에 한 단어를 표현하는 데 두 개 이상의 변수가 필요합니다. 다음과 같이 정의합시다.
- $s_i$: $i$에 해당하는 문장이 영어인가?
- $e_j$: $j$에 해당하는 단어가 영어인가?
- $f_j$: $j$에 해당하는 단어가 프랑스어가 아닌가?
이 때, 각 상황은 다음과 같이 표현됩니다.
- 문장 $i$에 단어 $j$가 속해 있는 경우 $s_i$가 true이면 $e_j$가 true여야하고, $s_i$가 false이면 $f_j$가 false여야합니다.
- 영어이면서 동시에 프랑스어인 단어가 존재하는 경우: $e_i$가 true이면서 $f_i$가 false이면 비용이 $1$ 발생합니다.
이제 2, 4, 5 조건을 이용한 모델링으로 문제를 해결하면 됩니다.
추가 조건의 Hardness
참고로, 4, 5번 제약 조건에 더해 $v_i$와 $v_j$가 서로 달라야한다와 같은 제약조건이 있는 경우는 문제를 효율적으로 해결하는 방법을 모릅니다. 효율적인 방법이 존재하면 2SAT이 주어졌을 때 참인 clause를 최대한 많이 만드는 MAX-2SAT 문제를 풀 수 있기 때문입니다. MAX-2SAT 문제는 NP-hard 이므로 이 문제도 NP-hard가 됩니다. $v_i$와 $v_j$가 달라야 한다와 같은 경우에는, 변수를 $v_i$ 대신 “$v_i$가 아니다”와 같은 형태로 작성하여 우회하여 해결해야 합니다. (위의 영어와 프랑스어 문제가 이에 해당합니다.)