Kalkulator Aliran Jaringan (Aliran Maksimum)

Tentang Kalkulator Aliran Jaringan (Aliran Maksimum)

Kalkulator Aliran Jaringan Aliran Maksimum menghitung aliran maksimum dari sumber (source) s yang dipilih ke muara (sink) t yang dipilih dalam jaringan terarah berkapasitas apa pun. Di balik layar, alat ini menjalankan metode Ford-Fulkerson dengan jalur augmentasi pencarian melebar (BFS) (algoritma Edmonds-Karp), lalu mencatat setiap jalur yang ditemukannya sehingga Anda dapat memutar ulang seluruh proses keputusan satu iterasi pada satu waktu. Halaman hasil juga memunculkan min-cut — partisi bottleneck yang membuktikan nilai aliran Anda benar-benar optimal.

Apa Itu Masalah Aliran Maksimum?

Jaringan aliran adalah graf terarah G = (V, E) bersama dengan fungsi kapasitas c: E → ℝ_≥0. Dua simpul dibedakan: sumber s (tempat aliran berasal) dan muara t (tempat aliran dikonsumsi). Sebuah aliran f adalah setiap penugasan f(u, v)≥ 0 pada tepi yang mematuhi:

Masalah aliran maksimum menanyakan aliran f yang memaksimalkan |f|. Secara intuitif: jika tepinya adalah pipa air dengan kapasitas tertentu, berapa liter per detik yang dapat Anda kirim dari s ke t?

Cara Kerja Algoritma — Ford-Fulkerson dengan BFS

Algoritma memelihara graf residual di samping aliran saat ini. Untuk setiap tepi (u, v) dengan kapasitas c dan aliran saat ini f, graf residual berisi:

• sebuah tepi residual maju (u, v) dengan kapasitas c − f (berapa banyak lagi yang masih bisa didorong), dan
• sebuah tepi residual balik (v, u) dengan kapasitas f (berapa banyak aliran yang telah dilakukan yang masih bisa dibatalkan).

Pada setiap iterasi, algoritma melakukan pencarian melebar (breadth-first search / BFS) dari s ke t di atas graf residual. Jika jalur ditemukan, kapasitas tepi terkecil di jalur tersebut — bottleneck — ditambahkan ke aliran pada setiap tepi maju dan dikurangi pada setiap tepi balik di sepanjang jalur tersebut. Ini disebut jalur augmentasi. Ketika BFS tidak lagi dapat mencapai t, aliran saat ini adalah optimal.

Menggunakan BFS (daripada pencarian jalur sewenang-wenang) mengubah Ford-Fulkerson menjadi Edmonds-Karp, dengan waktu berjalan yang terjamin sebesar O(V · E²). Ini juga menjamin penghentian pada kapasitas irasional, yang tidak dilakukan oleh Ford-Fulkerson biasa.

Teorema Max-Flow Min-Cut

Sebuah potongan (cut) adalah partisi simpul menjadi dua himpunan (S, T) dengan s ∈ S dan t ∈ T. Kapasitasnya adalah jumlah kapasitas tepi yang mengalir dari S ke T:

Teorema max-flow min-cut (Ford & Fulkerson, 1956) menyatakan:

Alat ini menemukan min-cut secara otomatis. Setelah Edmonds-Karp berakhir, alat ini menjalankan satu lagi BFS dari s pada graf residual; simpul yang terjangkau membentuk S, sisanya membentuk T, dan setiap tepi yang melintasi S → T di graf asli akan jenuh. Jumlah kapasitas mereka tepat sama dengan nilai aliran maksimum — terlihat di hasil utama sebagai "Kapasitas min-cut ✓ mengonfirmasi optimalitas".

Fitur yang Dirancang untuk Pembelajaran

• Animasi langkah demi langkah. Putar ulang setiap jalur augmentasi dengan kontrol putar, jeda, dan langkah. Lihat jalur mana yang dipilih BFS, tepi mana yang menjadi bottleneck, dan bagaimana total aliran bertambah.
• Tiga matriks yang disinkronkan. Beralih antara matriks kapasitas C, matriks aliran akhir f, dan matriks residual C − f — tiga gambaran yang bersama-sama menjadi karakteristik setiap aliran.
• Tampilan partisi min-cut. Simpul sisi-S dan sisi-T terdaftar sebagai chip dengan tepi jenuh yang menyeberang disorot dalam warna merah.
• Tabel tepi per tepi. Untuk setiap tepi: kapasitas, aliran, residual, bilah utilisasi, dan pil saturasi.
• Tata letak berlapis kiri-ke-kanan. Gambar graf dihitung dari jarak BFS dari sumber, sehingga air terlihat "mengalir" dari kiri ke kanan — persis seperti yang digambarkan di buku teks.

Format Input

1. Daftar tepi dengan kapasitas

Satu tepi per baris. Bentuk panah paling mudah dibaca tetapi beberapa alternatif juga berfungsi:

Juga diterima: A, B, 10 · A B 10 · A -> B , 10. Beberapa tepi di antara pasangan yang sama akan dijumlahkan.

2. Matriks kapasitas

Satu baris per baris, nilai dipisahkan oleh spasi atau koma. Entri C[i][j] adalah kapasitas tepi dari simpul i ke simpul j. Gunakan 0 untuk "tidak ada tepi". Matriks harus berbentuk persegi dan diagonalnya harus 0 (tidak ada loop mandiri).

Masukkan label simpul yang cocok di kolom Label matriks (dipisahkan koma atau spasi). Jika dikosongkan, label default ke S, A, B, …, T.

Aplikasi Aliran Maksimum

Contoh Pengerjaan

Contoh cepat "Buku teks" mengkodekan jaringan 6 simpul dengan sumber S dan muara T. Menjalankan Edmonds-Karp menghasilkan empat jalur augmentasi:

1. S → A → B → T dengan bottleneck 4 (tepi A-B adalah pembatas). Total sementara: 4.
2. S → A → D → T dengan bottleneck 6. Total sementara: 10.
3. S → C → D → T dengan bottleneck 4 (tepi D-T sekarang menjadi pembatas, hanya tersisa 4). Total sementara: 14.
4. S → C → D → B → T dengan bottleneck 5. Total sementara: 19.

Algoritma berhenti — tidak ada lagi jalur augmentasi yang ada. Min-cut adalah (S = {S, C}, T = {A, B, D, T}) dengan tepi yang menyeberang S → A (kapasitas 10) dan C → D (kapasitas 9), berjumlah 19 — persis dengan nilai aliran maks.

Cara Menggunakan Kalkulator Ini

1. Pilih format input menggunakan tab — daftar tepi (direkomendasikan) atau matriks kapasitas.
2. Masukkan jaringan Anda. Anda dapat memulai dari contoh cepat dan memodifikasinya. Untuk input matriks, sertakan juga label jika Anda menginginkan nama selain S, A, B, …, T.
3. Tentukan sumber dan muara (atau biarkan kosong untuk mendeteksi S dan T secara otomatis).
4. Klik Hitung Aliran Maksimum. Halaman hasil menunjukkan nilai aliran maks, partisi min-cut, visualisasi graf berlapis, setiap jalur augmentasi, tabel utilisasi tepi, dan tiga matriks (kapasitas, aliran, residual).
5. Putar animasi di bawah graf untuk memutar ulang keputusan algoritma. Klik langkah jalur augmentasi mana pun untuk langsung melompat ke sana.

Batasan

• Simpul: hingga 30 — agar visualisasi dan matriks tetap terbaca.
• Tepi: hingga 200.
• Kapasitas: non-negatif, hingga 10⁹. Kapasitas pecahan diperbolehkan.
• Tidak ada loop mandiri. Loop mandiri tidak membawa aliran dalam formulasi aliran maks standar dan akan ditolak.

Pertanyaan yang Sering Diajukan

Apa itu masalah aliran maksimum?

Diberikan jaringan terarah di mana setiap tepi memiliki kapasitas non-negatif, masalah aliran maksimum menanyakan: berapa banyak aliran yang dapat didorong dari simpul sumber s yang ditentukan ke simpul muara t yang ditentukan, dengan aturan bahwa aliran pada setiap tepi tidak boleh melebihi kapasitasnya dan aliran yang masuk ke setiap simpul non-sumber, non-muara harus sama dengan aliran yang meninggalkannya? Jawabannya disebut nilai aliran maks.

Apa itu metode Ford-Fulkerson?

Ford-Fulkerson adalah teknik umum untuk menghitung aliran maks. Ini secara berulang menemukan jalur augmentasi dari sumber ke muara dalam graf residual dan mendorong aliran sebanyak mungkin sepanjang jalur tersebut (kapasitas bottleneck), lalu memperbarui graf residual. Prosedur berakhir ketika tidak ada lagi jalur augmentasi yang ada. Ketika diimplementasikan dengan pencarian melebar (BFS) untuk pemilihan jalur, ini disebut Edmonds-Karp dan berjalan dalam waktu O(V · E²).

Apa itu min-cut dari jaringan aliran?

Potongan (cut) adalah partisi simpul menjadi dua himpunan S dan T sedemikian rupa sehingga sumber ada di S dan muara ada di T. Kapasitas potongan adalah jumlah kapasitas tepi dari S ke T. Min-cut adalah potongan dengan kapasitas minimum. Teorema max-flow min-cut yang terkenal membuktikan bahwa nilai aliran maksimum selalu sama dengan kapasitas potongan minimum, sehingga menemukan satu akan memberikan yang lain secara gratis.

Apa itu graf residual?

Graf residual melacak berapa banyak lagi aliran yang masih bisa didorong pada setiap tepi. Untuk setiap tepi asli (u, v) dengan kapasitas c dan aliran saat ini f, graf residual berisi tepi maju (u, v) dengan kapasitas c minus f (sisa kapasitas) dan tepi balik (v, u) dengan kapasitas f (aliran yang dapat dibatalkan). Jalur augmentasi menggunakan tepi graf residual, memungkinkan algoritma untuk membatalkan keputusan sebelumnya.

Mengapa alat ini menggunakan BFS untuk jalur augmentasi?

Memilih jalur augmentasi dengan pencarian melebar / BFS (Edmonds-Karp) menjamin penghentian waktu polinomial terlepas dari kapasitas tepi. Ford-Fulkerson biasa dengan strategi pencarian jalur sewenang-wenang dapat berulang untuk jumlah iterasi eksponensial pada input patologis, dan pada kapasitas irasional mungkin tidak berhenti sama sekali. BFS juga menghasilkan jalur augmentasi terpendek, yang lebih mudah dibaca dan dipahami.

Apa arti tepi jenuh (saturated edge)?

Tepi dikatakan jenuh ketika alirannya sama dengan kapasitasnya, sehingga tidak ada aliran tambahan yang dapat didorong padanya. Tepi jenuh adalah hambatan (bottleneck) jaringan, dan setiap min-cut seluruhnya terdiri dari tepi jenuh dari sisi S ke sisi T dari potongan tersebut. Alat ini menyoroti tepi jenuh dalam warna merah sehingga Anda dapat melihat struktur bottleneck dalam sekejap.

Bacaan Lebih Lanjut

• Maximum flow problem — Wikipedia
• Ford–Fulkerson algorithm — Wikipedia
• Edmonds–Karp algorithm — Wikipedia
• Max-flow min-cut theorem — Wikipedia