Max-Flow dan Min-Cut

Berapa banyak air yang dapat mengalir dari sumber ke tujuan melalui jaringan pipa dengan kapasitas berbeda-beda? Bagaimana distribusi bandwidth optimal pada jaringan komputer? Pertanyaan-pertanyaan ini mengarah ke persoalan Maximum Flow: diberikan graph berarah berbobot dengan node sumber s dan node tujuan t, berapa aliran maksimum yang dapat dikirim dari s ke t tanpa melanggar kapasitas edge? Persoalan ini saling terkait dengan Minimum Cut — himpunan edge minimum yang bila dipotong memisahkan s dari t. Teorema Max-Flow Min-Cut menyatakan kedua nilai ini sama, sebuah hasil fundamental yang menjadi dasar banyak algoritma. Pada Chapter ini kita akan membedah algoritma Ford-Fulkerson, varian Edmonds-Karp berbasis BFS, dan mengimplementasikannya dalam C++.

Aturan: Flow Network dan Constraint #

Diberikan graph berarah G = (V, E) dengan kapasitas c(u, v) ≥ 0 untuk setiap edge, node sumber s, dan node tujuan t. Sebuah flow adalah fungsi f: E → R yang memenuhi:

1. Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v) untuk setiap edge.
2. Flow conservation: untuk setiap node u selain s dan t, total flow masuk = total flow keluar.

Max flow = flow dengan total keluar dari s (atau masuk ke t) maksimum.

Mekanisme: Ford-Fulkerson dengan Residual Graph #

Ide Ford-Fulkerson: ulangi berikut sampai tidak ada augmenting path:

1. Cari augmenting path dari s ke t pada residual graph G_f — graph dengan kapasitas residual c_f(u, v) = c(u, v) - f(u, v) untuk edge forward, dan c_f(v, u) = f(u, v) untuk edge backward (membatalkan flow).
2. Hitung bottleneck = kapasitas residual minimum sepanjang path.
3. Augment: tambahkan bottleneck ke flow sepanjang path (kurangi forward, tambah backward).

Loop berhenti saat tidak ada augmenting path. Total flow terakumulasi = max flow.

Mekanisme: Edmonds-Karp (BFS-based) #

Edmonds-Karp adalah varian Ford-Fulkerson yang menggunakan BFS untuk menemukan augmenting path. BFS menjamin path terpendek (dalam jumlah edge), yang membatasi jumlah iterasi O(V · E) — setiap iterasi O(E) BFS → total O(V · E²).

Implementasi Edmonds-Karp #

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

class MaxFlow {
    int n;
    std::vector<std::vector<long long>> capacity;
    std::vector<std::vector<int>> adj;

public:
    explicit MaxFlow(int n) : n(n), capacity(n, std::vector<long long>(n, 0)), adj(n) {}

    void add_edge(int u, int v, long long cap) {
        adj[u].push_back(v);
        adj[v].push_back(u);          // untuk edge residual
        capacity[u][v] += cap;        // += untuk multi-edge
    }

    // BFS cari augmenting path
    bool bfs(int s, int t, std::vector<int>& parent) {
        std::fill(parent.begin(), parent.end(), -1);
        parent[s] = s;
        std::queue<std::pair<int, long long>> q;
        q.push({s, LLONG_MAX});

        while (!q.empty()) {
            auto [u, flow] = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (parent[v] == -1 && capacity[u][v] > 0) {
                    parent[v] = u;
                    long long new_flow = std::min(flow, capacity[u][v]);
                    if (v == t) {
                        parent[t] = u; // pastikan parent[t] sudah set
                        return true;
                    }
                    q.push({v, new_flow});
                }
            }
        }
        return false;
    }

    // Edmonds-Karp: BFS-based Ford-Fulkerson
    long long maxflow(int s, int t) {
        long long total = 0;
        std::vector<int> parent(n);
        while (bfs(s, t, parent)) {
            // Hitung bottleneck
            long long flow = LLONG_MAX;
            for (int v = t; v != s; v = parent[v]) {
                int u = parent[v];
                flow = std::min(flow, capacity[u][v]);
            }
            // Update residual
            for (int v = t; v != s; v = parent[v]) {
                int u = parent[v];
                capacity[u][v] -= flow;
                capacity[v][u] += flow;
            }
            total += flow;
        }
        return total;
    }
};

int main() {
    // Network flow:
    //   S --(10)--> A --(4)--> T
    //   S --(8)---> B --(10)-> T
    //   A --(2)---> B
    //   B --(9)---> A
    int n = 4; // 0=S, 1=A, 2=B, 3=T
    MaxFlow mf(n);
    int s = 0, t = 3;
    mf.add_edge(s, 1, 10); // S->A
    mf.add_edge(s, 2, 8);  // S->B
    mf.add_edge(1, t, 4);  // A->T
    mf.add_edge(2, t, 10); // B->T
    mf.add_edge(1, 2, 2);  // A->B
    mf.add_edge(2, 1, 9);  // B->A

    long long flow = mf.maxflow(s, t);
    std::cout << "Max flow S -> T: " << flow << "\n";

    std::cout << "\nTrace manual:\n";
    std::cout << "  S->A->T : 4 (bottleneck A->T=4)\n";
    std::cout << "  S->B->T : 8 (bottleneck S->B=8)\n";
    std::cout << "  S->A->B->T : 2 (A->B=2, B->T masih 2)\n";
    std::cout << "  Total: 4 + 8 + 2 = 14\n";
    return 0;
}

Output yang Dihasilkan:

Max flow S -> T: 14

Trace manual:
  S->A->T : 4 (bottleneck A->T=4)
  S->B->T : 8 (bottleneck S->B=8)
  S->A->B->T : 2 (A->B=2, B->T masih 2)
  Total: 4 + 8 + 2 = 14

Bedah Kode Baris-per-Baris #

1. std::vector<std::vector<long long>> capacity: matriks kapasitas residual. Awalnya = kapasitas asli. Saat augment, kapasitas forward berkurang, kapasitas backward (residual) bertambah.
2. std::vector<std::vector<int>> adj: adjacency list. Setiap edge forward u → v menambah v ke adj[u] dan u ke adj[v] — karena edge backward juga perlu diperiksa di BFS.
3. adj[u].push_back(v); adj[v].push_back(u);: tambahkan keduanya secara simetris. Bahkan bila hanya ada edge asli u → v, edge residual v → u akan muncul saat flow dikirim.
4. capacity[u][v] += cap: gunakan += agar multi-edge (beberapa edge u → v dari input) terakumulasi dengan benar.
5. bool bfs(int s, int t, std::vector<int>& parent): BFS standar dengan modifikasi — hanya ikuti edge dengan kapasitas residual > 0. Return true bila path s → t ditemukan, dengan parent[] menyimpan rekonstruksi path.
6. parent[s] = s: marker bahwa s sudah dikunjungi dan menjadi root path.
7. if (parent[v] == -1 && capacity[u][v] > 0): kondisi BFS. Hanya push v bila belum dikunjungi dan ada kapasitas residual.
8. if (v == t) return true;: early termination saat tujuan ditemukan. Path sudah pasti shortest karena BFS.
9. for (int v = t; v != s; v = parent[v]): rekonstruksi path dari t ke s via array parent. Loop mundur.
10. flow = std::min(flow, capacity[u][v]): hitung bottleneck — kapasitas residual minimum sepanjang path. Inilah jumlah flow yang bisa di-push.
11. capacity[u][v] -= flow; capacity[v][u] += flow;: augment flow. Kurangi kapasitas forward (sudah dipakai), tambah kapasitas backward (memungkinkan “membatalkan” flow nanti).
12. total += flow: akumulasi total flow.
13. Hasil = 14:
    • Augment 1: BFS temukan S → A → T. Bottleneck min(10, 4) = 4. Push 4. Sisa: S→A=6, A→T=0. Total = 4.
    • Augment 2: BFS temukan S → B → T. Bottleneck min(8, 10) = 8. Push 8. Sisa: S→B=0, B→T=2. Total = 12.
    • Augment 3: BFS temukan S → A → B → T. Bottleneck min(6, 2, 2) = 2. Push 2. Sisa: S→A=4, A→B=0, B→T=0. Total = 14.
    • Augment 4: BFS tidak temukan path → selesai.

Teorema Max-Flow Min-Cut #

Teorema: Pada setiap flow network, nilai max flow = kapasitas min cut.

Min cut adalah partisi V = S ∪ T dengan s ∈ S dan t ∈ T, sehingga total kapasitas edge dari S ke T minimum.

Pada contoh di atas:

• Cut {S, A, B} | {T}: edge A → T (4) dan B → T (10) = 14. ✓ Sama dengan max flow!
• Cut {S} | {A, B, T}: edge S → A (10) dan S → B (8) = 18. Lebih besar.
• Cut {S, A} | {B, T}: edge S → B (8) dan A → T (4) dan A → B (2) = 14. ✓ Sama!

Hasil: min cut = 14 = max flow. Konfirmasi teorema.

Cara Menemukan Min Cut Setelah Max Flow #

Setelah algoritma berhenti (tidak ada augmenting path), jalankan BFS/DFS dari s pada residual graph — node yang terjangkau = S, sisanya = T. Edge-edge dari S ke T yang kapasitas aslinya > 0 (atau lebih tepatnya, edge dari S ke T di graph asli dengan f(u,v) = c(u,v), yaitu kapasitas residual forward = 0) adalah anggota min cut.

Kompleksitas #

Komparasi Algoritma Max Flow #

Aplikasi Nyata #

• Bipartite matching: max matching = max flow dengan sumber ke semua node kiri, semua node kanan ke tujuan.
• Project selection: pilih subset proyek dengan constraint dependensi — reduksi ke min cut.
• Image segmentation: graph pixel → min cut → segment foreground/background.
• Circulation problem: tambahkan edge t → s dengan kapasitas ∞ — flow konservasi semua node.
• Network capacity planning: berapa bandwidth maksimum antar dua titik di jaringan.
• Sport elimination: apakah tim X masih bisa menang liga? Reduksi ke max flow.

Ringkasan #

• Max flow = aliran maksimum dari sumber s ke tujuan t tanpa melanggar kapasitas.
• Min cut = partisi (S, T) dengan total kapasitas edge S → T minimum.
• Teorema max-flow min-cut: max flow = min cut (nilai numerik sama).
• Ford-Fulkerson: iteratif cari augmenting path dan augment. Kompleksitas O(E · |f|).
• Edmonds-Karp: Ford-Fulkerson dengan BFS = O(V · E²), konvergensi terjamin.
• Residual graph: kapasitas forward dikurangi flow, kapasitas backward = flow (untuk membatalkan).
• Aplikasi: bipartite matching, image segmentation, project selection, sport elimination.

Section 16 (algoritma graph) selesai. Anda kini memiliki perangkat lengkap untuk menyelesaikan persoalan graph modern — dari traversal dasar (BFS/DFS) hingga algoritma tingkat lanjut (SCC, articulation points, max flow).