네트워크 플로우(Network Flow)

---

목록

1. 네트워크 플로우(Network Flow)란?

2. 네트워크 플로우의 성질

3. 최대 유량을 구하는 알고리즘 - 에드몬드 카프 알고리즘(BFS 방식)

---

1. 네트워크 플로우(Network Flow)란?

실생활에서 퇴근길을 생각해보자.

17명의 사람들이 회사에서 X 아파트로 가야한다(의도치 않게 모두 같은 아파트에 산다). 이때 차를 타고 가는데 A, B, C, D위치를 이용하여 집으로 가야한다.

회사에서 A위치를 가는 동안은 시간당 차가 16대가 동시에 지나갈 수 있고 B위치는 3대가 동시에 지나갈 수 있다.

길이 많으니 기호로 나타내서 표현하면 다음과 같다.

(X->Y :: K 의미는 X에서 Y로 가는데 시간당 K개의 차가 동시에 지나갈 수 있다는 의미)

회사->A :: 16

회사->B :: 3

A->B :: 1

A->C :: 20

B->C :: 1

B->D :: 7

C->B :: 5

C->집 :: 10

D->집 :: 8

이를 그림으로 표현하면 다음과 같다.

이때 가장 많이 X 아파트로 도착할 수 있는 경우가 어떻게 될까?

무작위로 한번 시간당 회사에서 집으로 가는길에 몇대의 차가 갈 수 있는지 도로를 선택하여보자.

이 그림에서 X/Y의 의미는 시간당 동시에 Y대가 갈 수 있는 길에 시간당 X대가 지나가고 있다는 의미이다.

이 경우는 최종적으로 12대의 차가 시간당 회사에서 집으로 도착할 수 있게 된다.

반면에 아래와 같은 경우는 더 많은 차를 동시에 집으로 보낼 수 있게된다.

만약 그림이 이상하다 느껴진다고 하더라도 일단 계속 읽어내려가보자.

이때는 시간당 17대의 차가 회사에서 집으로 가고 있음을 볼 수 있다.

이때 네트워크 플로우(Network Flow)의 내용으로 접근하기 위해 유량 그래프(Flow Network)로 생각해본다면, 회사가 소스(Source)가 되고, 집이 싱크(Sink)가 된다.

위치A~D는 정점이 되고, 각 도로는 간선이 되는데 그 간선은 용량(Capacity)을 가지게 된다. 이때 각 간선은 파이프 같은 역할을 하고 유량을 보낼 수 있는 역할을 하게된다.

이제 유량 그래프로 그림을 나타내면 다음과 같다.

위의 2번째 그림과 3번째 그림은 유량 그래프에서 유량을 각각 보냈을 때의 모습을 보여준 것이고,

바로 위의 그림은 최대 유량을 보냈을 때의 모습을 나타낸 것이다.

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

이제, 유량 그래프에서 몇가지 공식처럼 항상 참인 내용을 확인해보자.

2. 네트워크 플로우의 성질

유량 그래프의 성질을 알아보기 전에 다시 용어를 정리하고 확인하자.

소스(S, Source) :: 시작 위치를 의미한다.

싱크(T, Sink) :: 끝 위치를 의미한다. 

정점(Vertex) :: 유량이 모이는 위치

간선(Edge) :: 유량이 흐르는 파이프 역할

용량(Capacity) :: 유량이 흐를 수 있는 크기

c(u,v) :: c는 Capacity를 의미하고, u에서 v로 흐를 수 있는 간선의 용량을 의미한다.

f(u,v) :: f는 Flow를 의미하고, u에서 v로 흐른 실제 유량을 의미한다.

1. 특정 경로를 따라 유량을 보낼 때는 그 경로에 포함된 간선 중 가장 용량이 작은 간선에 의해 결정된다.

예를들어, S->B->D->T로 경로를 지정하였다면 3, 7, 8의 용량중 가장 작은 3에 의해 항상 3만 보내게 된다.

2. 용량 제한 속성 :: f(u,v) ≤ c(u,v)

 

이 내용이 무조건 자명한 이유는 흐르는 양이 항상 그 간선의 용량을 넘을 수는 없다는 의미이다.

따라서 f(u,v) ≤ c(u,v)는 항상 자명하다.

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

이 내용은 조금 생소 할 지 모르지만, 한번 보고 나면 쉽다.

S->B로 유량이 3이 흘렀다면 B->S로는 -3이 흘렀다는 의미와 같다는 것이다.

4. 유량의 보존 :: Σf(u,v) = 0

이 말이 의미하는 것은 항상 들어오는 유량과 나가는 유량의 합은 같아야 한다는 의미이다.

만약 유량이 3이 들어왔는데 10으로 나갈 수 없다는 것이고,

10이 들어왔는데 3이 나가고 7이 머무르고 있을 수는 없다는 의미이다.

예외적인 부분이 있는데 회사와 집 즉, S(source)와 T(Sink)는 그렇지 않다.

이전부터 이상하다고 느꼈을지, 혹은 지금와서 느꼈을 지 모르겠지만 가장 위에서 두번째 그림은 유량의 보존을 만족하고 있지 않은 틀린 그림이다.

아래에 그 그림을 가져와서 보자면, 16이 흘렀는데 16과 1이 흐르며 17이 흐르고 있는 장면은 이미 틀렸고, C에서 16이 들어왔는데 6이 머물고 10만 집으로 간다는 것도 유량의 보존에 모순이다.

3. 최대 유량을 구하는 알고리즘 - 에드몬드 카프 알고리즘(BFS 방식)

이제는 유량 그래프에서 항상 최대 유량을 찾아 낼 수 있는 에드몬드 카프 알고리즘에 대해 알아보자.

원래 포드 풀커슨 알고리즘이라고 DFS방식으로 이루어지는 알고리즘이 있으나

 이 방식보다 보편적을 쓰이는 에드몬드 카프 BFS 방식(물론 이 알고리즘도 최대 유량의 기본 알고리즘이다.)으로 알아보고자 한다.

---

1) Edmonds-Karp Algorithm이 O(VE^2)인 이유

Edmonds-Karp Algorithm이 VE^2인 이유를 증명하기 위해서는, 증가 경로를 많아야 VE번 찾는다는 것을 보이면 된다. BFS 한번이 O(E)이기 때문이다. 이 사실을 보이겠다.

정의 1. 간선의 capacity == 간선에 흐른 flow 인 간선을 포화 간선이라 정의한다. 그렇지 않은 간선을 비포화 간선이라고 정의한다.

정의 2. 비포화 간선들로 이루어진 그래프를 Residual Graph라고 정의한다. 

Lemma 1. Residual Graph에서 현재의 source - sink 최단경로가 D라고 했을 때, 최단 경로를 D로 유지하는 동안 E번만 증가 경로를 찾는다. 

증명. 한번 flow를 흘리면, Residual Graph의 간선 중 최소 하나가 포화 상태로 차 버리게 된다. 포화 상태로 차게 된다면, 최단 경로가 D인 한 다시 그 간선을 보게 될 일은 없다. (역변을 타게 되면 최단 경로가 D+2 이상이 되는 고로, 그러한 경로는 찾지 않는다) 역변을 탈 일이 없으니 간선은 비포화에서 포화로만 변하고, 모든 간선이 포화로 변하면 경로가 없게 된다. 고로 최단 경로를 고정했을 때 O(E) 개의 증가 경로만을 찾는다. 

최단 경로의 길이는 V 이하이니 이러한 과정이 V번 일어난다. 고로, 많아야 VE번 증가 경로를 찾는다. 

출처: http://koosaga.com/133

---

[6086번] 최대 유량 :: https://www.acmicpc.net/problem/6086 문제를 기반으로 알고리즘을 설명하겠습니다.

주석 및 이 문제의 입출력 부분때문에 코드가 난잡하고 길어보이지만, 막상 주석을 지우고 이 알고리즘을 이해하고 다른 문제를 접근하면 생각외로 짧은 코드이다.

그리고 조금있다가 확인하겠지만, 역방향 개념에 대해서는 이 문제에서 다루지 않기 때문에 풀리지만, 추후 다른 문제를 풀게 될 때

역방향 간선, 값을 주지 않으면 유량의 대칭성에 모순이 될 수 있으므로 항상 추가해둔다.

자세한 내용은 주석을 통해 모두 달아두었습니다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
 
#define MAX 52
#define INF 987654321
 
using namespace std;
 
int main()
{
    int n;
    int c[MAX][MAX]; // capacity :: i->j로 가는 간선 용량
    int f[MAX][MAX]; // flow :: i->j로 현재 흐르고 있는 유량
 
    memset(c, 0, sizeof(c));
    memset(f, 0, sizeof(f));
 
    vector<int> adj[MAX];
    
    // 입력
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        char chfrom, chto;
        int val;
        // \n 때문에 " %c로 받는다.
        scanf(" %c %c %d", &chfrom, &chto, &val);
 
        // 입력받은 문자를 0~51사이 값으로 변환
        int from, to;
        if ('A' <= chfrom && chfrom <= 'Z')
            from = chfrom - 'A';
        else
            from = chfrom - 'a' + 26;
 
        if ('A' <= chto && chto <= 'Z')
            to = chto - 'A';
        else
            to = chto - 'a' + 26;
 
        c[from][to] += val; // 용량을 추가해준다.
        c[to][from] += val; 
        adj[from].push_back(to);
        adj[to].push_back(from); // 역방향 간선 추가
    }
 
    int totalFlow = 0, S = 0, T = 'Z' - 'A'; // S :: source, T :: sink
 
    // 증가 경로를 못 찾을 때까지
    while (1)
    {
        int prev[MAX];
        memset(prev, -1, sizeof(prev));
 
        queue<int> q;
        // 싱크를 처음 push 해준다.
        q.push(S);
 
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
 
            for (int i = 0; i < adj[cur].size(); i++)
            {
                int next = adj[cur][i];
 
                // next를 방문하였다면 continue
                if (prev[next] != -1)
                    continue;
 
                // 아직 흐를 수 있는 유량이 있다면
                // 즉, cur -> next로 갈 수 있는 유량이 있다면
                if (c[cur][next] - f[cur][next] > 0)
                {
                    q.push(next);
 
                    // next의 경로 추적을 위해 저장
                    prev[next] = cur;
 
                    // 만약 next가 sink면 break
                    if (next == T)
                        break;
                }
            }
        }
 
        // source -> sink의 간선이 없다면 break;
        if (prev[T] == -1)
            break;
 
        int flow = INF;
 
        // 지금까지 구한 경로 상에서 가장 flow가 낮은 곳을 구한다.
        for (int i = T; i != S; i = prev[i])
            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);
        
        // 해당 경로에 flow를 보낸다.
        // 그리고 역방향으로는 flow를 빼준다.
        for (int i = T; i != S; i = prev[i])
        {
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
        }
 
        totalFlow += flow;
    }
 
    printf("%d\n", totalFlow);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>