[Algo] 유량 네트워크 (1) 포드-풀커슨 방법(Ford-Fulkerson Method) (2024.11.03 수정)

Park Yeongseo·2024년 10월 12일
2

Algorithm

목록 보기
12/17
post-thumbnail

Introduction to Algorithm 4th edition을 번역 및 정리한 글입니다.
(2024.11.03) 파티 문제를 잘못 모델링해서 수정했습니다.

1. 유량 네트워크 (Flow networks)

유량 네트워크 G=(V,E)G = (V, E)는 간선 (u,v)E(u, v) \in E가 음이 아닌 용량(capacity) c(u,v)0c(u, v) \geq 0을 가지고 있는 유향 그래프로, 특별한 두 개의 정점, 소스(source) ss, 싱크(sink) tt를 가진다. 단 여기에서 간선 (u,v)(u, v)가 존재하는 경우, 그 역방향 간선 (v,u)(v, u)는 존재하지 않아야 한다.

(1) 흐름(유량, flow)

위와 같은 네트워크 GG에서 흐름 ff는 다음의 두 성질을 만족하는 실수-값 함수 f:V×VRf : V \times V \rightarrow \mathbb{R}다.

(a) 용량 제한

모든 u,vVu, v \in V에 대해, uu에서 vv로 흐르는 흐름 f(u,v)f(u, v)는 다음을 만족해야 한다.

0f(u,v)c(u,v)0 \leq f(u, v) \leq c(u, v)

다시 말해, 한 정점에서 다른 정점으로의 흐름은 음이 아니며, 해당 간선의 용량을 초과하지 않는 값이어야 한다.

(b) 흐름 보존

모든 uV{s,t}u \in V - \{s, t\}에 대해 다음을 만족한다.

vVf(u,v)=vVf(v,u)\sum_{v\in V}f(u, v) = \sum_{v \in V}f(v, u)

즉 소스와 싱크를 제외한 모든 정점에 대해, 해당 정점으로 들어오는 흐름의 총합과 해당 정점에서 나가는 흐름의 총합은 동일해야 한다.

아래와 같은 유량 그래프가 있다고 생각해보자. 각 간선에 적힌 숫자는 해당 간선의 용량이다.

간선 (s,v1)(s, v_1)에 8의 유량을 흘려 보면 아래와 같이 흐르게 될 것이다. 각 간선에 적힌 f/cf/ccc의 용량을 가지고 있는 해당 간선에 ff의 유량을 흘려 보냈음을 말한다.

2. 역평행 간선과 슈퍼 노드

(1) 역평행 간선(antiparallel edge)

앞서 유량 네트워크 G=(V,E)G = (V, E)(u,v)(u, v)라는 간선이 있으면 (v,u)(v, u)라는 간선은 없어야 한다고 말했다. 이러한 간선 (u,v)(u, v)(v,u)(v, u)를 가리켜 역평행(antiparallel)하다고 말하는데, 만약 주어진 그래프에 역평행 간선이 존재하는 경우에는 어떻게 처리해야 할까?

대충 위와 같이 역평행한 간선 (u,v)(u, v)(v,u)(v, u)가 모두 있는 경우, 아래와 같이 새로운 정점 vv'를 추가해 역평행한 간선과 동치인 유량 네트워크를 모델링할 수 있다.

(2) 여러 개의 소스와 싱크를 가지는 경우

한편, 여러 개의 소스와 싱크가 존재하는 경우에는 어떻게 처리할 수 있을까?

다음과 같은 경우가 주어졌다고 해보자. 각각 세 개의 소스 s1,s2,s3s1, s2, s3와 싱크 t1,t2,t3t1, t2, t3가 있다(간선의 용량 표시는 생략).

각 소스/싱크들과 연결된 새로운 소스 ss, 싱크 tt를 만들고, 무한한 용량의 간선으로 이어, 단일한 소스/싱크를 가질 수 있게 만들어 준다. 이렇게 만들어진 소스 ss를 슈퍼소스(supersource), 싱크 tt를 슈퍼싱크(supersink)라 한다.

3. 최대 유량 문제(maximum-flow problem)

흐름 ff의 값 f|f|는 다음과 같이 정의된다.

f=vVf(s,v)vVf(v,s)| f| = \sum_{v \in V}f(s, v) - \sum_{v \in V}f(v, s)

즉 유량 ff의 값 f|f|는 소스에서 나가는 흐름의 총합에서 소스로 들어오는 흐름의 총합을 뺀 것을 말한다. 최대 유량 문제는 소스 ss, 싱크 tt를 가지는 유량 네트워크 GG에서, 이 값이 최대가 되는 흐름을 찾는 문제다.

위 유량 네트워크를 예로 보면 다음과 같이 (s,v2)(s, v2)에 추가로 3의 유량을 흘려 보냈을 때 최대 유량이 된다.

(1) 대표 문제

P4 파티: https://www.acmicpc.net/problem/2367

문제에서 주어진 예제 입력을 위와 같은 유량 네트워크로 모델링 할 수 있다.

한 사람이 최대 K(=3)K(=3) 접시의 음식을 준비할 수 있기에 간선 (s,pi)(s, p_i)의 용량을 3으로 두고, 한 사람이 준비할 수 있는 한 종류의 음식은 최대 한 접시이기에 (pi,fj)(p_i, f_j) 간선의 용량은 모두 1로 둔다.

이제 ss에서 ff로 흐르는 최대 유량을 찾으면 문제를 해결할 수 있다.

(2024.11.03) 각 음식에서 tt로의 간선이 무한한 용량을 가지고 있는 것으로 그려놨지만, 문제를 다시 읽어보니 각 음식에도 최대 가져올 수 있는 접시의 수에 제한이 있었습니다. 때문에 해당 간선들의 용량은 무한이 아니라 음식 당 가져올 수 있는 접시의 수가 되어야 합니다.

4. Ford-Fulkerson method

포드-풀커슨 방법은 가장 간단하게 최대 유량을 찾기 위해 쓰이는 방법이다. 여기서 쓰이는 세 가지 주요 개념들이 있는데, 잔여 네트워크(residual network), 증가 경로(augmenting path), (cut)이다.

기본적인 아이디어는 간단하다. 유량을 추가로 흘려 보낼 수 있는 경로가 없을 때까지 그런 경로가 있는지를 확인하고, 그런 경로가 있으면 유량을 흘려 보내는 것이다.

다음으로 넘어가기에 앞서 아래의 케이스를 생각해보자.

위 유량 네트워크에서 흐를 수 있는 최대 유량은 11이다.

그런데 아래와 같이 (s,v2)(s, v2)로 8의 유량이 흘렀다고 생각해보자.

(s,v2)(s, v2)는 이미 가득 차 있으므로 더 이상 추가 유량을 흘려보낼 수 없고, (s,v1)(s, v1)으로 유량을 흘려보내도 이미 (v3,v4),(v3,t)(v3, v4), (v3, t)의 용량이 가득 차 있기 때문에 추가적인 유량을 흘려보낼 수 없게 된다.

(1) Residual networks

(a) 잔여 용량(Residual Capacity)

유량 네트워크 GG와 흐름 ff가 주어졌다고 하자. 잔여 네트워크(residual network)는 이렇게 흐름을 보내고 남은 GG의 간선의 용량을 자신의 간선의 용량으로 가지고 있는 네트워크다.

간단히, 용량 c(u,v)c(u, v)의 간선(u,v)(u, v)에 유량 f(u,v)f(u, v)가 흐르고 있다면, 이 간선에는 c(u,v)f(u,v)c(u, v) - f(u, v)의 유량을 추가로 흘려보낼 수 있으므로, 해당 간선은 GfG_f에서 cf(u,v)=c(u,v)f(u,v)c_f(u, v) = c(u, v) - f(u, v)의 용량을 가지는 간선으로 추가된다.

그런데 위와 같이 이미 흐른 유량 때문에 더 이상 유량을 흘려 보낼 수 없게 되는 경우를 생각해보자. 이미 어떤 간선에 흐르는 유량은 줄이고 다른 곳의 유량을 높여 전체 유량을 증가할 수 있다면 위와 같은 문제를 해결할 수 있을 것이다.

이를 위해 잔여 네트워크에는 GG에는 없던 다른 간선들도 추가되는데, GG의 간선에 양의 유량 f(u,v)f(u, v)가 흐른다면, 잔여 네트워크 GfG_f에는 잔여 용량(residual capacity) cf(v,u)=f(u,v)c_f(v, u) = f(u, v)를 갖는 간선 (v,u)(v, u)도 추가된다. 이렇게 역방향의 간선(v,u)(v, u)으로 흐름을 보내는 것은 순방향 간선 (u,v)(u, v)의 흐름을 줄이는 것으로 생각할 수 있고, 이를 통해 이미 간선(u,v)(u, v)를 통해 흘려보낸 흐름을 줄이는 것이 가능해진다.

요컨대 소스 ss, 싱크 tt, 흐름 ff를 가지고 있는 유량 네트워크 G=(V,E)G = (V, E)에 대해, 잔여 용량 cf(u,v)c_f(u, v)는 다음과 같이 정의할 수 있다.

cf(u,v)={c(u,v)f(u,v)if (u,v)E,f(v,u)if (v,u)E,0otherwisec_f(u, v) = \begin {cases} c(u,v) - f(u,v) & \text{if} \ (u, v)\in E,\\ f(v, u) & \text{if} \ (v, u)\in E,\\ 0 & otherwise \end {cases}

앞서 제한하기를 유량 네트워크에 간선 (u,v)(u, v)가 있으면 (v,u)(v, u)는 없다고 했으니, 잔여 네트워크의 간선은 위 셋 중 하나만을 그 용량으로 가진다.

(b) 잔여 간선(Residual Edges)

위의 잔여 용량을 통해 잔여 네트워크 GfG_f는 다음과 같이 정의할 수 있다.

Gf=(V,Ef), where Ef={(u,v)V×V:cf(u,v)>0}G_f = (V, E_f), \ \text{where}\ E_f=\{(u,v) \in V \times V: c_f(u, v) > 0\}

(b) 잔여 네트워크에서의 흐름

이 잔여 네트워크는 (u,v)(u, v)(v,u)(v, u)가 함께 존재할 수 있다는 점만을 제외하면 유량 네트워크와 동일한 성질을 가지고 있으며, 잔여 네트워크에서의 흐름은 원래 유량 네트워크에 흐름을 더하는 데에 로드맵을 제공한다.

ffG=(V,E)G = (V, E)의 흐름, ff'GGff에 대한 잔여 네트워크 GfG_f의 흐름이라고 하자. 이때 ffff'만큼 증가(augmentation)시킨 것(fff \uparrow f'로 표기)은 다음과 같은 V×VRV \times V \rightarrow \mathbb{R}의 함수로 정의할 수 있다.

(ff)(u,v)={f(u,v)+f(u,v)f(v,u)if (u,v)E,0otherwise.(f \uparrow f')(u, v) = \begin {cases} f(u, v) + f'(u, v) - f'(v, u) & \text{if} \ (u,v) \in E, \\ 0 & otherwise. \end {cases}

GG에는 이미 f(u,v)f(u, v)가 흐르고 있다. 여기에 f(u,v)f'(u, v)를 더하는 것은 추가로 더 흘려보낼 수 있는 흐름을 흘려보내는 것이고, f(v,u)f'(v, u)를 빼는 것은 이미 흘려 보낸 유량을 그만큼 취소(cancellation)하는 것으로 볼 수 있다.

Lemma 1

G=(V,E)G = (V, E)가 소스 ss, 싱크 tt를 가지는 유량 네트워크라 하고, ffGG의 흐름이라고 하자. GfG_f를 유량 네트워크 GGff에 대한 잔여 네트워크라 하고, ff'GfG_f의 흐름이라고 하자. 위에서 정의된 fff \uparrow f'는 값 ff=f+f|f \uparrow f'| = |f| + |f'|를 가지는 GG의 흐름이다.

pf.pf.
우선 fff \uparrow f'가 흐름의 첫 번째 성질(용량 제한)을 만족함을 보이도록 하자.

잔여 용량의 정의에 따라 (u,v)E(u, v) \in E이면 cf(v,u)=f(u,v)c_f(v, u) = f(u, v)이다. ff'GfG_f의 흐름이므로, f(v,u)f'(v, u)cf(v,u)c_f(v, u)를 초과할 수 없고, 따라서 f(v,u)cf(v,u)=f(u,v)f'(v, u) \leq c_f(v, u) = f(u, v)다. 그러므로

(ff)(u,v)=f(u,v)+f(u,v)f(u,v)f(u,v)+f(u,v)f(u,v)=f(u,v)0\begin {aligned} (f \uparrow f') (u, v) &= f(u, v) + f'(u,v) - f'(u, v) \\ & \geq f(u,v) + f'(u, v) - f(u , v)\\ &= f'(u, v)\\ & \geq 0 \end {aligned}

이다.

또한 흐름은 음이 아니고, 간선의 용량을 넘을 수 없음을 생각하면

(ff)(u,v)==f(u,v)+f(u,v)f(v,u)f(u,v)+f(u,v)f(u,v)+cf(u,v)=f(u,v)+c(u,v)f(u,v)=c(u,v)\begin {aligned} (f \uparrow f') (u, v) = & = f(u, v) + f'(u, v) - f'(v, u) \\ & \leq f(u, v) + f'(u, v)\\ & \leq f(u, v) + c_f(u, v)\\ & = f(u, v) + c(u, v) - f(u, v) \\ & = c(u, v) \end{aligned}

이다.

따라서 fff \uparrow f'0(ff)(u,v)c(u,v)0 \leq (f \uparrow f')(u,v) \leq c(u,v)로, 흐름의 첫 번째 성질을 만족한다.

다음으로는 fff \uparrow f'가 흐름의 두 번째 성질(흐름 보존)을 만족하면서 ff=f+f|f \uparrow f'| = |f| + |f'|임을 보이자.

모든 uVu \in V에 대해 다음이 성립한다.

vV(ff)(u,v)vV(ff)(v,u)=vVf(u,v)vVf(v,u)+vVf(u,v)vVf(v,u)\begin {aligned} \sum_{v\in V}(f \uparrow f')(u, v) - &\sum_{v \in V}(f \uparrow f')(v, u) = \\ & \sum_{v \in V}f(u, v) - \sum_{v \in V}f(v, u) + \sum_{v \in V}f'(u, v) - \sum_{v \in V}f'(v, u) \end{aligned}

이를 증명하기 위해, 어떤 고정된 정점 uu에 대해 다음과 같이 두 집합을 정의해보자.

Vl(u)={v:(u,v)E}Ve(u)={v:(v,u)E}\begin {aligned} & V_l(u) = \{v : (u, v) \in E\} \\ & V_e(u) = \{v : (v, u) \in E\} \end {aligned}

GG에 간선 (u,v)(u, v)(v,u)(v, u)가 함께 있는 경우가 없기 때문에, Vl(u)Ve(u)=V_l(u) \cap V_e(u) = \emptyset이고, Vl(u)Ve(u)VV_l(u) \cup V_e(u) \subseteq V다.

이전에 나온 항등식을 다시 보자.

(ff)(u,v)={f(u,v)+f(u,v)f(v,u)if (u,v)E,0otherwise.(f \uparrow f')(u, v) = \begin {cases} f(u, v) + f'(u, v) - f'(v, u) & \text{if} \ (u,v) \in E, \\ 0 & otherwise. \end {cases}

(ff)(u,v)(f \uparrow f')(u, v)가 양수가 되는 경우는 (u,v)E(u, v) \in E일 때 밖에 없다. 반대로, (ff)(v,e)(f \uparrow f')(v, e)가 양수가 되는 경우는 (v,u)E(v, u) \in E일 때 밖에 없다. (각각 그 외의 경우는 모두 0이므로)

따라서 위 항등식은 다음과 같이 쓸 수 있다.

vV(ff)(u,v)vV(ff)(v,u)=vVl(u)(ff)(u,v)vVe(u)(ff)(v,u)=vVl(u)(f(u,v)+f(u,v)f(v,u))vVe(u)(f(v,u)+f(v,u)f(u,v))=vVl(u)f(u,v)vVe(u)f(v,u)+vVl(u)f(u,v)+vVe(u)f(u,v)vVl(u)f(v,u)vVe(u)f(v,u)=vVl(u)f(u,v)vVe(u)f(v,u)+vVl(u)Ve(u)f(u,v)vVl(u)Ve(u)f(v,u)=vVf(u,v)vVf(v,u)+vVf(u,v)vVf(v,u)\begin {aligned} & \sum_{v\in V}(f \uparrow f')(u, v) - \sum_{v \in V}(f \uparrow f')(v, u) \\ & = \sum_{v\in V_l(u)}(f \uparrow f')(u, v) - \sum_{v \in V_e(u)}(f \uparrow f')(v, u) \\ & = \sum_{v \in V_l(u)}(f(u, v) + f'(u, v) - f'(v, u)) - \sum_{v \in V_e(u)}(f(v, u) + f'(v, u) - f'(u, v)) \\ & = \sum_{v \in V_l(u)}f(u, v) - \sum_{v \in V_e(u)}f(v, u) + \sum_{v \in V_l(u)}f'(u, v) + \sum_{v \in V_e(u)}f'(u, v) - \sum_{v \in V_l(u)}f'(v, u) - \sum_{v \in V_e(u)}f'(v, u) \\ & = \sum_{v \in V_l(u)}f(u, v) - \sum_{v \in V_e(u)}f(v, u) + \sum_{v \in V_l(u) \cup V_e(u)}f'(u, v) - \sum_{v \in V_l(u) \cup V_e(u)}f'(v, u) \\ & = \sum_{v \in V}f(u, v) - \sum_{v \in V}f(v, u) + \sum_{v \in V}f'(u, v) - \sum_{v \in V}f'(v, u) \end{aligned}

이제 u=su = s라 하자. 아래와 같이 ff=f+f| f \uparrow f'| = |f| + |f'|임을 증명할 수 있다.

ff=vV(ff)(s,v)vV(ff)(v,s)=vVf(s,v)vVf(v,s)+vVf(s,v)vVf(v,s)=f+f\begin {aligned} |f \uparrow f'| &= \sum_{v\in V}(f \uparrow f')(s, v) - \sum_{v \in V}(f \uparrow f')(v, s) \\ & = \sum_{v \in V}f(s, v) - \sum_{v \in V}f(v, s) + \sum_{v \in V}f'(s, v) - \sum_{v \in V}f'(v, s) \\ & = |f| + |f'| \end {aligned}

또한 위 항등식을 정리하면 모든 uV{s,t}u \in V - \{s, t\}에 대해 다음이 성립함도 증명할 수 있다.

vVf(u,v)=vVf(v,u)(G에서의 흐름 보존)vVf(u,v)=vVf(v,u)(G의 흐름은 G의 흐름과 같은 성질을 가짐)vV(ff)(u,v)=vinV(ff)(v,u).(ff의 G에서의 흐름 보존)\begin{aligned} \sum_{v \in V}f(u, v) &= \sum_{v \in V}f(v, u) &(G \text{에서의 흐름 보존})\\ \sum_{v \in V}f'(u, v) &= \sum_{v \in V} f'(v, u) &(G'\text{의 흐름은 }G \text{의 흐름과 같은 성질을 가짐})\\ \therefore \sum_{v \in V}(f \uparrow f')(u, v) &= \sum_{v in V}(f \uparrow f')(v, u). &(f \uparrow f' \text{의 } G \text{에서의 흐름 보존}) \end{aligned}

(2) Augmenting paths

유량 네트워크 G=(V,E)G = (V, E)와 흐름 ff가 주어졌을 때, 증가 경로(augmenting path) pp는 잔여 네트워크 GfG_f의, ss에서 tt로의 단순 경로(simple path)다.

증가 경로 위의 간선 (u,v)(u, v)에는 최대 cf(u,v)c_f(u, v)의 유량이 흐를 수 있으며, 이 간선들의 용량 중 최솟값을 증가 경로의 잔여 용량이라고 한다.

cf(p)=min{cf(u,v):(u,v) is in p}c_f(p) = min\{c_f(u, v) : (u, v) \text{ is in } p\}

Lemma 2

유량 네트워크 G=(V,E)G = (V, E)와 흐름 ff를 생각하자. ppGfG_f의 증가 경로라 할 때, fp:V×VRf_p : V \times V \rightarrow \mathbb{R}를 다음과 같이 정의하면, fpf_pfp=cf(p)>0|f_p| = c_f(p) > 0GfG_f의 흐름이다.

fp(u,v)={cf(p)if (u,v) is on p,0otherwise.f_p(u, v) = \begin {cases} c_f(p) & \text{if } (u,v)\ \text{is on } p, \\ 0 & \text{otherwise.} \end {cases}

fp(u,v)cf(p)cf(u,v)f_p(u, v) \leq c_f(p) \leq c_f(u,v)이므로 용량 제한은 만족한다(증가 경로의 잔여 용량).
pp가 잔여 네트워크 GfG_f의, ss에서 tt로의 단순 경로이기에, s,ts, t를 제외한 정점들로 들어오는 흐름은 정점을 지나 동일한 양으로 그대로 흘러나가게 되므로 흐름 보존도 만족된다.

u=su = s인 경우를 보면, ppss에서 tt로의 단순 경로이기에, ss에서 나가는 간선은 fp(s,v)=cf(p)f_p(s, v) = c_f(p)를 유량으로 갖는 간선 하나 뿐이고, ss로 들어오는 간선은 존재하지 않는다. 따라서 vVfp(s,v)vVfp(v,s)=cf(p)0=cf(p)\sum_{v \in V}f_p(s, v) - \sum_{v \in V}f_p(v, s) = c_f(p) - 0 = c_f(p)이다.

Corollary 1

G=(V,E)G = (V, E)가 유량 네트워크고, ffGG의 흐름, ppGfG_f에서의 증가 경로라 하자. fpf_p가 위에 정의된 것과 같고, fffpf_p만큼 증가하는 경우, 함수 ffpf \uparrow f_p는 값 ffp=f+fp>f|f \uparrow f_p| = |f| + |f_p| > |f|을 가지는 GG의 흐름이다.

pf.pf. Lemma 1과 2.

(3) Cuts of flow networks

포드-풀커슨 방법은 더 이상 증가 경로를 찾을 수 없을 때까지 증가 경로를 찾아 유량을 흘려보내는 방법을 사용하는데, 그렇다면 이 과정이 모두 종료됐을 때 최대 유량을 찾을 수 있음이 보장될까?

최대 유량-최소 컷 정리(max-flow min-cut theorem)에 따르면 유량 네트워크의 유량이 최대라는 것은 잔여 네트워크에 더 이상 증가 경로가 없다는 것과 동치가 된다.

이를 알아보기 위해 (cut)에 대해 알아보자.

유량 네트워크 G=(V,E)G = (V, E)의 컷 (S,T)(S, T)는 정점 집합 VVsSs \in S, tTt \in T인 두 개의 집합 SSTT로 분할한 것이다.

ff가 흐름일 때, SSTT를 가로지르는 net flow f(S,T)f(S, T)는 다음과 같이 정의된다.

f(S,T)=uSvTf(u,v)uSvTf(v,u)f(S, T) = \sum_{u \in S}\sum_{v \in T}f(u, v) - \sum_{u \in S}\sum_{v \in T}f(v, u)

이때 컷 (S,T)(S, T)의 용량은 다음과 같이 정의된다.

c(S,T)=uSvTc(u,v)c(S, T) = \sum_{u \in S}\sum_{v \in T}c(u, v)

앞서 봤던 네트워크를 이렇게 잘라보자. S={s,v1,v2},T={v3,v4,t}S = \{s, v1, v2\}, T = \{v3, v4, t\}가 되도록 잘랐다.

이때 f(S,T)=8+0+3=11f(S, T) = 8 + 0 + 3 = 11 , c(S,T)=8+10+3=21c(S, T) = 8+10+3 = 21이다.

네트워크의 최소 컷(minimum cut)은 네트워크의 모든 컷들 중 최소의 용량을 가지는 것을 말한다.

위 네트워크의 경우, 이렇게 c(S,T)=11c(S, T) = 11이 되도록 분할할 수 있고, 이것이 최소 컷이 된다.

Lemma 3

ff가 소스 ss, 싱크 tt를 가지는 유량 네트워크 GG의 흐름일 때, GG의 임의의 컷 (S,T)(S, T)에 대해 (S,T)(S, T)를 가로지르는 net flow는 f(S,T)=ff(S, T) = |f|다.

pf.pf.
GG의 임의의 uV{s,t}u \in V - \{s,t\}에 대해, 흐름 보존이 만족되므로 f|f|는 다음과 같이 쓸 수 있다. 뒤쪽 괄호 안이 모두 0이 되기 때문이다.

f=vVf(s,v)vVf(v,s)+uS{s}(vVf(u,v)vVf(v,u))|f| = \sum_{v \in V}f(s, v) - \sum_{v \in V}f(v,s) + \sum_{u \in S - \{s\}}(\sum_{v \in V}f(u, v) - \sum_{v \in V}f(v,u))

위 항등식을 전개하고 다시 묶으면 다음을 얻을 수 있다.

f=vVf(s,v)vVf(v,s)+uS{s}(vVf(u,v)vVf(v,u))=vVf(s,v)vVf(v,s)+uS{s}vVf(u,v)uS{s}vVf(v,u)=vV(f(s,v)+uS{s}f(u,v))vV(f(v,s)+uS{s}f(v,u))=vVuSf(u,v)vVuSf(v,u)\begin {aligned} |f| &= \sum_{v \in V}f(s, v) - \sum_{v \in V}f(v,s) + \sum_{u \in S - \{s\}}(\sum_{v \in V}f(u, v) - \sum_{v \in V}f(v,u)) \\ &= \sum_{v \in V}f(s, v) - \sum_{v \in V}f(v,s) + \sum_{u \in S - \{s\}}\sum_{v \in V}f(u, v) - \sum_{u \in S - \{s\}}\sum_{v \in V}f(v, u) \\ &= \sum_{v \in V}(f(s, v) + \sum_{u \in S - \{s\}}f(u, v)) - \sum_{v \in V}(f(v, s) + \sum_{u \in S - \{s\}}f(v, u)) \\ &= \sum_{v \in V}\sum_{u \in S}f(u, v) - \sum_{v \in V}\sum_{u \in S}f(v, u) \end {aligned}

V=STV = S \cup T이고 ST=S \cap T = \emptyset이므로 각 vV\sum_{v \in V}vSvT\sum_{v\in S} 와 \sum_{v \in T}의 합으로 나타낼 수 있다.

f=vVuSf(u,v)vVuSf(v,u)=vSuSf(u,v)+vTuSf(u,v)vSuSf(v,u)vTuSf(v,u)=(vSuSf(u,v)vSuSf(v,u))+vTuSf(u,v)vTuSf(v,u)=(0)+vTuSf(u,v)vTuSf(v,u)=vTuSf(u,v)vTuSf(v,u)=f(S,T)\begin{aligned} |f| &= \sum_{v \in V}\sum_{u \in S}f(u, v) - \sum_{v \in V}\sum_{u \in S}f(v, u)\\ &= \sum_{v \in S}\sum_{u \in S}f(u, v) + \sum_{v \in T}\sum_{u \in S}f(u, v) - \sum_{v \in S}\sum_{u \in S}f(v, u) - \sum_{v \in T}\sum_{u \in S}f(v, u)\\ &= (\sum_{v \in S}\sum_{u \in S}f(u, v) - \sum_{v \in S}\sum_{u \in S}f(v, u)) + \sum_{v \in T}\sum_{u \in S}f(u, v) - \sum_{v \in T}\sum_{u \in S}f(v, u)\\ &= (0) + \sum_{v \in T}\sum_{u \in S}f(u, v) - \sum_{v \in T}\sum_{u \in S}f(v, u) \\ &= \sum_{v \in T}\sum_{u \in S}f(u, v) - \sum_{v \in T}\sum_{u \in S}f(v, u)\\ &= f(S, T) \end{aligned}

Corollary 2

네트워크 GG의 임의의 흐름 ff의 값은 GG의 임의의 컷의 용량을 초과하지 못한다.

pf.pf.
(S,T)(S, T)GG의 임의의 컷, ff를 임의의 흐름이라 하자. Lemma 4와 용량 제한으로 인해

f=f(S,T)=uSvTf(u,v)uSvTf(v,u)uSvTf(u,v)uSvTc(u,v)=c(S,T)\begin {aligned} |f| &= f(S, T)\\ &= \sum_{u\in S}\sum_{v\in T}f(u, v) - \sum_{u\in S}\sum_{v\in T}f(v, u)\\ & \leq \sum_{u\in S}\sum_{v\in T}f(u, v)\\ & \leq \sum_{u\in S}\sum_{v\in T}c(u, v)\\ & = c(S, T) \end {aligned}

가 성립한다.

다만 이 따름정리는 f|f|의 상한이 c(S,T)c(S, T)라고 말할 뿐이고, 아래의 최대 유량 최소 컷 정리에 따르면 사실 최대 유량은 최소 컷의 용량과 동일하다.

최대 유량 최소 컷 정리(Max-flow Min-cut Theorem)

ff가 소스 ss, 싱크 tt를 가지는 유량 네트워크 G=(V,E)G = (V, E)의 흐름이라 하자. 다음의 세 조건은 서로 동치다.
1. ffGG의 최대 유량이다.
2. 잔여 네트워크에 GfG_f 증가 경로가 존재하지 않는다.
3. GG의 어떤 컷 (S,T)(S, T)에 대해, f=c(S,T)|f| = c(S, T) 다.

pf.(1)(2):pf. (1) \Rightarrow (2) : ffGG의 최대 유량인데 GfG_f에 증가 경로 pp가 존재한다고 하자. 만약 그렇다면 Corollary 1에 따라 GG에는 ffp>f|f \uparrow f_p| > |f|인 유량이 흐를 수 있다. ffGG의 최대 유량이라는 가정과 모순이므로 ff가 최대 유량이면 GfG_f에 증가 경로는 존재하지 않는다.

(2)(3):(2) \Rightarrow (3): GfG_f에 증가 경로가 없다고 하고, 다음과 같이 집합 S,TS, T를 정의하자.

S={vV:Gf에 s에서 v로의 경로가 존재}T=VS\begin{aligned} S &= \{v \in V: G_f\text{에 }s \text{에서 } v \text{로의 경로가 존재}\}\\ T &= V - S \end{aligned}

GfG_f에 증가 경로가 없으므로 t∉St \not\in S고, 따라서 tTt \in T다.

uS,vTu \in S, v \in T인 두 정점에 대해, (u,v)E(u, v) \in E가 있을 때, f(u,v)=c(u,v)f(u, v) = c(u, v)다. 만약 f(u,v)<c(u,v)f(u, v) < c(u, v)라면 남은 용량이 있어 (u,v)Ef(u, v) \in E_f가 되어 증가 경로에 포함되고, ss에서 vv로의 경로가 존재하기 때문이다.

만약 (v,u)E(v, u) \in E라면 f(v,u)=0f(v, u) = 0이 되어야 한다. 그렇지 않으면 cf(u,v)=f(v,u)c_f(u, v) = f(v, u)가 되어 (u,v)Ef(u, v) \in E_f가 되고, 마찬가지로 vSv \in S가 되기 때문이다.

따라서 다음과 같이 쓸 수 있다.

f(S,T)=uSvTf(u,v)uSvTf(v,u)=uSvTc(u,v)uSvT0=c(S,T)\begin {aligned} f(S, T) &= \sum_{u\in S}\sum_{v\in T}f(u, v) - \sum_{u\in S}\sum_{v\in T}f(v, u)\\ &= \sum_{u\in S}\sum_{v\in T}c(u, v) - \sum_{u\in S}\sum_{v\in T}0 \\ &= c(S, T) \end {aligned}

Lemma 3에 따라 f=f(S,T)=c(S,T)|f| = f(S, T) = c(S, T)이다.

(3)(1):(3) \Rightarrow (1) : Corollary 2에 따르면 임의의 컷 (S,T)(S, T)에 대해 fc(S,T)|f| \leq c(S, T)다. 따라서 어떤 컷에 대해 f=c(S,T)|f| = c(S, T)가 되는 것은 이 ff가 최대 유량이라는 말이다.

5. 기본 Ford-Fulkerson

포드-풀커슨 방법에서는 반복적으로 증가 경로 pp를 찾고, 이를 통해 유량 ff를 값 f+fp|f| + |f_p|를 갖는 ffpf \uparrow f_p로 바꾼다.

FORD-FULKERSON(G, s, t)
for each edge (u,v)G.E(u, v) \in G.E
    (u,v).f=0(u, v).f = 0
while there exists a path pp from ss to tt in the residual network GfG_f
    cf(p)=min{cf(u,v):(u,v) is in p}c_f(p) = min\{c_f(u, v) : (u, v) \text{ is in } p\}
    for each edge (u,v)(u, v) in pp
      if (u,v)G.E(u, v) \in G.E
        (u,v).f=(u,v).f+cf(p)(u,v).f = (u, v).f + c_f(p)
      else (v,u).f=(v.u).fcf(p)(v, u).f = (v.u).f - c_f(p)
return ff

일단 모든 간선의 흐름을 0으로 초기화한 후, 잔여 네트워크 GfG_f에서 증가 경로를 찾는다. 증가 경로를 찾았다면 경로의 잔여 용량만큼 흐름을 추가로 흘려 보내주는데, 이때 간선이 EE에 존재한다면 순방향이므로 흐름을 더해주고, 그렇지 않은 경우네는 역방향이므로 흐름을 빼준다.

더 이상 증가 경로를 찾을 수 없는 경우, 최대 유량을 찾은 것임을 증명했으므로 최대 유량인 ff를 반환한다.

포드 풀커슨 방법에 대한 분석은 다음 글에

0개의 댓글