Aliran Maksimum

1. Introduction

Aliran Maksimum (Max Flow) adalah salah satu dari problem dalam kelompok problem yang melibatkan aliran dalam sebuah jaringan.

Dalam problem Max Flow, kita ingin mencari aliran maksimum dari sebuah simpul source tertentu s ke sebuah simpul sink tertentu t pada sebuah graf G yang berbobot dan berarah.

Ada beberapa algoritma untuk mencari aliran maksimum yang meliputi metode Ford-Fulkerson, algoritma Edmonds-Karp, dan algoritma Dinic (ada algoritma-algoritma lainnya, namun belum terdapat dalam visualisasi di sini).

Problem ganda dari Max Flow adalah Min Cut, yaitu dengan mencari aliran maksimum s-t dari G, kita juga sekaligus menemukan potongan terkecil s-t dari G, yaitu himpunan edge dengan bobot minimum yang harus dbuang dari G sehingga tidak ada lagi jalur dari s ke t di G.

1-1. Motivasi-Aplikasi

Max-Flow (or Min-Cut) problems arise in various applications, e.g.,

  1. Transportation-related problems (what is the best way to send goods/material from s (perhaps a factory) to t (perhaps a super-sink of all end-users))
  2. Network attacks problems (sabotage/destroy some edges to disconnect two important points s and t)
  3. (Bipartite) Matching and Assignment problems (that also has specialized algorithms, see Graph Matching visualization
  4. Sport teams prospects
  5. Image segmentation, etc...

2. Visualisasi

Halaman visualisasi ini akan menunjukkan eksekusi dari algoritma Aliran Maks (Max Flow) yang berjalan dalam graf flow (residu).


Untuk membuat visualisasi dari graf-graf flow ini konsisten, kami memaksa aturan penggambaran graf di halaman ini dimana simpul source s/simpul sink t selalu adalah simpul 0/V-1 dan selalu digambar pada sisi paling-kiri/paling-kanan dari visualisasi ini. Sebuah batasan lainnya adalah kapasitas-kapasitas sisi adalah bilangan-bilangan bulat diantara [1..99].

Batasan-batasan untuk keperluan visualisasi ini tidak ada untuk masalah max flow standar.

2-1. Masukan

Masukan untuk algoritma Max Flow adalah graf flow (graf berarah berbobot G = (V, E) di mana bobot sisi e mewakili kapasitas c(e) (satuannya tergantung pada masalah, misalnya, liter/detik, orang/jam, dll) dari aliran yang dapat melewati sisi tersebut) dengan dua simpul yang dibedakan: simpul source s (dengan in-degree 0) dan simpul sink/tujuan/target t (dengan out-degree 0). Graf flow biasanya terhubung s-t, yaitu, ada setidaknya satu jalur dari s ke t (jika tidak, aliran maksimum secara trivial adalah 0).

Dalam visualisasi ini, dua input tambahan dari s (biasanya simpul 0) dan t (biasanya simpul V-1) diminta sebelum eksekusi algoritma Max Flow yang dipilih dan dapat disesuaikan oleh pengguna.

2-2. Keluaran

Keluaran dari algoritma Max Flow adalah nilai flow maksimum dan penugasan flow f pada setiap sisi yang memenuhi dua batasan penting:

sehingga nilai flow (value(f) = ∑v: (s, v) ∈ E f(s,v)) adalah maksimum.

Dalam visualisasi ini, kita fokus menunjukkan nilai flow maksimum terakhir dan komponen ST-min cut akhir pada akhir setiap eksekusi algoritma aliran maksimum, daripada penugasan tepat aliran f pada setiap sisi, yaitu, f(e) harus dihitung secara manual dari kapasitas awal c(e) (bingkai pertama dari animasi) dikurangi kapasitas residual akhir dari sisi e (bingkai terakhir dari animasi). Fitur yang hilang ini kemungkinan akan ditambahkan pada iterasi berikutnya dari halaman visualisasi ini.


Diskusi: Adakah cara lain untuk menghitung nilai aliran value(f)?

2-3. Jawabannya

[This is a hidden slide]

2-4. Graf Residu

n Pada awal tiga algoritma Max Flow yang dibahas dalam visualisasi ini (metode Ford-Fulkerson, algoritma Edmonds-Karp, dan algoritma Dinic), graf flow awal dikonversi menjadi graf residual (dengan potensi penambahan sisi flow balik dengan kapasitas awal nol).

Sisi-sisi dalam graf residual menyimpan kapasitas sisa dari sisi-sisi tersebut yang dapat digunakan oleh aliran-aliran di masa depan. Pada awalnya, kapasitas sisa ini sama dengan kapasitas asli seperti yang ditentukan dalam graf aliran input.

Algoritma Max Flow akan mengirimkan flow untuk menggunakan beberapa (atau semua) dari kapasitas yang tersedia ini, secara iteratif.

Setelah kapasitas sisa dari suatu sisi mencapai 0, sisi tersebut tidak lagi dapat menerima aliran tambahan. Di masa mendatang, kami akan memperbarui visualisasi ini sehingga setiap sisi dalam graf residual yang memiliki kapasitas 0 (termasuk nol awal dari sisi aliran balik) tidak ditampilkan dalam visualisasi.

3. Masukan Graf Flow

Ada tiga sumber berbeda untuk menspesifikasikan graf masukan:

  1. Gambar Graf: Anda dapat menggambar graf berarah dan berbobot apapun dengan simpul 0 sebagai simpul sumber default (sisi kiri dari layar) dan simpul V-1 sebagai simpul akhiran default (sisi kanan dari layar).
  2. Modeling: Banyak problem graf yang dapat direduksi menjadi masalah aliran maks. Di visualisasi ini, kami telah menyediakan contoh-contoh modeling untuk masalah Pencocokan Bipartit dengan Kardinalitas Maksimum (Maximum Cardinality Bipartite Matching, MCBM), masalah Rook Attack(tidak tersedia saat ini), dan masalah Baseball Elimination (tidak tersedia saat ini).
  3. Graf-Graf Contoh: Anda dapat memilih dari daftar graf-graf contoh pilihan kami untuk memulai.

4. Algoritma Max-Flow

Terdapat tiga algoritma Max Flow berbeda dalam visualisasi ini:

  1. Metode Ford-Fulkerson yang pelan O(mf × E),
  2. Algoritma Edmonds-Karp O(V × E^2) Edmonds-Karp, atau
  3. Algoritma Dinic O(V^2 × E).

Terdapat beberapa algoritma max flow lainnya, tetapi mereka masih belum ada dalam visualisasi ini.

4-1. Mirip Namun Tak Sama

Untuk tiga algoritma Max Flow yang dibahas dalam visualisasi ini, flow berturut-turut dikirim dari simpul source s ke simpul sink t melalui jalur augmentasi yang tersedia (jalur augmentasi adalah jalur dari s ke t yang melewati sisi-sisi dengan kapasitas residual positif (c(e)-f(e)) yang tersisa).

Ketiga algoritma Max Flow dalam visualisasi ini memiliki perilaku berbeda dalam cara mereka menemukan jalur augmentasi.

Namun, semua tiga algoritma Max Flow dalam visualisasi ini berhenti ketika tidak ada lagi jalur augmentasi yang mungkin dan melaporkan nilai flow maksimum (dan penugasan flow pada setiap sisi dalam graf flow).

Nanti kita akan membahas bahwa nilai flow maksimum ini juga merupakan nilai potongan minimum dari graf flow (Teorema Max-Flow/Min-Cut yang terkenal itu).

5. Algoritma-Algoritma Aliran Maks (Max Flow) 

mulai dari 0 flow
while terdapat jalur augmentasi: // algoritma iteratif
  cari jalur augmentasi (untuk sekarang, sembarang graf travesal bisa)
  hitung bottleneck kapasitas
  tambahkan flow pada jalur sebanyak kapasitas bottleneck

5-1. Teorema Max-Flow/Min-Cut

Teorema terkenal ini menyatakan bahwa dalam jaringan aliran, aliran maksimum (max flow) dari s ke t sama dengan total bobot sisi-sisi dalam pemotongan minimum (min cut), yaitu total bobot sisi-sisi terkecil yang harus dihilangkan untuk memutuskan hubungan s dari t.


Dalam kelas Ilmu Komputer yang khas, dosen biasanya akan meluangkan waktu untuk menjelaskan teorema ini dengan benar (menjelaskan apa itu st-cut, kapasitas st-cut, aliran bersih melintasi st-cut yang sama dengan penugasan aliran f saat ini yang tidak akan melebihi kapasitas pemotongan, dan akhirnya Teorema Max-Flow/Min-Cut). Untuk visualisasi ini, kami hanya mengambil pernyataan ini apa adanya.


Diskusi: Untuk kelas nyata di NUS, kami sebenarnya akan membahas teorema-teorema ini.

5-2. Cut dan Flow, Definisi

[This is a hidden slide]

5-3. Cut dan Flow, Sama

[This is a hidden slide]

5-4. Cut dan Flow, Weak Duality

[This is a hidden slide]

5-5. Teorema Max-Flow/Min-Cut, Formalitas

[This is a hidden slide]

5-6. Teorema Jalur Augmentasi

Menggunakan Teorema Max-Flow/Min-Cut, kita kemudian dapat membuktikan bahwa flow f adalah maxflow jika dan hanya jika tidak ada (lagi) jalur augmentasi yang tersisa dalam graf residual.

Karena inilah yang dilakukan oleh Metode Ford-Fulkerson, kita dapat menyimpulkan kebenaran dari Metode Ford-Fulkerson ini, yaitu, jika Metode Ford-Fulkerson berakhir, maka tidak ada jalur augmentasi yang tersisa dan dengan demikian flow yang dihasilkan adalah maksimum (dan kita juga dapat membangun Min-Cut yang setara, pada slide berikutnya).

5-7. Mencari Sisi dalam Min-Cut

We can constructively identify the edges in the Min-Cut as follows:

  1. Run Ford-Fulkerson (or any other Max Flow) algorithm until it terminates.
  2. Let S be the set of vertices that are still reachable from the source s.
    We can run DFS (or BFS) in the residual graph from the source vertex s.
    All the vertices that are still reachable are in S.
    Let T be the remaining vertices, i.e., T = V \\ S.
  3. For every vertex in S, enumerate outgoing edges:
    If edge exits S (and into T), add to min-cut.
    If both ends of edge are in S, then continue.

That's it, (S,T) is an st-cut, edges from (S → T) are the minimum cut, and the flow that goes through this minimum cut (S,T) is the maximum possible.

5-8. Bukti

[This is a hidden slide]

5-9. Analisis Metode Ford-Fulkerson

Ford-Fulkerson method always terminates if the capacities are integers.


This is because every iteration of Ford-Fulkerson method always finds a new augmenting path and each augmenting path must have a bottleneck capacity at least 1 (due to that integer constraint). Therefore, each iteration increases the flow of at least one edge by at least 1, edging the Ford-Fulkerson closer to termination.


As the number of edges is finite (as well as the finite max capacity per edge), this guarantees the eventual termination of Ford-Fulkerson method when the max flow mf is reached and there is no more augmenting path left.


In the worst case, Ford-Fulkerson method runs for mf iterations, and each time it uses O(E) DFS. The rough overall runtime is thus O(mf × E) — this is actually not desirable especially if the value of mf is a huge number.


Discussion: What if the capacities are rational numbers? What if the capacities are floating-point numbers?

5-10. Kapasitas Bilangan Tak Bulat

[This is a hidden slide]

6. Jalur Augmentasi Terpendek Dahulu

Ide: Bagaimana jika kita tidak mempertimbangkan semua jalur augmentasi, tetapi mempertimbangkan jalur augmentasi dengan jumlah sisi yang terlibat paling sedikit terlebih dahulu (sehingga kita tidak menempatkan flow pada lebih banyak sisi daripada yang diperlukan).

6-1. Ide 1: Edmonds-Karp

Implementasi: Pertama, kita mengabaikan kapasitas dari sisi-sisi terlebih dahulu (anggap semua sisi dalam graf residual memiliki bobot 1), dan kita menjalankan BFS O(E) untuk menemukan jalur augmentasi terpendek (dalam hal jumlah sisi yang digunakan). Segala sesuatu lainnya sama seperti Metode Ford-Fulkerson dasar yang diuraikan sebelumnya.

Dapat dibuktikan bahwa Edmonds-Karp akan menggunakan paling banyak O(VE) iterasi sehingga berjalan paling lama dalam waktu O(VE * E) = O(VE^2).

6-2. Bukti

[This is a hidden slide]

6-3. Ide 2: Dinic

Algoritma Dinic juga menggunakan startegi yang mirip dengan mencari jalur augmentasi terpendek terlebih dahulu.
Namun Algoritma Dinic berjalan dalam waktu lebih cepat O(V^2 × E) karena lebih efisien menggunakan jalur terpendek BFS.
Slide ini akan dikembangkan.

7. Implementasi Algoritma Max-Flow Efisien

Pada saat anda mengerjakan masalah Max Flow (atau Min Cut), kita tidak perlu menciptakan roda tiap kali.


Anda dapat menggunakan/memodifikasi kode implementasi kami untuk algoritma Max Flow (Edmonds-Karp/Dinic): maxflow.cpp | py | java | ml.