최대 흐름 - Ford-Fulkerson과 Edmonds-Karp¶

Edmonds-Karp 알고리즘은 흐름 네트워크에서 최대 흐름을 계산하는 Ford-Fulkerson 방법의 한 구현입니다.

흐름 네트워크¶

먼저 흐름 네트워크, 흐름, 최대 흐름이 무엇인지 정의합시다.

네트워크는 정점 $V$와 간선 $E$로 이루어진 방향 그래프 $G$에 함수 $c$를 결합한 것으로, 이 함수는 각 간선 $e \in E$에 음이 아닌 정수 값, 즉 $e$의 용량을 부여합니다. 이러한 네트워크에서 두 정점을 추가로 지정하여 하나를 소스, 다른 하나를 싱크로 표시하면, 이를 흐름 네트워크라고 부릅니다.

흐름 네트워크에서 흐름은 함수 $f$이며, 이 함수 역시 각 간선 $e$에 음이 아닌 정수 값, 즉 흐름을 부여합니다. 이 함수는 다음 두 조건을 만족해야 합니다:

간선의 흐름은 용량을 초과할 수 없습니다.

$$f(e) \le c(e)$$

그리고 소스와 싱크 정점을 제외하면, 정점 $u$로 들어오는 흐름의 합은 $u$에서 나가는 흐름의 합과 같아야 합니다.

$$\sum_{(v, u) \in E} f((v, u)) = \sum_{(u, v) \in E} f((u, v))$$

소스 정점 $s$에는 나가는 흐름만 있고, 싱크 정점 $t$에는 들어오는 흐름만 있습니다.

다음 방정식이 성립함은 쉽게 알 수 있습니다:

$$\sum_{(s, u) \in E} f((s, u)) = \sum_{(u, t) \in E} f((u, t))$$

흐름 네트워크는 다음과 같이 시각화하면 잘 이해할 수 있습니다: 간선을 수도관으로 나타내면, 간선의 용량은 그 관을 통해 초당 흐를 수 있는 물의 최대량이고, 간선의 흐름은 현재 그 관을 통해 초당 흐르고 있는 물의 양입니다. 이것이 첫 번째 흐름 조건의 근거가 됩니다. 파이프를 통해 흐를 수 있는 물의 흐름은 그 파이프의 용량을 초과할 수 없습니다. 정점은 분기점 역할을 하여, 일부 관에서 물이 흘러나오면 이 정점들이 그 물을 어떤 방식으로든 다른 관으로 분배합니다. 이것은 두 번째 흐름 조건의 근거도 됩니다. 각 분기점에서는 들어온 물이 모두 다른 관으로 분배되어야 합니다. 물이 마법처럼 사라지거나 생겨날 수는 없습니다. 소스 $s$는 모든 물의 근원이며, 물은 오직 싱크 $t$로만 빠져나갈 수 있습니다.

다음 그림은 흐름 네트워크를 보여 줍니다. 각 간선의 첫 번째 값은 흐름을 나타내며 초기값은 0이고, 두 번째 값은 용량을 나타냅니다.

네트워크의 흐름 값은 소스 $s$에서 생성되는 모든 흐름의 합이며, 이는 싱크 $t$에서 소비되는 모든 흐름의 합과 같습니다. 최대 흐름은 가능한 최대 값을 갖는 흐름입니다. 흐름 네트워크에서 이러한 최대 흐름을 찾는 것이 우리가 풀고자 하는 문제입니다.

수도관 시각화에서 이 문제는 다음과 같이 표현할 수 있습니다: 소스에서 싱크까지 관을 통해 얼마나 많은 물을 흘려보낼 수 있습니까?

다음 그림은 흐름 네트워크에서의 최대 흐름을 보여 줍니다.

Ford-Fulkerson 방법¶

한 가지를 더 정의하겠습니다. 방향 간선의 잔여 용량은 용량에서 흐름을 뺀 값입니다. 어떤 방향 간선 $(u, v)$를 따라 흐름이 있다면, 역방향 간선의 용량은 0이며 그 흐름을 $f((v, u)) = -f((u, v))$로 정의할 수 있다는 점에 유의해야 합니다. 이로써 모든 역방향 간선의 잔여 용량도 정의됩니다. 이 모든 간선으로 잔여 네트워크를 만들 수 있습니다. 잔여 네트워크는 정점과 간선이 같은 네트워크이며, 다만 잔여 용량을 용량으로 사용합니다.

Ford-Fulkerson 방법은 다음과 같이 동작합니다. 먼저 각 간선의 흐름을 0으로 설정합니다. 그런 다음 $s$에서 $t$로 가는 증가 경로를 찾습니다. 증가 경로는 잔여 그래프에서 경로 위의 모든 간선의 잔여 용량이 양수인 단순 경로입니다. 그러한 경로를 찾으면 그 간선들을 따라 흐름을 증가시킬 수 있습니다. 증가 경로를 계속 찾으면서 흐름을 증가시킵니다. 증가 경로가 더 이상 존재하지 않으면 흐름은 최대입니다.

증가 경로를 따라 흐름을 증가시킨다는 것이 무엇을 의미하는지 더 자세히 살펴봅시다. 경로에 있는 간선들의 잔여 용량 중 가장 작은 값을 $C$라고 합시다. 그러면 다음과 같은 방식으로 흐름을 증가시킵니다: 경로에 있는 모든 간선 $(u, v)$에 대해 $f((u, v)) ~\text{+=}~ C$와 $f((v, u)) ~\text{-=}~ C$로 갱신합니다.

이 방법을 보여 주는 예시는 다음과 같습니다. 위와 같은 흐름 네트워크를 사용합니다. 처음에는 흐름 0으로 시작합니다.

잔여 용량이 각각 7, 5, 8인 경로 $s - A - B - t$를 찾을 수 있습니다. 이들 중 최솟값은 5이므로 이 경로를 따라 흐름을 5만큼 증가시킬 수 있습니다. 이렇게 하면 네트워크의 흐름은 5가 됩니다.

다시 증가 경로를 찾으면, 이번에는 잔여 용량이 각각 4, 3, 3, 5인 $s - D - A - C - t$를 찾습니다. 따라서 흐름을 3만큼 증가시킬 수 있고, 네트워크의 흐름은 8이 됩니다.

이번에는 잔여 용량이 각각 1, 2, 3, 3인 경로 $s - D - C - B - t$를 찾으므로 흐름을 1만큼 증가시킵니다.

이번에는 잔여 용량이 각각 2, 3, 1, 2인 증가 경로 $s - A - D - C - t$를 찾습니다. 흐름을 1만큼 증가시킬 수 있습니다. 그런데 이 경로는 매우 흥미롭습니다. 이 경로는 역방향 간선 $(A, D)$를 포함합니다. 원래의 흐름 네트워크에서는 $A$에서 $D$로 흐름을 보내는 것이 허용되지 않습니다. 하지만 이미 $D$에서 $A$로 3의 흐름이 있으므로 이것이 가능합니다. 이에 대한 직관은 다음과 같습니다: $D$에서 $A$로 3의 흐름을 보내는 대신 2만 보내고, 이를 $s$에서 $A$로 1의 흐름을 추가로 보내는 것으로 보충합니다. 그러면 경로 $D - C - t$를 따라 1의 흐름을 추가로 보낼 수 있습니다.

이제 $s$와 $t$ 사이에서 증가 경로를 찾을 수 없으므로, 이 $10$의 흐름이 가능한 최댓값입니다. 최대 흐름을 찾았습니다.

Ford-Fulkerson 방법은 증가 경로를 찾는 방법을 지정하지 않는다는 점에 유의해야 합니다. 가능한 접근 방식으로는 DFS나 BFS를 사용하는 것이 있으며, 둘 다 $O(E)$에 동작합니다. 네트워크의 모든 용량이 정수라면, 각 증가 경로마다 네트워크의 흐름은 최소 1만큼 증가합니다(자세한 내용은 정수 흐름 정리를 참고하십시오). 따라서 Ford-Fulkerson의 복잡도는 $O(E F)$이며, 여기서 $F$는 네트워크의 최대 흐름입니다. 용량이 유리수인 경우에도 알고리즘은 종료되지만, 복잡도에는 상한이 없습니다. 용량이 무리수인 경우에는 알고리즘이 끝내 종료되지 않을 수 있으며, 최대 흐름으로 수렴하지 않을 수도 있습니다.

Edmonds-Karp 알고리즘¶

Edmonds-Karp 알고리즘은 증가 경로를 찾는 데 BFS를 사용하는 Ford-Fulkerson 방법의 한 구현일 뿐입니다. 이 알고리즘은 1970년에 Yefim Dinitz가 처음 발표했으며, 이후 1972년에 Jack Edmonds와 Richard Karp가 독립적으로 발표했습니다.

복잡도는 최대 흐름과 무관하게 나타낼 수 있습니다. 이 알고리즘은 용량이 무리수인 경우에도 $O(V E^2)$ 시간에 동작합니다. 직관적으로 설명하면, 증가 경로를 찾을 때마다 간선 중 하나가 포화되며, 그 간선이 나중에 다시 증가 경로에 나타난다면 그 간선에서 $s$까지의 거리는 더 길어집니다. 단순 경로의 길이는 $V$ 이하입니다.

구현¶

행렬 capacity는 모든 정점 쌍에 대한 용량을 저장합니다. adj는 무방향 그래프의 인접 리스트인데, 증가 경로를 찾을 때 방향 간선의 역방향도 사용해야 하기 때문입니다.

함수 maxflow는 최대 흐름의 값을 반환합니다. 알고리즘이 진행되는 동안 행렬 capacity에는 실제로 네트워크의 잔여 용량이 저장됩니다. 각 간선의 흐름 값은 실제로 저장되지 않지만, 추가 행렬을 사용하여 흐름도 저장하고 반환하도록 구현을 확장하는 것은 쉽습니다.

int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;

int bfs(int s, int t, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<int, int>> q;
    q.push({s, INF});

    while (!q.empty()) {
        int cur = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next : adj[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                int new_flow = min(flow, capacity[cur][next]);
                if (next == t)
                    return new_flow;
                q.push({next, new_flow});
            }
        }
    }

    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    vector<int> parent(n);
    int new_flow;

    while (new_flow = bfs(s, t, parent)) {
        flow += new_flow;
        int cur = t;
        while (cur != s) {
            int prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }

    return flow;
}

정수 흐름 정리¶

이 정리에 따르면, 네트워크의 모든 용량이 정수일 때 최대 흐름의 크기도 정수이며, 각 간선의 흐름 또한 정수인 최대 흐름이 존재합니다. 특히, Ford-Fulkerson 방법은 그러한 흐름을 찾아냅니다.

최대 흐름 최소 컷 정리¶

$s$-$t$-컷은 흐름 네트워크의 정점들을 두 집합으로 나눈 분할로, 한 집합은 소스 $s$를 포함하고 다른 집합은 싱크 $t$를 포함합니다. $s$-$t$-컷의 용량은 소스 쪽에서 싱크 쪽으로 향하는 간선들의 용량의 합으로 정의됩니다.

당연히, 어떤 $s$-$t$-컷의 용량보다 더 많은 흐름을 $s$에서 $t$로 보낼 수는 없습니다. 따라서 최대 흐름은 최소 컷 용량을 넘을 수 없습니다.

최대 흐름 최소 컷 정리는 여기서 한 걸음 더 나아갑니다. 이 정리에 따르면 최대 흐름의 용량은 최소 컷의 용량과 같아야 합니다.

다음 그림에서 앞서 사용한 흐름 네트워크의 최소 컷을 볼 수 있습니다. 이 그림은 컷 $\{s, A, D\}$와 $\{B, C, t\}$의 용량이 $5 + 3 + 2 = 10$이며, 이는 우리가 찾은 최대 흐름과 같다는 것을 보여 줍니다. 다른 컷들은 더 큰 용량을 가집니다. 예를 들어 $\{s, A\}$와 $\{B, C, D, t\}$ 사이의 용량은 $4 + 3 + 5 = 12$입니다.

최소 컷은 Ford-Fulkerson 방법으로 최대 흐름을 계산한 후에 찾을 수 있습니다. 가능한 최소 컷 중 하나는 다음과 같습니다. 잔여 그래프에서 (잔여 용량이 양수인 간선을 사용하여) $s$로부터 도달할 수 있는 모든 정점의 집합과 나머지 모든 정점의 집합입니다. 이 분할은 $s$에서 시작하는 DFS를 사용하여 쉽게 찾을 수 있습니다.