Maximum flow - Fold-Fulkerson and Edmonds-Karp

Maximum flow - Ford-Fulkerson and Edmonds-Karp - Algorithms for Competitive Programming

 

Maximum Flow - Fold-Fulkerson and Edmonds-Karp

 

Directed graph와 source vertex, sink vertex, 그리고 각 edge의 capacity가 주어진다.

 

source vertex에서 sink vertex로 보낼 수 있는 maximum flow는 얼마인지 구하는 유형이다.

(굵기가 다양한 파이프를 edge라 하고 source에 물이 무한하게 있다고 하였을 때, source에서 sink까지 1초에 얼마나 많은 unit의 물이 도달하는지로 생각하자)

 

기본적으로 Fold-Fulkerson method(계속해서 source vertex에서 sink vertex로의 경로를 고려하였을 때 물을 더 보낼 수 있다면 더 보내도록 반복하는 방법)를 사용하면 된다.

 

Fold-Fulkerson method을 naive 하게 생각하면 O(EF)(E: edge의 개수, F: maximal flow of the network)가 된다.

(dfs, bfs를 하며 source에서 sink로의 flow를 증가시킬 수 있는 경로를 찾는다 (O(E)). 이 과정을 한 번 할 때마다 capacity를 1 이상 늘릴 수 있으므로 F 번 반복하였을 때 과정이 종료됨을 계산할 수 있다)

 

Fold-Fulkerson method을 implementation 하는 알고리즘 중 Edmond-Karp algorithm의 complexity는 O(VE^2)이다.

 

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;
}

 

Integral Flow Theorem

 

Integral flow theorem: flow network의 모든 edge의 capacity가 integer라면, maximum flow에서의 각 edge의 flow도 integer이다.

 

 

Max-Flow Min-Cut Theorem

 

Max-flow min-cut theorem: graph의 vertex 들을 각각 sink와 source를 가진 두 개의 set으로 partition 했을 때(cut 했을 때)(이를 s-t-cut이라 한다) source side에서 sink side로 가는 edge 들의 capacity의 합보다 그래프의 maximum flow가 작거나 같은 것은 자명하다. (만약 그렇지 않다면 source에서 sink로 maximum flow만큼 흐를 수가 없다)

 

Max-flow Min-cut Theorem은 여기서 한발 더 나아가는데, min-cut을 하였을 때 cut되는 edge의 capacity 총합이 maximum flow와 같다는 것이다. (min-cut은 비용이 최소가 되는 cut을 의미한다)

 

5 + 3 + 2 = 10 (cost of min-cut = maximum flow)

 

 

이러한 min-cut을 구하는 방법은 아래에 잘 설명되어 있다. (Edmonds-Karp 이후 dfs를 한 번 더 돌려주면 된다)

 

source side vertex를 구하려면 Edmond-Karp algorithm이 완료되었을 때, source에 물을 더 흘려 도달할 수 있는 vertex 들을 선택하면 된다. (이 외의 것들은 sink side)

 

min-cut에 해당하는 edge를 구하려면, source에 물을 더 흘려 capacity가 0이라 더 이상 흐를 수 없는 edge 들을 선택하면 된다.

 

[알고리즘] Max-Flow Min-Cut Theorem (최대 유량 최소컷 정리)