[그래프] Graph 11: 네트워크 유량(Network flow) : 포드-풀커슨 알고리즘

1. 그래프의 용량(Network Flow)

 

네트워크를 이용해 아주 큰 파일을 다운로드하는 중이라고 하자.

 

이렇게 존송받을 자료의 양이 많을 때 관심을 갖는 부분은 서버가 보낸 패킷이 내 컴퓨터에 몇 밀리초 만에 도착하느냐가 아니라

 

1초에 몇 MB의 자료를 전송받을 수 있느냐이다.

 

네트워크를 구성하는 케이블들에는 일정한 대역폭이 있기 때문에, 단위 시간당 일정량 이상의 자료를 전송할 수 없다.

 

따라서 패킷을 여러 경로로 나누어 보내 그 중 일부가 좀더 먼 길을 돌아오더라도 초당 10MB를 전송받는 것이 훨씬 이득이다.

 

 

이렇게 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 '흐름' 혹은 '유량'을 보낼 수 있는지를 계산하는 문제를 네트워크 유량 문제(Network Flow)라고한다.

 

네트워크 유량은 굉장히 강력한 최적화 문제로, 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는 데도 이용할 수 있다.

 

 

 

2. 유량 네트워크 (flow network)

 

유량 네트워크(flow network):

    각 간선에 용량이라는 추가 속성이 존재하는 방향 그래프(파이프 역활)

   

 

정점 u에서 v로 가는 간선의 용량을 c(u, v), 실제 흐르는 유량을 f(u, v)라고 쓸 때,

네트워크의 유량은 항상 다음 세가지 속성을 만족한다.

 

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

    가장 자명한 속성으로, 각 간선의 유량은 해당 간선의 용량을 초과할 수 없다.

 

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

    u에서 v로 유량이 흘러올 경우, v의 입장에서는 u로 음수의 유량을 보내는 것이라고 생각함

 

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

    각 정점에 들어오는 유량과 나가는 유량의 양은 정확히 같아야 함을 나타낸다.

    유량의 대칭성에 의해 정점에 들어오는 유량은 모두 음수로 표현되므로

    한 정점에서 다른 모든 정점에 보내는 유량을 합하면 모두 0 이 되어야한다.

 

 

 

유량 네트워크에는 항상 특수한 두 정점 소스(source)와 싱크(sink)가 존재한다.

 

소스는 유량이 시작되는 정점이며

 

싱크는 유량이 도착하는 정점이다.

 

따라서 이 두 정점에서는 유량의 보존 속성은 성립하지 않는다.

 

하지만 다른 모든 정점에 유량의 보존 속성이 성립해야 하기 때문에,

 

소스에서 나온 모든 유량은 결국 싱크로 들어가게 된다.

 

 

네트워크 유량 문제는 이렇게 소스와 싱크 사이에 흐를 수 있는 최대 유량을 계산하는 문제이다.

 

 

3. 포드-풀커슨 알고리즘(Ford-Fulkerson algorithm)

 

네트워크 유량 문제를 해결하는 가장 기초적인 방법이다.

 

이 알고리즘은 최초로 고안된 네트워크 유량 알고리즘으로 그 개념과 구현이 비교적 간단하다.

 

이보다 빠른 알고리즘도 존재하지만 프로그래밍 대회에 출제되는 규모의 문제를 푸는 데는 큰 문제가 없다.

 

 

동작원리

 

 

유량 네트워크의 모든 간선의 유량을 0으로 두고 시작한다.

 

 

 

 

소스에서 싱크로 유량을 더 보낼 수 있는 경로를 찾아 유량을 보내기를 반복한다.

 

이렇게 유량을 보내는 경로를 증가 경로(augmenting path)라고 부른다.

 

 

 

경로를 따라 유량을 보낼 수 있으려면 각 간선에 이미 흐르고 있는 유량 외에 추가로 유량을 보낼 수 있는 여유 용량이 있어야한다.

 

용량이 10인 간선에 이미 4만큼 유량이 흐르고 있다면, 더 흘려 보낼 수 있는 유량의 양은 6이다.

 

간선의 용량과 유량의 차이를 잔여 용량(residual capacity)라고 부르기도 한다.

 

전여 용량 r(u, v) 는 다음과 같다.

 

r(u, v) = c(u, v) - f(u, v)

 

 

증가 경로를 통해 흘려보낼 수 있는 유량의 최대량은, 포함된 간선의 잔여 용량 중 가장 작은 값으로 결정된다.

(위의 그림에서 0-1-3 에서 1-3은 2의 유량을 더 보낼 수 있지만 0-1로는 1의 유량만 보낼 수 있으므로 0-1-3은 최대 1의 유량만 보낼 수 있다.)

 

포드 폴커슨 알고리즘은 이와 같은 증가 경로가 더 이상 존재하지 않을 때까지 증가 경로를 찾고,

 

보낼 수 있는 최대 유량을 해당 경로를 따라 보내는 작업을 반복한다.

 

이 증가 경로를 찾는 과정은 그래프의 탐색 알고리즘을 이용하면 쉽게 구현할 수 있다.

 

하지만 위 방법대로라면 어떤 증가 경로를 선택하느냐에 따라 최대 유량을 찾을 수 없는 경우가 생긴다.

(위 그림에서 만약 0-1-2-3 를 선택했을때 0-2-3로 유량을 다시 보낼 수 없게 된다.)

 

 

문제 해결

유량의 대칭성으로 위 문제를 해결 할 수 있다.

 

2에서 1로 가는 간선은 없으므로 해당 간선의 용량 c(2, 1)는 0이 되지만

 

유량의 대칭성에 의하면 유량 f(2, 1)는 -1이 된다.

 

따라서 잔여 용량을 계산하면 r(2, 1) = c(2, 1) - f(2, 1) = 0 - (-1) = 1 이 된다.

 

 

2에서 1로 1만큼 유량을 보낼 수 있다는 것이다.

 

실제로 존재하지도 않는 간선으로 유량을 보낼 수 있는 이유는 

 

유량을 줄이는 것은 상대에게 유량을 보내주는 것과 같은 효과를 갖기 때문이다.

(다시 돌려줌)

 

이와 같은 속성은 두 정점이 서로 상대에게 유량을 보내 주는 것은 의미가 없기 때문에 성립한다.

따라서 0-2에 1의 유량을 보내고 2-1에 1의 유량을 보내면 1-3에 1의 유량을 보낼 수 있게 된다.

 

이때 1-2 와 2-1은 서로 상쇄되서 없애 버릴 수 있다.

 

결과적으로 유량 네트워크의 세 속성은 그대로 성립하며 소스에서 싱크로 가는 총 유량도 변하지 않기 때문에

 

최대 유량을 찾는 데 아무런 영향 없다.

 

따라서 새 유량을 보내는 것과 기존의 유량을 상쇄하는 것은 사실상 같은 연산이라고 할 수 있다.

 

 

4. 포드-풀커슨 알고리즘 구현(에드몬드-카프 알고리즘)

잔여 용량이 남은 간선들만을 사용하는 너비 우선 탐색을 이용해 증가 경로를 찾고,

 

이를 따라 유량을 보내는 일을 더 이상 증가 경로가 없을 때까지 반복한다.

 

networkFlow()는 각 간선의 용량을 나타내는 capacity[][]가 주어질 때,

 

네트워크를 따라 source에서 sink로 흘러보낼 수 있는 최대 유량을 반환한다.

 

이 때 각 간선을 따라 흐르는 유량은 flow[][]에 저장된다.

 

 

networkFlow()의 내부는 커다란 무한 반복문으로 구성된다

 

이 반복문 내부에서는 우선 잔여 용량이 남아 있는 간선만을 이용해 bfs를 수행한다.

 

소스에서 싱크까지의 경로를 찾아냈다면 각 간선을 검사하며 그 중 최소 잔여 용량을 찾는다.

 

이것이 이 경로를 따라 보낼 수 있는 최대 유량이 된다.

 

그 후에는 각 간선의 유량을 갱신하는데, 유량의 대칭성을 유지하기 위해 한 방향의 유량을 늘리면 다른 방향의 유량은 줄여야한다.

 

 

 
const int MAX_V = 10;
const int INF = 987654321;
int V;
 
int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V];
 
int networkFlow(int source, int sink)
{
    memset(flow, 0, sizeof(flow));
    int totalFlow = 0;
    while(true)
    {
        vector<int> parent(MAX_V, -1);
        queue<int> q;
        parent[source] = source;
        q.push(source);
        while(!q.empty() && parent[sink] == -1)
        {
            int here = q.front(); q.pop();
            for(int there = 0; there < V; there++)
            {
                if(capacity[here][there] - flow[here][there] > 0 && parent[there] == -1)
                {
                    q.push(there);
                    parent[there] = here;
                }
            }
        }
        if(parent[sink] == -1) break;
        int amount = INF;
        for(int p = sink; p != source; p = parent[p])
            amount = min(capacity[parent[p]][p] - flow[parent[p]][p], amount);
        for(int p = sink; p != source; p = parent[p]) 
        {
            flow[parent[p]][p] += amount;
            flow[p][parent[p]] -= amount;
        }
        totalFlow += amount;
    }
    return totalFlow;
}

 

 

5. 정당성의 증명과 최소 컷 최대 유량 정리(Min-cut Max-flow Theorem)

최대 유량을 구하는 것이니, 유량을 보낼 수 있는 한 최대로 보내야한다.

 

하지만, 증가 경로가 여러 개인 경우 그중 아무것이나 택해도 괜찮은지,

 

증가 경로를 잘못 택할 경우, 최대 유량을 찾기 전에 막혀서 더 증가 경로를 찾지 못하게 되는 일이 없는지

 

이와 같은 경우가 없다는 것을 증명하는 정리가 바로 최소 컷 최대 유랑 정리이다.

 

이 정리는 포드-풀커슨 알고리즘의 정당성을 보이는 것만이 아니라 최대 유량 문제와 최소 컷 문제가 밀접하게 연관되어 있음을 보이기 때문에 중요하다.

빨간 원 = S / 나머지 점 = T

 

컷(cut): 소스와 싱크가 각각 다른 집합에 속하도록 그래프의 정점들을 두 개의 집합으로 나눈 것이다.

S: 이때 소스가 속한 집합 ( 위 그림에서 원 내부의 점들 )

T: 이때 싱크속에 속한 집합 ( 위 그림에서 원 외부의 점들 )

 

S에서 T로 가는 간선들의 용량 합을   컷 S, T의 용량이라고 정의하고, (위 그림에서 20 + 7 + 8 = 35)

S에서 T로 실제로 보내는 총 유량을   컷 S, T의 유량이라고 정의한다. (위 그림에서 13 + 0 - 3 + 7 = 17)

 

컷의 유량은 s에서 t로 보내는 총 유량이기 때문에, T에서 S 로 흘러오는 (c, b)의 간선의 유량은 음수로 계산된다.

 

 

모든 컷의 유량과 용량에는 다음 두 속성이 항상 성립한다.

 

1. 컷의 유량은 소스에서 싱크로 가는 총 유량과 같다 

    네트워크의 모든 유량은 S에 포함된 소스에서 흘러나와 T에 포함된 싱크로 흘러들어가기 때문이다.

    T에서 S로 흘러오는 유량은 음수로 계산되므로, 유량의 일부가 S와 T를 여러 번 오가는 경우에도 컷의 유량에는 한 번만 포함된다.

 

2. 컷의 유량은 용량과 같거나 더 작을 것이다.

    모든 간선에 대해 유량은 용량 이하의 값이기 때문

 

 

 

모든 컷의 유량은 같고, 어떤 컷에서라도 용량은 유량 이상의 값이라는 것이다.

 

이때 네트워크에서 용량이 가장 작은 컷을 찾아내는 문제를 최소 컷(Min cut) 문제라고 부른다.

 

 

 

최소 컷 문제는 최대 유량과 밀접하게 연관되어 있다.

 

만약 네트워크에 용량과 유량이 같은 컷 S', T'가 존재한다고 하자,

 

이때 S', T'는 항상 최소 컷이며, 현재 소스에서 싱크로 보내는 유량은 네트워크의 최대 유량임을 보일 수 있다.

 

S', T' 보다 용량이 작은 컷이 존재한다면 해당 컷에 대해 유량이 용량보다 크므로 모순이고,

 

이보다 많은 유량을 보내는 방법이 있을 경우 S', T'에 대해 유량이 용량보다 크므로 모순이기 때문이다.

 

 

 

최소 용량 최대 유량 정리는 증가 경로가 존재하지 않는 유량 네트워크에서 용량과 유량이 같은 컷을 찾아내는 방법을 보여준다.

 

소스에서 잔여 용량이 있는 간선을 통해 갈 수 있는 정점들의 집합 S와 그럴 수 없는 정점 T로 정점의 집합을 나누는 것이다.

 

이와 같은 분류에서 소스는 항상 S에 속할 것이고, 증가 경로가 존재하지 않기 때문에 싱크는 항상 T에 속할 것이다.

 

따라서 S, T는 유량 네트워크의 컷이 된다.

 

 

이제 S에 속한 정점에서 T에 속한 정점으로 가는 모든 간선의 잔여 용량은 0이다.

 

잔여 용량이 1이라도 있다면 반대쪽 정점 또한 S에 포함되어야 하기 때문이다.

 

이 말은 모든 간선에 대해 용량과 유량이 같다는 뜻이므로,

 

이 컷은 우리가 원하는 용량과 유량이 같은 컷이 된다.

 

 

 

포드-풀커슨 알고리즘은 유량네트워크에 증가 경로가 더 이상 존재하지 않을 때 종료하므로,

 

이 과정에서 찾아낸 유량은 네트워크의 최대 유량이 된다.

 

이렇게 최소 컷 최대 유량 정리는 포드-풀커슨 알고리즘의 정당성을 증명함과 동시에,

 

같은 알고리즘을 이용해 최소 컷 문제도 풀 수 있음을 보여준다.

 

 

 

6. 시간 복잡도와 탐색 알고리즘의 선택

networkFlow()의 무한 반복문은 증가 경로를 더 이상 찾지 못할 때까지 반복해서 수행되는데,

 

최대 유량에 도달하기 위해 증가 경로를 몇 번이나 찾아야 할지 미리 예측하기 어렵기 때문이다.

 

증가 경로를 하나 찾을 때마다 전체 유량이 최소 1만큼은 증가한다는 점을 이용하여 이를  예측할 수 있다.

 

따라서 최대 유량 f에 대해 증가 경로는 많아 봐야 f번 찾게된다.

 

 

여기에 그래프의 탐색에 드는 O(|V| + |E|)를 곱하면 전체 O(|E|f)의 시간이 걸린다.

만약 증가 경로가 항상 1-2를 지나가는 것만 발견하면..

 

이는 최대 유량이 큰 경우 느려질 가능성이 커진다.

(만약 최소 잔여 용량이 1인 경로가 있을 경우 엄청나게 말그대로 1만큼만 증가 시키기 때문에 느려진다)

 

 

하지만 위의 알고리즘은 너비 우선 탐색을 사용하기 때문에 항상 가장 짧은 증가 경로만을 찾고,

(아마 bfs 스패닝 트리의 형태 즉 부모-자식간에만 연결되어 있기 때문일 것이다, 위의 그림에서 결코 1->2 는 포함안시킴)

(dfs 일 경우 항상 1->2가 포함된다)

 

따라서 최대 유량이 큰 경우 항상 최악의 선택을 하는 일은 일어날 수 없다.

 

BFS를 이용해 구현할 경우 최대 O(|V||E|) 개의 증가 경로만을 사용해 최대 유량을 얻을 수 있다고 한다

 

따라서 위의 코드는 O(|E|f) 와 O(|V||E|^2)중 작은 것이 시간 복잡도가 된다.

 

 

 

 

7. 인접 리스트로 포드-폴커슨 알고리즘 구현하기

 

일반적인 경우 인접 리스트에서 방향 그래프를 저장할때는 각 간선의 시작점에만 해당 간선의 정보를 저장한다.

 

그러나 포드-풀커슨 알고리즘을 구현할 때는 그렇게 할 수 없다.

 

유량의 상쇄를 통해 실제 간선의 반대 방향으로도 유량을 보낼 필요가 있기 때문이다.

 

 

따라서 각 단방향 간선 (u, v)마다 용량이 0인 '유령' 간선(v, u)를 네트워크에 추가해줘야 한다.

 

이 유령 간선은 유량을 상쇄하는 데만 사용할 수 있다.

 

이때  각 간선은 자신의 반대 방향 간선에 빠르게 접근 가능해야한다.

 

한 간선의 유량을 갱신할 때 다른 한쪽 또한 갱신해야하기 때문이다.

 

 

한 가지 방법은 각 간선을 구조체로 표현하고, 각 간선이 반대 방향 간선의 포인터를 가지고 있도록 하는 것이다.

 

이와 같은 구조체의 대체적인 형태는 다음과 같다.

 

 

struct Edge {
    int target, capacity, flow;
    Edge* reverse;
    int residualCapacity() const { return capacity - flow; }
    void push(int amt) {
        flow += amt;
        recverse->flow -= amt;
    }
};
 
vector<Edge*> adj[MAX_V];
 
void addEdge(int u, int v, int capacity)
{
    Edge* uv = new Edge(), vu* = new Edge();
    
    uv->target = v;
    uv->capcity = capacity;
    uv->flow = 0;
    uv->reverse = vu;
    vu->target = u;
    vu->capacity = 0;
    vu->flow = 0;
    vu->reverse = uv;
    adj[u].push_back(uv);
    adj[v].push_back(vu);
}

 

 

 

 

 

- 알고리즘 문제해결전략 991p