네트워크 유량(Network flow)

네트워크 유량 문제

Network flow

네트워크 유량문제는 최대 유량(Maximum flow)라고도 한다.

방향이 있는 그래프에서 각 간선에 흐를 수 있는 용량이 정해져 있을 때, 출발점에서 도착점까지 보낼 수 있는 최대 유량을 계산하는 문제

 

용어

= Source(시작점)에서 Sink(도착점)으로 동시에 보낼 수 있는 최대 양을 구하는 알고리즘

Source: 시작점

Sink: 도착점

Capacity: 용량(각 간선에 흐를 수 있는 최대 용량)

Augmented Path: 증가 경로(최소 1 이상의 유량이 흐를 수 있는 시작점에서 도착점까지의 경로)

Flow: 유량, 해당 간선에 실제로 흐르는 용량

 

네트워크 유량 문제의 특징

1. 용량의 제한, 각 간선에 흐르는 유량을 그 간선의 용량을 넘을 수 없음

2. 유량의 보존, 어떤 정점을 기준으로 볼 때, 들어오는 유량의 총합은 나가는 유량의 총합과 같다.

3. 유량의 대칭, 정점 a와 b가 있을 때, a에서 b로 10만큼의 유량이 흐른다면, b에서 a로 -10만큼의 유량이 흐르는 것과 같다.

 

Ford-Fulkerson Algorithm

네트워크 유량 문제를 해결하기 위해 포드-풀커슨 알고리즘을 제시한다.

포드-풀커슨 알고리즘에서는 최대 유량 문제를 해결하기 위해 다음과 같은 과정을 제시한다.

 

1. 시작점에서 도착점까지의 증가 경로를 찾아냄

2. 증가 경로 상의 간선 중 용량이 가장 작은 것을 찾아냄

3. 2에서 찾는 최소 용량만큼 유량을 흘려보냄

4. 더 이상 증가 경로가 발견 되지 않을 때까지 위 과정을 반복

 

하지만, 포드-풀커슨 알고리즘에서는 어떻게 경로를 찾는가에 대해서는 특별히 정해져 있지 않다.

즉, 증가 경로를 탐색한다면 다항 시간안에 알고리즘이 동작하지 않을 수 있다.

이때, 증가 경로를 BFS로 선택하는 경우를 에드몬즈-카프 알고리즘이라고 한다.

 

 

Edmonds-Karp Algorithm

에드몬즈-카프 알고리즘은 증가 경로를 BFS로 탐색하여 다항 시간안에 최대 유량 문제를 해결할 수 있다.

포드 풀커슨 알고리즘을 BFS를 통해 구현하는 것 이라고 생각하면 편하다.

에드몬즈-카프 알고리즘의 증명: https://gazelle-and-cs.tistory.com/82

 

동작 과정

0. 다음과 같은 유향 그래프에 대해 최대 유량을 구해보자

 

1. BFS로 증가 경로를 찾는다. 정점 1, 2, 3, 5를 지나는 증가경로가 하나 찾아진다.

 

2. 증가 경로를 이루는 간선 중, 최소 용량은 1이다. 1 만큼 유량을 흘려보내준다.

 

3. 다음 증가 경로를 찾아준다. 1, 2, 4, 5를 지나는 증가 경로가 찾아진다.

 

4. 마찬가지로 해당 경로의 최소 용량인 1만큼 유량을 흘려보내준다.

위 과정을 반복하더라도 1과 2를 연결하는 간선이 2/2로 더 이상 유량을 흘려보낼 수 없다.

따라서, 최대 유량은 1+1=2이다.

 

알고리즘 동작 자체는 BFS로 증가 경로를 찾고, 해당 경로에 대해 유량을 반영해주는 것을 반복하면 됨으로 간단하다.

하지만, 위 과정이 항상 최대 유량을 보장할지에 대해서는 생각 해 봐야 한다.

그래서 나온 것이 최소 컷 최대 유량 정리이다.

 

Min-cut Max-flow Teorem

컷(Cut)이란?

유량 네트워크에서 컷이란 소스와 싱크가 다른 집합에 속하도록 그래프의 정점들을 두 개의 집합으로 나눈 것이다.

시작점(소스)가 있는 곳의 컷을 S라고 하고, 도착점(싱크)가 있는 곳의 컷을 T라고 할 때, 다음과 같은 컷으로 나눌 수 있다.

 

최소 컷(Min-cut)이란?

네트워크에서 용량이 가장 작은 컷을 찾아내는 문제를 말한다.

이 최소 컷 문제는 최대 유량과 매우 밀접한 관련이 있다.

 

컷에서의 용량과 유량

다음과 같은 유향 그래프가 있고, 다음과 같은 컷으로 그래프를 나누었다고 하자

S-T 컷 1

이때, S에서 T로 가는 간선들의 용량 합을 S,T의 용량이라고 하고, S에서 T로 가는 유량을 S, T의 유량이라고한다.

컷의 용량은 S에서 T로 가는 모든 간선의 용량을 합하지만, 컷의 유량의 경우 T->S의 간선인 4번 정점에서 3번 정점으로 흐르는 1만큼의

용량을 포함해야한다. 따라서 S->T의 유량 합은 9가 된다.

S->T 용량 합: 3 + 1 + 5 = 9

S->T 유량 합: 3 + 3 + 4 + (-1) = 7

 

유향 그래프의 모든 컷과 유량에서는 다음과 같은 속성 두개가 항상 성립한다.

 

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

위 사진에서도 6번 정점(싱크)로 들어오는 최대 유량은 7이고, S->T컷에서의 유량 합도 7로 동일함을 볼 수 있다.

컷을 어떻게 나누더라도 7로 동일 하다.

이를 확인하기 위해 다른 컷으로도 나눠보자

S-T 컷 2

S->T의 용량 합: 3 + 2 + 3 = 8

S->T의 유량 합: 3 + 1 + 3 = 7

마찬가지로, 6번 정점(싱크)로 들어오는 최대 유량 7과 같음을 확인할 수 있다.

 

2.  컷의 유량은 용량과 작거나 같다.

용량은 해당 노드를 통해 흐를 수 있는 상한 값 이다. 따라서, 흐를 수 있는 정도는 해당 간선의 최대 용량을 넘을 수 없다는 것은 당연하다.

간선의 용량보다 더 크게 물이 흐른다...? 있을 수 없다.

 

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

이때, 네트워크에서 최소 컷(용량이 가장 작은 컷)을 찾아보자

-> 네트워크에 용량과 유량이 같은 컷이 존재한다면, 해당 컷이 최소 컷이 된다.

 

즉 아래와 위 유향 그래프에서는 아래와 같은 경우가 최소 컷이 된다.

모든 증가 경로에 유량을 흘려보낸 뒤, 소스(시작점)정점에서 갈 수 있는 정점들은 S집합, 그 외 모든 정점은 T집합으로 나눈다.

S = {1, 2}

T = {3, 4, 5, 6}

S->T 용량 합: 7

S->T 유량 합: 7

으로 유량과 용량이 7로 같은 최소 컷을 구할 수 있다.

 

정리하자면, 포드-풀커슨(에드몬즈-카프) 알고리즘은 유향 그래프에서 증가 경로가 더 이상 존재하지 않을 때 탐색을 종료하고,

이때의 컷은 유향 그래프에서의 최소 컷이 된다.

그리고 최소 컷의 용량은 최대 유량의 크기와 같고, 이는 포드-풀커슨(에드몬즈-카프) 알고리즘이 항상 최대 유량을 보장함을 증명한다.

 

문제 풀이 및 코드

문제

[백준] 도시 왕복하기 1: https://www.acmicpc.net/problem/17412

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
int N, P;
int capacity[401][401]; // 간선 최대 용량
int flow[401][401]; // 현재 사용중인 용량
int networkFlow(int source, int sink)
{
    memset(flow, 0, sizeof(flow));
    int totalFlow = 0;
    while (true)
    {
        vector<int> parent(N + 1, -1);
        queue<int> q;

        parent[source] = source;
        q.push(source);

        // 더 이상 나아갈 수 없거나, 목적지에 도달한 경우
        while (!q.empty() && parent[sink] == -1)
        {
            int now = q.front();
            cout << now << " ";
            q.pop();
            for (int i = 1; i <= N; ++i)
            {
                if (capacity[now][i] - flow[now][i] <= 0) continue;
                if (parent[i] == -1) 
                {
                    q.push(i);
                    parent[i] = now;
                }
            }
        }

        // 증가 경로를 못 찾는다면 종료
        if (parent[sink] == -1) break;

        int amount = 987654321;
        // 역으로 탐색하면서, 유량을 얼마나 보낼지 탐색
        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;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> P;
    for (int i = 0; i < P; ++i)
    {
        int a, b;
        cin >> a >> b;
        capacity[a][b] = 1;
    }
    cout << networkFlow(1, 2);
    return 0;
}