Maximum Flow & Max-flow Min-cut
Updated:
Maximum Flow
최대 유량 문제(Maximum Flow)는 방향 그래프에서 각 간선의 용량이 정해져 있을 때, 정해진 출발점(source)에서 도착점(sink)까지 보낼 수 있는 최대의 유량을 계산하는 문제이다.
유량 그래프(Flow Network)와 유량 그래프에서 흐르는 유량(Flow)의 예시는 다음과 같다.
유한 그래프는 무한한 양의 물이 흘러들어오는 정점 s(source)와 무한한 양의 물을 받아낼 수 있는 정점 t(sink)가 있고 각 파이프에는 물이 흐르는 방향과 흘릴 수 있는 용량이 정해져 있다. 간선에 적힌 a/b에서 b가 용량, a가 현재 유량이다.
위 그림의 경우 $s \to a \to b \to t$경로로 2, $s \to a \to t$경로로 1, $s \to e \to t$경로로 4, $s \to c \to d \to t$경로로 4의 유량이 흐르며 총 유량이 11이다. 최소 1의 유량이 흐를 수 있는 source에서 sink로의 경로를 증가 경로(Augmented Path)라고 하는데, 위 그림에서는 더 이상의 증가 경로가 없다.
Residual Graph
포드-풀커슨 알고리즘은 증가 경로가 나오지 않을 때까지 유량을 greedy 방법으로 흘려주는 방식이다.
초기 그래프에서 DFS를 적용하여 증가 경로 $s \to a \to e \to t$를 찾았다고 하자. 간선 $s \to a$는 3, 간선 $a \to e$는 5, 간선 $e \to t$는 4의 용량을 가지고 있으므로, 이 증가 경로를 통해서는 최솟값인 3의 유량이 최대로 흐를 수 있다.
간선 $s \to a$의 유량이 최대가 되었으므로 증가 경로는 더 이상 간선 $s \to a$를 포함할 수 없다. 이후 간선 $s \to c$을 사용하는 증가 경로인 $s \to c \to d \to t$를 찾았고 최대 유량인 4를 흘려주었다.
마지막으로 간선 $s \to e$를 포함하는 증가 경로인 $s \to e \to t$를 찾았고, $e \to t$에 이미 유량 3이 흐르고 있으므로 최대 1까지만 더 흘려줄 수 있다.
이렇게 구한 증가 경로들의 총 유량은 8인데 앞서 보았듯이 최대 유량은 11이다. greedy 방법대로 증가 경로를 찾았지만 최대 유량을 찾지 못했는데 이를 해결하기 위해 잔여 그래프(Residual Graph)가 사용된다.
잔여 그래프는 유량 그래프에서 이미 어떠한 유량이 흐른 뒤, 앞으로 더 흘릴 수 있는 남은 용량만 고려해서 만든 그래프로, 실제로는 남은 용량만 고려하지 않고, 기존의 간선과 반대 방향인 가상의 간선을 추가한다. 만약 기존의 간선에 유량 n이 흐르고 있었다면, 반대 방향의 간선으로 유량 -n이 흐른다고 판단하며, 이렇게 하여 반대 방향의 간선에 n만큼의 여유 용량이 생기므로 해당 간선에 유량을 흘려 줄 수 있다.
왼쪽이 기존의 유량 그래프라면, 잔여 그래프는 오른쪽과 같다. a에서 b로 가는 파이프의 용량이 C이고 그 중 이미 F만큼 흐르고 있다고 하면, a에서 b로 가는 파이프는 아직 C-F만큼의 용량이 남았으니 이를 잔여 그래프로 만든다. 또한 b에서 a로 가는 가상의 파이프를 만들고 a에서 b로 C만큼 흐른다고 하면, 반대 방향으로 -C만큼 유량이 흐른다 판단하여 b에서 a로 가상의 파이프를 통해 C만큼의 유량을 흘려줄 수 있다.
잔여 그래프를 통해 반대 방향의 간선에 유량을 흘릴 수 있다는 것은 기존 간선에 있던 유량을 취소하고 우회한다는 것과 같은 의미이다. 따라서 앞서 greedy 방법을 사용했을 때 해결되지 않은 최대 유량이 반대 방향의 간선을 설정해 줌으로써 해결할 수 있다. 이것이 포드-풀커슨 알고리즘의 가장 중요한 부분이다.
포드-풀커슨 알고리즘의 시간 복잡도를 따지기 위해 위 예시를 들어보면 DFS로 경로를 찾을 때 $s \to a \to b \to t$를 먼저 찾는다. 여기에 유량 1을 흘려주고 다음으로 $s \to b \to a \to t$ 경로를 찾는다. 간선 $b \to a$의 용량은 0이고, 유량은 -1이므로 잔여 그래프를 통해 최대 1의 유량을 흘려줄 수 있다. 이 두번의 시행 후 그래프는 오른쪽과 같다. 이 방법대로 계속하면 최대 유량인 $99+99=198$번의 시행 후에야 최대 유량을 찾을 수 있다. 따라서 DFS로 증가 경로를 찾으면 시간 복잡도 $O(Ef)$ (E: 간선의 수, f: 최대 유량)이 된다.
시간 복잡도가 큰 문제를 해결하기 위해선 DFS만 BFS로 바꾸면 된다. BFS로 증가 경로를 찾으면 시간 복잡도가 $O(VE^2)$로 단축되고, 이를 에드몬드-카프 알고리즘이라 한다.
Max-flow Min-cut
Cut
컷(cut)이란 source에서 sink로 가는 경로를 완전히 없애기 위해서 잘라내야 하는 간선들을 의미한다.
자른 간선을 회색으로 표현하면 왼쪽은 cut이 올바르게 된 경우지만 오른쪽은 아니다. s-t컷의 크기는 잘라낸 간선의 가중치 합으로 정의된다. 최소 컷은 자연스럽게 s-t컷의 크기가 가장 작은, 즉 가중치 합이 가장 작은 경우가 된다.
Min-cut
최대 유량 최소 컷(Max-flow Min-cut) 정리는 임의의 유량 그래프에 대해, 최대 유량의 크기와 최소 컷의 크기가 동일하다는 정리이다.
최대 유량과 최소 컷의 관계에 대해 생각해보면, 앞서 최대 유량(Maximum Flow) 문제에서 알아보았듯이 최대 유량은 잔여 그래프상 s에서 t로 가는 경로가 없다. 이는 s-t컷이 이루어졌다는 의미이기도 한다.
최소 컷은 기본적으로 그래프를 두 부분으로 나누기 때문에, 이 두 부분을 각각 집합으로 관리한다. 엄밀히 말하면 집합 $S$를 s에 도달 가능한 정점들의 집합으로 정의하고, 집합 $T$를 t로 갈 수 있는 정점들의 집합으로 정의한다. 만약 두 집합에 모두 들어가지 않는 정점이 있다면, 아무렇게나 추가해줘도 된다.
만약 간선을 올바르게 잘라서 컷을 제대로 만들었다면, $S$와 $T$의 교집합이 없어야 한다. 만약 교집합이 있다면, 그 교집합에 속한 정점 $v$에 대해 $S \to v \to T$의 경로가 만들어지므로 올바른 컷이 아니게 된다.
유량은 s에서 t까지 흘러야 하는데, s에서 t로 가기 위해서는 반드시 $S$에서 $T$로 가는 간선을 지날 수밖에 없다. 따라서 최대 유량의 크기는 $S$에서 $T$로 가는 간선의 용량의 합을 넘을 수 없다. 따라서 최대 유량의 크기는 임의의 s-t컷의 크기보다 작거나 같아야 한다. 이는 최대 유량의 크기가 최소 컷보다 작거나 같음을 의미한다.
하지만 작거나 같음으로 설명이 되지는 않는다. 우리가 보여하는 것은 최소 컷이 최대 유량과 정확히 같다는 것이다. 따라서 최소 컷을 기준으로 한 분석뿐만 아니라 최대 유량을 기준으로 한 분석도 해봐야 한다.
최대 유량의 경우 잔여 그래프를 보는 것이 일반적이다. 최대 유량의 잔여 그래프에는 s에서 t로 가는 경로가 존재하지 않는다. 따라서 최대 유량을 토대로 최소 컷을 만들 수 있다.
잔여 그래프 기준 s에서 도달 가능한 정점과 t로 도달 가능한 정점들을 각각 $S$, $T$로 모은다. 최소 컷과 마찬가지로 두 경우 모두 해당되지 않는 정점이 있다면 아무렇게나 넣는다. 아래 예시는 정점 a를 임의로 $S$에 넣었다.
이제 원래 그래프에서 $S$에서 $T$로 가는 파이프를 생각해보면, 만약 $S$의 정점 v에서 $T$의 정점 w로 가는 파이프의 용량이 남는다면, 이는 잔여 그래프에서 $S \to v \to w \to T$라는 경로를 만들어낼 수 있고, 이는 최대 유량이라는 가정에 위배된다. 따라서 원래 그래프에서 $S$에서 $T$로 가는 모든 파이프들은 용량이 꽉 찬 상태여야 한다.
다음으로 $T$에서 $S$로 가는 파이프를 생각해보면 만약 w에서 v로 가는 파이프에 물이 조금이라도 흐른다면, 잔여 그래프에서 반대 방향으로 가상의 파이프가 생기므로 $S \to v \to w \to T$경로가 생긴다. 이 역시 최대 유량 가정에 위배된다.
최종적으로 모든 물은 s에서 출발해서 t로 흘러가며, t에서 s로 흐르는 물은 존재하지 않는다. 그런데 $S$에서 $T$로 가는 파이프는 모두 꽉 찬 상태이므로, $S$에서 $T$로 가는 파이프의 용량 합이 곧 최대 유량이 된다. 또한, 이때 $S$에서 $T$로 가는 파이프를 모두 끊으면, 올바른 컷을 만들어낼 수 있다. 즉, 최대 유량은 어떤한 컷과 동일한 크기를 가지는데, 최대 유량의 크기는 최소 컷의 크기보다 작거나 같아야 하니, 두 결론을 합치면 최대 유량은 최소 컷과 동일한 크기를 가져야 한다는 결론을 얻을 수 있다.
최대 유량 최소 컷 구현 코드는 다음과 같다.
int Max_Flow(int s, int e){
int min_cut = 0;
while(1){
queue<int> q;
q.push(s);
memset(pre, -1, sizeof(pre));
while(!q.empty()){ //bfs
int cur = q.front();
q.pop();
for(int i=0; i<line[cur].size(); i++){
int next = line[cur][i];
if(capacity[cur][next]-flow[cur][next]>0 && pre[next]==-1){
q.push(next);
pre[next] = cur;
if(next==e) break;
}
}
}
if(pre[e]==-1) break;
int maxflow = INT_MAX;
for(int i=e; i!=s; i=pre[i]) maxflow=min(maxflow, capacity[pre[i]][i]-flow[pre[i]][i]);
for(int i=e; i!=s; i=pre[i]){
flow[pre[i]][i] += maxflow;
flow[i][pre[i]] -= maxflow;
}
min_cut += maxflow;
}
return min_cut;
}
Vertex split
최소 컷 문제를 해결하다 보면 최대 유량 기준으로 간선이 아니라 정점을 컷해야 하는 경우도 있다. 정점 분할이란 정점에도 간선처럼 가중치를 주기 위해 정점을 하나의 간선으로 만드는 기법이다. 이때 정점을 간선처럼 취급하기 위해 정점을 두 개의 정점(in과 out)으로 분할한다. in 정점은 해당 정점으로 들어오는 간선들과 연결해주고, out 정점은 해당 정점에서 다른 정점으로 나가는 간선을 연결해준다.
정점 분할도 마찬가지로 간선의 역방향으로 유량 0의 가상의 간선이 있다. 정점 u와 v의 양방향 간선이 있는 경우 정점 분할 시 다음과 같이 표현된다.
코드로 구현하면 다음과 같다.
struct Edge{
int u, v, cap, flow;
Edge* rev;
Edge(int _u, int _v, int _c) : u(_u), v(_v), cap(_c), flow(0) {}
int Residual() const{
return cap-flow;
}
void AddFlow(int amount){
flow+=amount;
rev->flow-=amount;
}
};
정점 분할을 위한 구조체를 설정한다. 현재 정점 u, 목적지 정점 v와 capacity를 입력받고 역방향 가상 간선을 위한 rev를 정의한다. residual은 현재 잔여 용량을 반환하고 AddFlow는 u에서 v로 흐름이 발생할 때 flow를 추가해준다.
vector<Edge*> line[25000];
void AddLine(int source, int sink, int capacity){
Edge* E=new Edge(source, sink, capacity);
Edge* revE=new Edge(sink, source, 0);
E->rev=revE;
revE->rev=E;
line[source].push_back(E);
line[sink].push_back(revE);
}
정점인 Edge 구조체를 기반으로 간선을 생성한다. 간선에서 이동하는 방향은 capacity만큼의 용량을 주고 역방향 간선은 0을 준다.
AddLine(n*2, n*2+1, 1); //vertex split [in] -> [out]
정점 분할의 예시이다. 정점을 in out으로 분할하기 때문에, 기존 정점의 수에서 2배의 용량이 필요하다. 따라서 각 정점의 인덱스를 현재 정점이 n이라 할 때 in out을 각각 in: n*2, out: n*2+1로 설정한다.
AddLine(u*2+1, v*2, inf); //u [out] -> v [in]
AddLine(v*2+1, u*2, inf); //v [out] -> u [in]
간선 연결의 예시이다. 양방향 연결이라고 하면, 앞서 그림처럼 u의 out인 u*2+1에서 v의 in인 v*2로 연결해주고, v의 out인 v*2+1에서 u의 in인 u*2로도 연결해준다.
Reference
- Maximum Flow: https://unorderedmap.tistory.com/6
- Max-flow Min-cut: 공군 휴머니스트 air-wiki
- Vertex split: https://everenew.tistory.com/179
Leave a comment