Introduction to Algorithm 4th edition을 번역 및 정리한 글입니다.
(2024.11.03) 파티 문제를 잘못 모델링해서 수정했습니다.
1. 유량 네트워크 (Flow networks)
유량 네트워크 G=(V,E)는 간선 (u,v)∈E가 음이 아닌 용량(capacity) c(u,v)≥0을 가지고 있는 유향 그래프로, 특별한 두 개의 정점, 소스(source) s, 싱크(sink) t를 가진다. 단 여기에서 간선 (u,v)가 존재하는 경우, 그 역방향 간선 (v,u)는 존재하지 않아야 한다.
(1) 흐름(유량, flow)
위와 같은 네트워크 G에서 흐름 f는 다음의 두 성질을 만족하는 실수-값 함수 f:V×V→R다.
(a) 용량 제한
모든 u,v∈V에 대해, u에서 v로 흐르는 흐름 f(u,v)는 다음을 만족해야 한다.
0≤f(u,v)≤c(u,v)
다시 말해, 한 정점에서 다른 정점으로의 흐름은 음이 아니며, 해당 간선의 용량을 초과하지 않는 값이어야 한다.
(b) 흐름 보존
모든 u∈V−{s,t}에 대해 다음을 만족한다.
v∈V∑f(u,v)=v∈V∑f(v,u)
즉 소스와 싱크를 제외한 모든 정점에 대해, 해당 정점으로 들어오는 흐름의 총합과 해당 정점에서 나가는 흐름의 총합은 동일해야 한다.
아래와 같은 유량 그래프가 있다고 생각해보자. 각 간선에 적힌 숫자는 해당 간선의 용량이다.
간선 (s,v1)에 8의 유량을 흘려 보면 아래와 같이 흐르게 될 것이다. 각 간선에 적힌 f/c는 c의 용량을 가지고 있는 해당 간선에 f의 유량을 흘려 보냈음을 말한다.
2. 역평행 간선과 슈퍼 노드
(1) 역평행 간선(antiparallel edge)
앞서 유량 네트워크 G=(V,E)에 (u,v)라는 간선이 있으면 (v,u)라는 간선은 없어야 한다고 말했다. 이러한 간선 (u,v)와 (v,u)를 가리켜 역평행(antiparallel)하다고 말하는데, 만약 주어진 그래프에 역평행 간선이 존재하는 경우에는 어떻게 처리해야 할까?
대충 위와 같이 역평행한 간선 (u,v)와 (v,u)가 모두 있는 경우, 아래와 같이 새로운 정점 v′를 추가해 역평행한 간선과 동치인 유량 네트워크를 모델링할 수 있다.
(2) 여러 개의 소스와 싱크를 가지는 경우
한편, 여러 개의 소스와 싱크가 존재하는 경우에는 어떻게 처리할 수 있을까?
다음과 같은 경우가 주어졌다고 해보자. 각각 세 개의 소스 s1,s2,s3와 싱크 t1,t2,t3가 있다(간선의 용량 표시는 생략).
각 소스/싱크들과 연결된 새로운 소스 s, 싱크 t를 만들고, 무한한 용량의 간선으로 이어, 단일한 소스/싱크를 가질 수 있게 만들어 준다. 이렇게 만들어진 소스 s를 슈퍼소스(supersource), 싱크 t를 슈퍼싱크(supersink)라 한다.
3. 최대 유량 문제(maximum-flow problem)
흐름 f의 값 ∣f∣는 다음과 같이 정의된다.
∣f∣=v∈V∑f(s,v)−v∈V∑f(v,s)
즉 유량 f의 값 ∣f∣는 소스에서 나가는 흐름의 총합에서 소스로 들어오는 흐름의 총합을 뺀 것을 말한다. 최대 유량 문제는 소스 s, 싱크 t를 가지는 유량 네트워크 G에서, 이 값이 최대가 되는 흐름을 찾는 문제다.
위 유량 네트워크를 예로 보면 다음과 같이 (s,v2)에 추가로 3의 유량을 흘려 보냈을 때 최대 유량이 된다.
(1) 대표 문제
P4 파티: https://www.acmicpc.net/problem/2367
문제에서 주어진 예제 입력을 위와 같은 유량 네트워크로 모델링 할 수 있다.
한 사람이 최대 K(=3) 접시의 음식을 준비할 수 있기에 간선 (s,pi)의 용량을 3으로 두고, 한 사람이 준비할 수 있는 한 종류의 음식은 최대 한 접시이기에 (pi,fj) 간선의 용량은 모두 1로 둔다.
이제 s에서 f로 흐르는 최대 유량을 찾으면 문제를 해결할 수 있다.
(2024.11.03) 각 음식에서 t로의 간선이 무한한 용량을 가지고 있는 것으로 그려놨지만, 문제를 다시 읽어보니 각 음식에도 최대 가져올 수 있는 접시의 수에 제한이 있었습니다. 때문에 해당 간선들의 용량은 무한이 아니라 음식 당 가져올 수 있는 접시의 수가 되어야 합니다.
4. Ford-Fulkerson method
포드-풀커슨 방법은 가장 간단하게 최대 유량을 찾기 위해 쓰이는 방법이다. 여기서 쓰이는 세 가지 주요 개념들이 있는데, 잔여 네트워크(residual network), 증가 경로(augmenting path), 컷(cut)이다.
기본적인 아이디어는 간단하다. 유량을 추가로 흘려 보낼 수 있는 경로가 없을 때까지 그런 경로가 있는지를 확인하고, 그런 경로가 있으면 유량을 흘려 보내는 것이다.
다음으로 넘어가기에 앞서 아래의 케이스를 생각해보자.
위 유량 네트워크에서 흐를 수 있는 최대 유량은 11이다.
그런데 아래와 같이 (s,v2)로 8의 유량이 흘렀다고 생각해보자.
(s,v2)는 이미 가득 차 있으므로 더 이상 추가 유량을 흘려보낼 수 없고, (s,v1)으로 유량을 흘려보내도 이미 (v3,v4),(v3,t)의 용량이 가득 차 있기 때문에 추가적인 유량을 흘려보낼 수 없게 된다.
(1) Residual networks
(a) 잔여 용량(Residual Capacity)
유량 네트워크 G와 흐름 f가 주어졌다고 하자. 잔여 네트워크(residual network)는 이렇게 흐름을 보내고 남은 G의 간선의 용량을 자신의 간선의 용량으로 가지고 있는 네트워크다.
간단히, 용량 c(u,v)의 간선(u,v)에 유량 f(u,v)가 흐르고 있다면, 이 간선에는 c(u,v)−f(u,v)의 유량을 추가로 흘려보낼 수 있으므로, 해당 간선은 Gf에서 cf(u,v)=c(u,v)−f(u,v)의 용량을 가지는 간선으로 추가된다.
그런데 위와 같이 이미 흐른 유량 때문에 더 이상 유량을 흘려 보낼 수 없게 되는 경우를 생각해보자. 이미 어떤 간선에 흐르는 유량은 줄이고 다른 곳의 유량을 높여 전체 유량을 증가할 수 있다면 위와 같은 문제를 해결할 수 있을 것이다.
이를 위해 잔여 네트워크에는 G에는 없던 다른 간선들도 추가되는데, G의 간선에 양의 유량 f(u,v)가 흐른다면, 잔여 네트워크 Gf에는 잔여 용량(residual capacity) cf(v,u)=f(u,v)를 갖는 간선 (v,u)도 추가된다. 이렇게 역방향의 간선(v,u)으로 흐름을 보내는 것은 순방향 간선 (u,v)의 흐름을 줄이는 것으로 생각할 수 있고, 이를 통해 이미 간선(u,v)를 통해 흘려보낸 흐름을 줄이는 것이 가능해진다.
요컨대 소스 s, 싱크 t, 흐름 f를 가지고 있는 유량 네트워크 G=(V,E)에 대해, 잔여 용량 cf(u,v)는 다음과 같이 정의할 수 있다.
cf(u,v)=⎩⎪⎪⎨⎪⎪⎧c(u,v)−f(u,v)f(v,u)0if (u,v)∈E,if (v,u)∈E,otherwise
앞서 제한하기를 유량 네트워크에 간선 (u,v)가 있으면 (v,u)는 없다고 했으니, 잔여 네트워크의 간선은 위 셋 중 하나만을 그 용량으로 가진다.
(b) 잔여 간선(Residual Edges)
위의 잔여 용량을 통해 잔여 네트워크 Gf는 다음과 같이 정의할 수 있다.
Gf=(V,Ef), where Ef={(u,v)∈V×V:cf(u,v)>0}
(b) 잔여 네트워크에서의 흐름
이 잔여 네트워크는 (u,v)와 (v,u)가 함께 존재할 수 있다는 점만을 제외하면 유량 네트워크와 동일한 성질을 가지고 있으며, 잔여 네트워크에서의 흐름은 원래 유량 네트워크에 흐름을 더하는 데에 로드맵을 제공한다.
f를 G=(V,E)의 흐름, f′를 G의 f에 대한 잔여 네트워크 Gf의 흐름이라고 하자. 이때 f를 f′만큼 증가(augmentation)시킨 것(f↑f′로 표기)은 다음과 같은 V×V→R의 함수로 정의할 수 있다.
(f↑f′)(u,v)={f(u,v)+f′(u,v)−f′(v,u)0if (u,v)∈E,otherwise.
G에는 이미 f(u,v)가 흐르고 있다. 여기에 f′(u,v)를 더하는 것은 추가로 더 흘려보낼 수 있는 흐름을 흘려보내는 것이고, f′(v,u)를 빼는 것은 이미 흘려 보낸 유량을 그만큼 취소(cancellation)하는 것으로 볼 수 있다.
Lemma 1
G=(V,E)가 소스 s, 싱크 t를 가지는 유량 네트워크라 하고, f가 G의 흐름이라고 하자. Gf를 유량 네트워크 G의 f에 대한 잔여 네트워크라 하고, f′를 Gf의 흐름이라고 하자. 위에서 정의된 f↑f′는 값 ∣f↑f′∣=∣f∣+∣f′∣를 가지는 G의 흐름이다.
pf.
우선 f↑f′가 흐름의 첫 번째 성질(용량 제한)을 만족함을 보이도록 하자.
잔여 용량의 정의에 따라 (u,v)∈E이면 cf(v,u)=f(u,v)이다. f′가 Gf의 흐름이므로, f′(v,u)는 cf(v,u)를 초과할 수 없고, 따라서 f′(v,u)≤cf(v,u)=f(u,v)다. 그러므로
(f↑f′)(u,v)=f(u,v)+f′(u,v)−f′(u,v)≥f(u,v)+f′(u,v)−f(u,v)=f′(u,v)≥0
이다.
또한 흐름은 음이 아니고, 간선의 용량을 넘을 수 없음을 생각하면
(f↑f′)(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)
이다.
따라서 f↑f′ 는 0≤(f↑f′)(u,v)≤c(u,v)로, 흐름의 첫 번째 성질을 만족한다.
다음으로는 f↑f′가 흐름의 두 번째 성질(흐름 보존)을 만족하면서 ∣f↑f′∣=∣f∣+∣f′∣임을 보이자.
모든 u∈V에 대해 다음이 성립한다.
v∈V∑(f↑f′)(u,v)−v∈V∑(f↑f′)(v,u)=v∈V∑f(u,v)−v∈V∑f(v,u)+v∈V∑f′(u,v)−v∈V∑f′(v,u)
이를 증명하기 위해, 어떤 고정된 정점 u에 대해 다음과 같이 두 집합을 정의해보자.
Vl(u)={v:(u,v)∈E}Ve(u)={v:(v,u)∈E}
G에 간선 (u,v)와 (v,u)가 함께 있는 경우가 없기 때문에, Vl(u)∩Ve(u)=∅이고, Vl(u)∪Ve(u)⊆V다.
이전에 나온 항등식을 다시 보자.
(f↑f′)(u,v)={f(u,v)+f′(u,v)−f′(v,u)0if (u,v)∈E,otherwise.
(f↑f′)(u,v)가 양수가 되는 경우는 (u,v)∈E일 때 밖에 없다. 반대로, (f↑f′)(v,e)가 양수가 되는 경우는 (v,u)∈E일 때 밖에 없다. (각각 그 외의 경우는 모두 0이므로)
따라서 위 항등식은 다음과 같이 쓸 수 있다.
v∈V∑(f↑f′)(u,v)−v∈V∑(f↑f′)(v,u)=v∈Vl(u)∑(f↑f′)(u,v)−v∈Ve(u)∑(f↑f′)(v,u)=v∈Vl(u)∑(f(u,v)+f′(u,v)−f′(v,u))−v∈Ve(u)∑(f(v,u)+f′(v,u)−f′(u,v))=v∈Vl(u)∑f(u,v)−v∈Ve(u)∑f(v,u)+v∈Vl(u)∑f′(u,v)+v∈Ve(u)∑f′(u,v)−v∈Vl(u)∑f′(v,u)−v∈Ve(u)∑f′(v,u)=v∈Vl(u)∑f(u,v)−v∈Ve(u)∑f(v,u)+v∈Vl(u)∪Ve(u)∑f′(u,v)−v∈Vl(u)∪Ve(u)∑f′(v,u)=v∈V∑f(u,v)−v∈V∑f(v,u)+v∈V∑f′(u,v)−v∈V∑f′(v,u)
이제 u=s라 하자. 아래와 같이 ∣f↑f′∣=∣f∣+∣f′∣임을 증명할 수 있다.
∣f↑f′∣=v∈V∑(f↑f′)(s,v)−v∈V∑(f↑f′)(v,s)=v∈V∑f(s,v)−v∈V∑f(v,s)+v∈V∑f′(s,v)−v∈V∑f′(v,s)=∣f∣+∣f′∣
또한 위 항등식을 정리하면 모든 u∈V−{s,t}에 대해 다음이 성립함도 증명할 수 있다.
v∈V∑f(u,v)v∈V∑f′(u,v)∴v∈V∑(f↑f′)(u,v)=v∈V∑f(v,u)=v∈V∑f′(v,u)=vinV∑(f↑f′)(v,u).(G에서의 흐름 보존)(G′의 흐름은 G의 흐름과 같은 성질을 가짐)(f↑f′의 G에서의 흐름 보존)
(2) Augmenting paths
유량 네트워크 G=(V,E)와 흐름 f가 주어졌을 때, 증가 경로(augmenting path) p는 잔여 네트워크 Gf의, s에서 t로의 단순 경로(simple path)다.
증가 경로 위의 간선 (u,v)에는 최대 cf(u,v)의 유량이 흐를 수 있으며, 이 간선들의 용량 중 최솟값을 증가 경로의 잔여 용량이라고 한다.
cf(p)=min{cf(u,v):(u,v) is in p}
Lemma 2
유량 네트워크 G=(V,E)와 흐름 f를 생각하자. p가 Gf의 증가 경로라 할 때, fp:V×V→R를 다음과 같이 정의하면, fp는 ∣fp∣=cf(p)>0인 Gf의 흐름이다.
fp(u,v)={cf(p)0if (u,v) is on p,otherwise.
fp(u,v)≤cf(p)≤cf(u,v)이므로 용량 제한은 만족한다(증가 경로의 잔여 용량).
p가 잔여 네트워크 Gf의, s에서 t로의 단순 경로이기에, s,t를 제외한 정점들로 들어오는 흐름은 정점을 지나 동일한 양으로 그대로 흘러나가게 되므로 흐름 보존도 만족된다.
u=s인 경우를 보면, p가 s에서 t로의 단순 경로이기에, s에서 나가는 간선은 fp(s,v)=cf(p)를 유량으로 갖는 간선 하나 뿐이고, s로 들어오는 간선은 존재하지 않는다. 따라서 ∑v∈Vfp(s,v)−∑v∈Vfp(v,s)=cf(p)−0=cf(p)이다.
Corollary 1
G=(V,E)가 유량 네트워크고, f를 G의 흐름, p는 Gf에서의 증가 경로라 하자. fp가 위에 정의된 것과 같고, f가 fp만큼 증가하는 경우, 함수 f↑fp는 값 ∣f↑fp∣=∣f∣+∣fp∣>∣f∣을 가지는 G의 흐름이다.
pf. Lemma 1과 2.
(3) Cuts of flow networks
포드-풀커슨 방법은 더 이상 증가 경로를 찾을 수 없을 때까지 증가 경로를 찾아 유량을 흘려보내는 방법을 사용하는데, 그렇다면 이 과정이 모두 종료됐을 때 최대 유량을 찾을 수 있음이 보장될까?
최대 유량-최소 컷 정리(max-flow min-cut theorem)에 따르면 유량 네트워크의 유량이 최대라는 것은 잔여 네트워크에 더 이상 증가 경로가 없다는 것과 동치가 된다.
이를 알아보기 위해 컷(cut)에 대해 알아보자.
유량 네트워크 G=(V,E)의 컷 (S,T)는 정점 집합 V를 s∈S, t∈T인 두 개의 집합 S와 T로 분할한 것이다.
f가 흐름일 때, S와 T를 가로지르는 net flow f(S,T)는 다음과 같이 정의된다.
f(S,T)=u∈S∑v∈T∑f(u,v)−u∈S∑v∈T∑f(v,u)
이때 컷 (S,T)의 용량은 다음과 같이 정의된다.
c(S,T)=u∈S∑v∈T∑c(u,v)
앞서 봤던 네트워크를 이렇게 잘라보자. S={s,v1,v2},T={v3,v4,t}가 되도록 잘랐다.
이때 f(S,T)=8+0+3=11 , c(S,T)=8+10+3=21이다.
네트워크의 최소 컷(minimum cut)은 네트워크의 모든 컷들 중 최소의 용량을 가지는 것을 말한다.
위 네트워크의 경우, 이렇게 c(S,T)=11이 되도록 분할할 수 있고, 이것이 최소 컷이 된다.
Lemma 3
f가 소스 s, 싱크 t를 가지는 유량 네트워크 G의 흐름일 때, G의 임의의 컷 (S,T)에 대해 (S,T)를 가로지르는 net flow는 f(S,T)=∣f∣다.
pf.
G의 임의의 u∈V−{s,t}에 대해, 흐름 보존이 만족되므로 ∣f∣는 다음과 같이 쓸 수 있다. 뒤쪽 괄호 안이 모두 0이 되기 때문이다.
∣f∣=v∈V∑f(s,v)−v∈V∑f(v,s)+u∈S−{s}∑(v∈V∑f(u,v)−v∈V∑f(v,u))
위 항등식을 전개하고 다시 묶으면 다음을 얻을 수 있다.
∣f∣=v∈V∑f(s,v)−v∈V∑f(v,s)+u∈S−{s}∑(v∈V∑f(u,v)−v∈V∑f(v,u))=v∈V∑f(s,v)−v∈V∑f(v,s)+u∈S−{s}∑v∈V∑f(u,v)−u∈S−{s}∑v∈V∑f(v,u)=v∈V∑(f(s,v)+u∈S−{s}∑f(u,v))−v∈V∑(f(v,s)+u∈S−{s}∑f(v,u))=v∈V∑u∈S∑f(u,v)−v∈V∑u∈S∑f(v,u)
V=S∪T이고 S∩T=∅이므로 각 ∑v∈V는 ∑v∈S와∑v∈T의 합으로 나타낼 수 있다.
∣f∣=v∈V∑u∈S∑f(u,v)−v∈V∑u∈S∑f(v,u)=v∈S∑u∈S∑f(u,v)+v∈T∑u∈S∑f(u,v)−v∈S∑u∈S∑f(v,u)−v∈T∑u∈S∑f(v,u)=(v∈S∑u∈S∑f(u,v)−v∈S∑u∈S∑f(v,u))+v∈T∑u∈S∑f(u,v)−v∈T∑u∈S∑f(v,u)=(0)+v∈T∑u∈S∑f(u,v)−v∈T∑u∈S∑f(v,u)=v∈T∑u∈S∑f(u,v)−v∈T∑u∈S∑f(v,u)=f(S,T)
Corollary 2
네트워크 G의 임의의 흐름 f의 값은 G의 임의의 컷의 용량을 초과하지 못한다.
pf.
(S,T)를 G의 임의의 컷, f를 임의의 흐름이라 하자. Lemma 4와 용량 제한으로 인해
∣f∣=f(S,T)=u∈S∑v∈T∑f(u,v)−u∈S∑v∈T∑f(v,u)≤u∈S∑v∈T∑f(u,v)≤u∈S∑v∈T∑c(u,v)=c(S,T)
가 성립한다.
다만 이 따름정리는 ∣f∣의 상한이 c(S,T)라고 말할 뿐이고, 아래의 최대 유량 최소 컷 정리에 따르면 사실 최대 유량은 최소 컷의 용량과 동일하다.
최대 유량 최소 컷 정리(Max-flow Min-cut Theorem)
f가 소스 s, 싱크 t를 가지는 유량 네트워크 G=(V,E)의 흐름이라 하자. 다음의 세 조건은 서로 동치다.
1. f가 G의 최대 유량이다.
2. 잔여 네트워크에 Gf 증가 경로가 존재하지 않는다.
3. G의 어떤 컷 (S,T)에 대해, ∣f∣=c(S,T) 다.
pf.(1)⇒(2): f가 G의 최대 유량인데 Gf에 증가 경로 p가 존재한다고 하자. 만약 그렇다면 Corollary 1에 따라 G에는 ∣f↑fp∣>∣f∣인 유량이 흐를 수 있다. f가 G의 최대 유량이라는 가정과 모순이므로 f가 최대 유량이면 Gf에 증가 경로는 존재하지 않는다.
(2)⇒(3): Gf에 증가 경로가 없다고 하고, 다음과 같이 집합 S,T를 정의하자.
ST={v∈V:Gf에 s에서 v로의 경로가 존재}=V−S
Gf에 증가 경로가 없으므로 t∈S고, 따라서 t∈T다.
u∈S,v∈T인 두 정점에 대해, (u,v)∈E가 있을 때, f(u,v)=c(u,v)다. 만약 f(u,v)<c(u,v)라면 남은 용량이 있어 (u,v)∈Ef가 되어 증가 경로에 포함되고, s에서 v로의 경로가 존재하기 때문이다.
만약 (v,u)∈E라면 f(v,u)=0이 되어야 한다. 그렇지 않으면 cf(u,v)=f(v,u)가 되어 (u,v)∈Ef가 되고, 마찬가지로 v∈S가 되기 때문이다.
따라서 다음과 같이 쓸 수 있다.
f(S,T)=u∈S∑v∈T∑f(u,v)−u∈S∑v∈T∑f(v,u)=u∈S∑v∈T∑c(u,v)−u∈S∑v∈T∑0=c(S,T)
Lemma 3에 따라 ∣f∣=f(S,T)=c(S,T)이다.
(3)⇒(1): Corollary 2에 따르면 임의의 컷 (S,T)에 대해 ∣f∣≤c(S,T)다. 따라서 어떤 컷에 대해 ∣f∣=c(S,T)가 되는 것은 이 f가 최대 유량이라는 말이다.
5. 기본 Ford-Fulkerson
포드-풀커슨 방법에서는 반복적으로 증가 경로 p를 찾고, 이를 통해 유량 f를 값 ∣f∣+∣fp∣를 갖는 f↑fp로 바꾼다.
FORD-FULKERSON(G, s, t)
for each edge (u,v)∈G.E
(u,v).f=0
while there exists a path p from s to t in the residual network Gf
cf(p)=min{cf(u,v):(u,v) is in p}
for each edge (u,v) in p
if (u,v)∈G.E
(u,v).f=(u,v).f+cf(p)
else (v,u).f=(v.u).f−cf(p)
return f
일단 모든 간선의 흐름을 0으로 초기화한 후, 잔여 네트워크 Gf에서 증가 경로를 찾는다. 증가 경로를 찾았다면 경로의 잔여 용량만큼 흐름을 추가로 흘려 보내주는데, 이때 간선이 E에 존재한다면 순방향이므로 흐름을 더해주고, 그렇지 않은 경우네는 역방향이므로 흐름을 빼준다.
더 이상 증가 경로를 찾을 수 없는 경우, 최대 유량을 찾은 것임을 증명했으므로 최대 유량인 f를 반환한다.
포드 풀커슨 방법에 대한 분석은 다음 글에