네트워크플로우(Network flow) - 포드 풀커슨(Ford-Fulkerson) 알고리즘

네트워크 플로우란(Network flow)?

그래프의 경로의 길이가 아닌, ‘용량’의 관점에서 바라보는 시점.

Ex) 인터넷으로 영화를 다운받고 있는데 파일 원격지에서 얼마나 빨리 받을 수 있는지를 알고 싶다. 각 컴퓨터의 네트워크 장비는 대역폭의 제한이 있다. 따라서 가장 짧은 거리로 오는 것보다. 대역폭이 큰 쪽으로 오는 것이 더 유리하다.

위의 그림의 예에서 가중치는 비용이 아니라, 대역폭, 즉 유량이다.

A->B->E 의 경로에서는 최대 1의 데이터를 보낼 수 있는 반면에, A->C->D->E의 경로는 한 정점을 더 지나가게 되지만 한번에 100의 데이터를 보낼 수 있다.

용어

-       Source – 네트워크의 시작(A), Sink – 네트워크의 도착지(E)

-       정점 a에서 b로가는 용량 – c(a,b)

-       a에서 b로 흐르는 유량 – f(a,b)

-       a에서 b로 보낼 수 있는 잔여 용량 – r(a,b) = c(a,b)-f(a,b)

중요한 3가지 특성

1.     용량의 제한 -  f(a,b)<= c(a,b)

2.     유량의 대칭 – f(a,b) = - f(b,a)

3.     유량의 보존 – f(a,b)들의 합 = 0 => 각 정점에 들어오고 나가는 유량의 합은 같다.

 

 

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

포드-풀커슨 알고리즘은 최초의 네트워크 유량 알고리즘.

개념과, 구현이 간단

네트워크의 모든 간선의 유량을 0으로 시작, Source에서 Sink로 보낼 수 있는 경로로 유량을 보내기를 반복하면 된다.

 

중요점 – 유량의 상쇄

Ex) 최대 유량을 찾고 있는데 A-B-D로 유량을 보냈는데, 알고 보니 A-B-C-D가 더 최대 유량이였다. 잔여 용량이 없기 때문에 더 이상 보낼 수 없고, 최대값을 찾는 것에 실패를 했다.

위와 같은 문제점을 없애기 위해서, 유량을 보낼 때 Back-Edge를 만들어 줘야 한다. 문제가 없을까?

-       B->A의 용량 =>c(B,A) =0, 즉 B에서 A로 보낼 수 없는 상황

-       A->B로 유량을 1 보냈다고 하자. => f(A,B) =1.= -f(B,A)

-       잔여용량 = r(B,A) = c(B,A)-f(B,A) = 0 –(-1) = 1, 즉 하나를 보낼 수 있다.

ð  즉, 유량 하나를 보내는 것은 역으로 유량을 하나 보낼 수 있게 해주는 작업과 같다는 말이다.

 

 

 

 

 

 

결과적으로, 모든 네트워크를 모델링을 한 후에, Back Edge를 흘러가는 유량만큼 만들어 줌으로써, DFS,BFS를 가능할 때 까지 반복한다.

최소컷 최대 유량 정리(Min-cut Max-flow Theorem)

컷(cut) – Source와 Sink가 다른 집합에 속하도록 그래프의 정점들을 두 개의 집합으로 나눈 것. Source가 속한 집합을 S, Sink가 속한 집합을 T라고 두고, S->T로 보내는 총 유량을 컷 S,T의 유량이라고 정의한다.

컷의 중요 속성 2가지

1.     컷의 유량은 Source->Sink의 유량과 같다.

2.     컷의 유량 <= 컷의 용량

ð  네트워크에서 용량이 가장 작은 컷을 찾아내는 문제를 최소 컷(min cut)문제라고 함

ð  최소 컷 – 용량과 유량이 같은 컷을 찾아내면 된다.

즉, 최소컷을 찾기 위해서는 최대 유량을 찾으면 된다.

구현

잔여 용량이 없을 때 까지, 즉 보낼 수 있는 유량이 없을 때까지 BFS또는 DFS 반복

코드

코드는 백준 알고리즘 저지 11375번, 열혈강호의 풀이로 첨부해 두었다.

이분 매칭으로도 풀수 있지만, 네트워크 플로우의 기본을 닦기에 좋은 문제이다.

https://www.acmicpc.net/problem/11375

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#define SOURCE 0
#define SINK N+M+1
using namespace std;
int N, M;
int net[2002][2002];
vector<int> parents(2002);
bool visit[2002];
void backPath(int n) {
    while (n != 0) {
        int child = n;
        n = parents[n];
        //1감소
        net[n][child] --;
        net[child][n] ++;
    }
}
bool dfs(int start) {
    if (start == SINK) return true;
    for (int i = 0; i < N + M + 2;i++) {
        if (net[start][i] <= 0 || visit[i]==true) continue;
        //뺵경로 설정
        parents[i] = start;
        
        visit[i] = true;
        if (dfs(i)) return true;
    }
    return false;
}
int main()
{
    cin >> N >> M;
    memset(net, 0, sizeof(net));
    memset(visit, 0, sizeof(visit));
    int a, b;
    for (int i = 1; i <= N; i++)
    {
        cin >> a;
        for (int j = 0; j < a; j++) {
            cin >> b;
            net[i][N+b] = 1;
        }
    }
    //SOURCE -> 직원
    for (int i = 1; i <= N; i++) net[0][i] = 2;
    //일 ->SYNC
    for (int i = 1+N; i <= N+M; i++) net[i][SINK] = 1;
    int result = 0;
    while (dfs(0)) {
        result++;
        //빽엣지
        backPath(SINK);
        memset(visit, 0, sizeof(visit));
    }
    cout << result << endl;
    return 0;
}