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

Masalah Max-Flow (atau Min-Cut) muncul dalam beberapa aplikasi, seperti,

  1. Masalah terkait transportasi (apa cara terbaik untuk mengirimkan barang dari s (mungkin sebuah pabrik) ke t (mungkin sebuah distributor)
  2. Masalah terkait penyerangan jaringan (sabotasi/hancurkan beberapa sisi untuk memutuskan dua titik penting s dan t)
  3. Pencocokan (Bipartit) dan masalah Penugasan (yang juga mempunyai algoritma spesifik, lihatlah visualisasi Pencocokan Graf
  4. Prospek tim olahraga
  5. Segmentasi gambar, dll...

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

Kita bisa membangun sisi-sisi dalam Min-Cut sebagai berikut:

  1. Jalankan Ford-Fulkerson (atau algoritma MaxFlow lainnya) sampai selesai.
  2. Misalkan S merupakan himpunan simpul yang masih bisa dicapai dari source s.
    Kita jalankan DFS (atau BFS) dalam graf residu dari source s.
    Semua simpul yang masih dicapai berada di S.
    Misalkan T merupakan himpunan simpul sisanya T = V \\ S.
  3. Untuk semua sisi dalam S, cek semua sisi yang keluar:
    Jika sisi keluar dari S (dan masuk T), tambahkan sisi ini ke min-cut.
    Jika kedua titik akhir sisi berada dalam S, lanjutkan

Itu saja, (S,T) adalah sebuah st-cut, sisi dari (S → T) adalah perpotongan minimum (mincut), dan aliran yang melalui perpotongan minimum (S,T) adalah semaksimum mungkin.

5-8. Bukti

[This is a hidden slide]

5-9. Analisis Metode Ford-Fulkerson

Metode Ford-Fulkerson selalu berakhir jika kapasitanya adalah bilangan bulat.

Ini karena setiap iterasi metode Ford-Fulkerson selalu menemukan jalur augmentasi baru dan setiap jalur augmentasi harus memiliki kapasitas bottleneck minimal 1 (karena batasan bilangan bulat tersebut). Oleh karena itu, setiap iterasi meningkatkan aliran dari setidaknya satu sisi minimal 1, membawa Ford-Fulkerson lebih dekat ke penghentian.

Karena jumlah sisi adalah terbatas (begitu juga dengan kapasitas maksimum per sisi), ini menjamin penghentian metode Ford-Fulkerson ketika max flow mf tercapai dan tidak ada lagi jalur augmentasi yang tersisa.

Dalam kasus terburuk, metode Ford-Fulkerson berjalan selama mf iterasi, dan setiap kali menggunakan O(E) DFS. Waktu berjalan keseluruhan kira-kira adalah O(mf × E) — ini sebenarnya tidak diinginkan terutama jika nilai mf adalah angka yang sangat besar.

Diskusi: Bagaimana jika kapasitasnya adalah bilangan rasional? Bagaimana jika kapasitasnya adalah bilangan floating-point?

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.