네트워크 유량

네트워크 유량이란 유방향 그래프에 용량이 존재하는 것이다. 유량의 시작 정점을 Source, 끝 정점을 Sink라고 한다.
이 때, Source에서 Sink로 흘려보낼 수 있는 최대 유량(flow)을 구하는 문제를 네트워크 유량 문제라고 한다.

유량(flow) : 두 정점 사이에서 현재 흐르는 양
용량(capacity) : 두 정점 사이에 최대로 흐를수 있는 양
잔여 용량(residual capacity) : 두 정점 사이에서 현재 더 흐를 수 있는 유량. (용량 - 유량)
소스(source) : 유량이 시작되는 정점. 보통 S로 표현
싱크(sink) : 유량이 도착하는 정점. 보통 T로 표현
증가 경로(augmenting path) : S에서 T로 유량이 흐르는 경로

위 이미지와 같은 네트워크 유량이 있다고 하자.

S에서 1로 갈 수 있는 유량은 2, 2로 갈 수 있는 유량은 3이다.
S에서 1로 2만큼 유량이 흘러갔다면, 1에서 T로 용량은 3이지만 S에서 1로 흘러 들어온 2만큼만 유량을 보낼 수 있다.
마찬가지로, S에서 2로 갈 수있는 유량은 3이라 3을 흘려 보냈더라도 2에서 T로 흐를 수 있는 용량이 2라서 2만큼만 유량을 보낼 수 있다.
결과적으로 위 그래프는 S에서 T로 4를 흘러보내주게 되고, 최대 유량이 4라고 한다.

네트워크 유량 문제가 성립하기 위해서는 3가지 약속이 있다.
일단 네트워크 유량에서는 위에서" S에서 1로 갈 수 있는 유량은 2, 2로 갈 수 있는 유량은 3이다"
라는 표현을 c(S,1) = 2, c(S,2) = 3 이라고 간단하게 표현할 수 있다.

c(u,v) : capacity 정점 u에서 v로 가는 간선의 용량
f(u,v) : flow 정점 u에서 v로 실제 흐르는 유량
r(u,v) : residual 정점 u에서 v로 가는 잔여 용량 r(u,v) = c(u,v) - f(u,v)

1) 용량 제한 속성 f(u,v) <= c(u,v) :

두 간선 사이에서 흐르는 유량은 용량을 넘을 수 없다.

2) 유량의 대칭성 f(u,v) = -f(v,u) :

u->v로 2만큼 흐른다면, v->u엔 -2만큼 흐른다. 쉽게 생각하면, 'u->v로 2만큼 나가고 v->u로 2만큼 들어온다.' 라고 이해하면 된다.

3) 유량 보존의 법칙 ∑f(u,v) = 0 :

S 와 T를 제외하고는 각 정점에서 들어오는 유량과 나가는 유량이 일치해야 한다. 그래서 유량의 대칭성 때문에 S와 T를 제외하고 유량을 모두 합하면 0이 되어야 한다.

포드-풀커슨 알고리즘

최초의 네트워크 유량 알고리즘
개념과 구현이 간단하다.

개념

각 간선의 용량을 입력받는다.
DFS(포드-풀커슨)또는 BFS(에드몬드-카프)를 이용하여 r(u,v) > 0인 증가 경로를 찾는다.
찾은 증가 경로 상에서 r(u,v)이 가장 낮은 엣지를 찾는다.
잔여 용량만큼 S에서 T까지 유량을 흘려보낸다(경로의 모든 엣지에 유량 추가).
더 이상 증가 경로가 발견이 되지 않을 때까지 반복한다.

아래 그래프를 가지고 포드-풀커슨 알고리즘의 과정을 살펴 보면,

S->a->T 라는 증가 경로를 먼저 찾고, 그 다음 S->b->T라는 증가 경로를 찾아서 최대 유량을 찾을 수도 있다.

하지만, 만약 S->a->b->T라는 증가 경로를 가장 먼저 찾았는데, 이때 흘려 보낼수 있는 플로우는 1을 보내고 나니 그 다음 유량을 흘려 보낼 수 있는 루트를 찾아보니 없다.

여기서 위에서 살펴 보았던 2) 유량의 대칭성 f(u,v) = -f(v,u)의 개념이 이용된다.
현재 c(a,b)는 1이다. 그리고 c(b,a)는 경로가 존재하지 않으니 0이다.
그리고 f(a,b)도 방금 S->a->b->T 라는 증가 경로로 유량이 흘렀기 때문에 1이 되고, 유량의 대칭성에 의해서 f(b,a)은 -1이 된다.

그러면 놀랍게도 잔여 용량 r(b,a)(c(b,a) - f(b,a))은 0 - (-1)로, b에서 a로 흐르는 잔여 용량이 1이 된다.
즉, 유량을 하나 보내는 것은 반대 방향으로도 유량을 하나 보낼 수 있는 작업이 동반된다고 생각하면 된다.
이렇게 Back-Edge라고 불리는 역간선 덕분에 포드-풀커슨 알고리즘이 성립 가능하게 된다.

그러면 결과적으로는 어떤 경로를 선택하든 최대 유량을 구할 수 있다.

시간복잡도

시간복잡도는 O((V+E)F) 인데, E가 V를 도미넌트 하므로 보통 O(EF)라고 표현한다.

위와 같은 케이스가 포드-풀커슨 알고리즘의 워스트 케이스인데, 증가경로 한개당 플로우 1밖에 보낼 수 없다.
그래서 DFS를 플로우 수만큼 사용해야 하는데 플로우 수가 크다면 스택 오버플로우가 발생할 수 있다.
이러한 케이스는 BFS로 문제를 해결하는 에드먼드-카프 알고리즘에서 극복이 가능하다고 한다.

백준 6086 : 최대 유량

네트워크 유량 문제는 포드-풀커슨 알고리즘 외에도 에드먼드-카프 알고리즘, 최소컷, 이분매칭 MCMF, 디닉 알고리즘의 개념들과 그래프를 어떻게 설계해야하는지에 대한 다양한 방법들에 대한 공부가 필요하다고 합니다...

hongcheol / CS-study