1편 에서 이어집니다.

Min-CutPermalink

그래프에서 절단(Cut)의 정의는 다음과 같다.

그래프 G=(V,E)G=(V, E)에 대해 e∈Ee \in E 인 간선을 한 개 이상 끊어서 V1⊂VV_1 \subset V과 V2⊂VV_2 \subset V 두 정점 집합으로 나누며 V1∪V2=V & V1∩V2=∅⟺V2=V∖V1V_1 \cup V_2=V ~\&~ V_1 \cap V_2 = \varnothing \Longleftrightarrow V_2=V \setminus V_1

여기서 네트워크 그래프의 관점에서 보자면 source∈V1source \in V_1 이고 sink∈V2sink \in V_2 라고 할 수 있다.

네트워크 그래프에서 최소 컷(Minimum Cut)문제는 간선들을 절단해서 그래프를 정확히 두 개로 나누면서 간선을 자를 때마다 그 간선의 용량만큼 비용이 든다고 할 때, 그 최소 절단 용량합을 구하는 문제이다.

Min-Cut Max-Flow TheoremPermalink

결론적으로 최소 컷의 값은 최대 유량과 동치이다.

그래서 최소컷 문제도 그냥 Edmonds-Karp 알고리즘을 써서 최대 유량을 구하면 그것이 정답이다.

엄밀한 증명에 관련된 내용은 이 글을 추천한다.

0. NotationPermalink

  • 절단 용량 c(S)c(S): 유량 그래프에서 임의의 절단 SS를 이용해 그래프가 V1,V2V_1, V_2 로 나뉠 때, V1V_1 에서 V2V_2 로 이어진 간선의 용량의 합
    • 이것을 최소화 하는 것이 Min-Cut 문제이다.
  • 순 흐름양 f(S)f(S): 유량 그래프에서 임의의 절단 SS를 이용해 그래프가 V1,V2V_1, V_2로 나뉠 때, V1V2→\overrightarrow {V_1V_2} 혹은 V1V2←\overleftarrow {V_1V_2} 로 이어진 절단된 간선들에 흐르고 있는 유량의 총량
    • V1V2→\overrightarrow {V_1V_2} 방향은 이 값이 양수 (+)(+) 이고, V1V2←\overleftarrow {V_1V_2} 방향은 이 값이 음수 (−)(-) 이다.

1. 순 흐름양은 절단 용량 이하이다.Permalink

f(S)≤c(S) f(S) \le c(S)

어떤 간선에서 유량은 용량보다 많이 흐르고 있을 수 없기 때문에 쉽게 보여진다.

V1V2←\overleftarrow {V_1V_2} 는 음수로 더해지기 때문에 V1V2→\overrightarrow {V_1V_2} 간선들의 총 용량이 V1V2→\overrightarrow {V_1V_2} 간선들의 총 유량보다 작을 순 없다.

즉, f(S)f(S)가 c(S)c(S)보다 커질 순 없다.

2. 모든 절단의 순 흐름양은 동일하다.Permalink

source→sinksource \to sink 로 가는 유량의 흐름에서 어떤 절단을 취하든 항상 절단에 포함된 간선에서 V1V2→\overrightarrow {V_1V_2} 로 흐르고 있는 유량의 합은 동일하다는 의미이다.

TheoremPermalink

정리 1에 의해 f(S)≤c(S)f(S) \le c(S) 이므로 존재하는 SS중, c(S)c(S) 가 가장 작은 것을 찾는다면 그건 결국 f(S)f(S) 의 최대값을 찾는데 도움이 된다.

SS 중, 절단 용량 c(S)c(S)가 가장 작은 절단을 S∗S^* 라 하자. 역시나 유량 ∣f∣\lvert f \rvert 에 대해 ∣f∣≤c(S∗)\lvert f \rvert \le c(S^*) 이다.

어떤 유량이 ∣f∣=c(S)\lvert f \rvert = c(S) 라고 한다면, 그 때의 흐름양 ∣f∣\lvert f \rvert 가 최대 흐름(유량)이 되고, 그 때의 절단 SS가 S∗S^* 이다.

위 성질을 볼 때, 결국 S∗S^* 가 존재를 하면 최대 유량도 찾고 할 수 있는데, S∗S^* 는 항상 존재한다는 보장이 없다는 것이 문제이다.

하지만, S∗S^* 가 항상 존재하는 경우가 있는데, 그건 바로 source→sinksource \to sink 의 증가 경로 PP가 존재하지 않는 상황이다.

따라서 source→sinksource \to sink의 증가 경로 PP가 존재하지 않는다면 S∗S^*가 존재하여 그 때의 절단 용량이 곧 최대 유량이다.

증명Permalink

source→sinksource \to sink 로 증가 경로가 없을 때, sourcesource 로부터 잔여 네트워크를 이용해 도달할 수 있는 정점 집합을 S⊂VS \subset V 라고 하자.

S→V∖SS \to V \setminus S 로 나가는 간선은 없다. 왜냐면 여기에 여유용량이 있는 간선이 있다는 것은 SS의 정의에 위반되기 때문이다.

따라서 V∖S→SV \setminus S \to S 로 들어오는 간선만 고려하자. 그걸 vu→  (v∈V∖S, u∈S)\overrightarrow {vu} ~~ (v \in V \setminus S,~ u \in S) 라고 하자.

  1. vu→\overrightarrow {vu} 이 역간선이라면

원래 uv→\overrightarrow {uv} 는 그래프에 존재하는 정방향 간선이고 유량이 흐르고 있다는 것이 된다.

SS의 정의에 의해 uv→\overrightarrow {uv} 는 여유 용량이 00이여야 한다. ⇒c(u,v)=f(u,v)\Rightarrow c(u, v)=f(u, v)

  1. vu→\overrightarrow {vu} 이 정방향 간선이라면

원래 네트워크 그래프에는 vu→\overrightarrow {vu} 가 있을 것이고 uv→\overrightarrow {uv} 는 S→V∖SS \to V \setminus S 로 가는 간선인데 이 간선은 포함되지 않았으므로 vu→\overrightarrow {vu} 의 유량은 00이다.

결론적으로 V∖S→SV \setminus S \to S 로의 의 역간선들은 모두 S→V∖SS \to V \setminus S 의 정방향 간선들에 대응되면서 모두 유량이 꽉차있는 상태이고, V∖S→SV \setminus S \to S 로의 의 정방향 간선들은 모두 S→V∖SS \to V \setminus S 의 역간선들에 대응 되면서 유량이 00 인 상태이므로

∣f∣=f(S)=∑e∈(S→V∖S)f(e)−∑e∈(V∖S→S)f(e)=∑e∈(S→V∖S)f(e)−0=c(S) \lvert f \rvert = f(S)=\displaystyle \sum_{e \in (S \to V \setminus S)}f(e)-\sum_{e \in(V \setminus S \to S)}f(e)=\\ \displaystyle \sum_{e \in (S \to V \setminus S)}f(e)-0=c(S)

이다. ∣f∣=f(S)\lvert f \rvert=f(S) 는 정리 2에 의해 보여지고, source→sinksource \to sink 로의 증가 경로가 없다면 이것이 결국 ∑e∈(S→V∖S)f(e)\displaystyle \sum_{e \in (S \to V \setminus S)}f(e) 라는 것이 보여졌다.

그리고 이 간선들은 모두 여유용량 없이 f(u,v)=c(u,v)f(u,v)=c(u,v) 라는 것을 보였기 때문에 결국 절단 용량 c(S)c(S) 의 정의와 동치가 되기 때문에

증가 경로가 없는 상태의 네트워크 그래프에서 유량은 어떤 절단 SS의 절단 용량 c(S)c(S) 와 동일한 절단 SS이 항상 존재하고, f(S)≤c(S)f(S) \le c(S) 이기 때문에 위에서 언급한대로 이 때가 최대 유량임이 보여진다. □\square

참고 1

Comments

You may also enjoy