Max-Flow Min-Cut Theorem | imeimi / Algorithm DB

1s-t 유량

방향 그래프 G = (V, E), 소스 s, 싱크 t, 용량 함수 c: E → ℝ_≥0에 대해 유량 f는 각 간선 (u,v) ∈ E에 다음 조건을 만족하는 실수값을 부여한 것이다.

유량의 크기 |f| = ∑_(s,v)∈E f(s,v) − ∑_(v,s)∈E f(v,s)이다.

집합 A, B ⊆ V 사이의 순 유량 f(A, B) = ∑_{u∈A, v∈B, (u,v)∈E} f(u,v) − ∑_{u∈A, v∈B, (v,u)∈E} f(v,u)이다.

s ∈ S, t ∈ T, S ∪ T = V, S ∩ T = ∅인 (S, T)를 정점 분할이라고 한다.

컷 용량 c(S, T) = ∑_{u∈S, v∈T, (u,v)∈E} c(u,v)이다.

Max-Flow Min-Cut Theorem에 의하면 max|f| = min c(S, T)이다.

s ∈ S, t ∉ S인 임의의 S ⊆ V에 대해 |f| = f(S, V\S).

v ∈ S에서의 순 유출을 ex(v) = ∑_(v,w)∈E f(v,w) − ∑_(u,v)∈E f(u,v)로 정의한다. 흐름 보존에 의해 v ∈ S\{s}이면 ex(v) = 0이다. 따라서 ∑_v∈S ex(v) = ex(s) = |f|이다.

∑_v∈S ex(v)를 전개하면 S 내부 간선 (u,v) (u,v ∈ S)의 기여는 상쇄되므로 0이다. 따라서 S를 벗어나는 간선과 들어오는 간선만 남아 ∑_v∈S ex(v) = f(S, V\S). ■

임의의 s-t 유량 f와 s-t 컷 (S, T)에 대해 |f| ≤ c(S, T).

보조 정리 1에 의해 |f| = f(S, T).

f(S, T) = ∑_{u∈S, v∈T, (u,v)∈E} f(u,v) − ∑_{u∈S, v∈T, (v,u)∈E} f(v,u) ≤ ∑_{u∈S, v∈T, (u,v)∈E} c(u,v) − 0 = c(S, T). ■

최대 유량 f^*를 고정한다. 잔여 그래프 G_f^* = (V, E_f^*)를 다음과 같이 정의한다.

S^* = { v ∈ V : G_f^*에서 s → v 경로 존재 }로 정의한다. T^* = V\S^*로 두자.

f^*가 최대이므로 G_f^*에 s → t 경로가 없고, 따라서 t ∉ S^*이다. 즉 (S^*, T^*)는 s-t 컷이다.

∀u ∈ S^*, ∀v ∈ T^*에 대해

(u,v) ∈ E이면 잔여 용량 c(u,v) − f^*(u,v) = 0이어야 한다. 양수이면 G_f^*에 u → v 간선이 존재하여 v ∈ S^*이 되어 모순이다. 따라서 f^*(u,v) = c(u,v).
(v,u) ∈ E이면 잔여 용량 f^*(v,u) = 0이어야 한다. 양수이면 G_f^*에 u → v 간선이 존재하여 v ∈ S^*이 되어 모순이다. 따라서 f^*(v,u) = 0.

보조 정리 1에 의해

|f^*| = f^*(S^*, T^*) = ∑_{u∈S^*, v∈T^*, (u,v)∈E} f^*(u,v) − ∑_{u∈S^*, v∈T^*, (v,u)∈E} f^*(v,u) = ∑_{u∈S^*, v∈T^*, (u,v)∈E} c(u,v) − 0 = c(S^*, T^*)

따라서 max|f| = |f^*| = c(S^*, T^*) ≥ min c(S,T)이고, 보조 정리 2에 의해 max|f| ≤ min c(S,T)이므로 max|f| = min c(S,T). ■