Cara tercepat untuk menemukan potongan minimum dari aliran maksimum?

8

Ford-Fulkerson dapat menemukan aliran yang jarang dalam waktu linier dalam ukuran aliran dan jumlah node jika tepi memiliki kapasitas unit.

Bagaimana saya bisa menggunakan aliran st sparse untuk menemukan st min-cut dalam waktu sebanding dengan ukuran aliran dan jumlah node saya, untuk kasus max-flow volume rendah / volume rendah?

graph-algorithms max-flow max-flow-min-cut Elliot JJ
sumber
Apakah ada referensi cepat untuk definisi aliran jarang?
chazisop
1. Melintasi semua tepi dan menemukan tepi jenuh tampak cukup sah secara intuitif. Tapi satu kelemahannya adalah, tidak semua tepi jenuh harus dimiliki oleh min-cut. 2. Min-cut harus menjadi set tepi, bukan set simpul. 3. Jadi solusi khas seharusnya hanya jawaban yang diterima di atas. Dari max flow network (Baik diberikan atau Anda dapat menghitung oleh Ford-Fulkerson atau Edmunds-Karp), DFS atau BFS dari s, tandai semua simpul yang dapat dijangkau (Proses mencoba menemukan jalur penambahan tetapi Anda tahu y
Jinggang

Jawaban:

8

Jika Anda tidak menggunakan alur per se, tetapi gunakan algoritma Ford-Fulkerson (atau versi tertentu, seperti Edmonds-Karp), Anda bisa mendapatkan max-flow dan min-cut secara langsung sebagai hasilnya. Saat mencari jalur pembesaran, Anda melakukan traversal, di mana Anda menggunakan beberapa bentuk antrian dari simpul yang belum dikunjungi (dalam versi Edmonds-Karp, Anda menggunakan BFS, yang berarti antrian FIFO). Dalam iterasi terakhir, Anda tidak dapat mencapai dari (bagaimanapun, ini adalah kriteria terminasi). Pada titik ini, himpunan node yang Anda capai membentuk bagian- dari potongan, sedangkan node yang Anda tidak mencapai membentuk bagian- .tsst

Node daun dari pohon traversal Anda membentuk "pinggiran" dari -part, sedangkan node dalam antrian traversal Anda membentuk pinggiran -part, dan apa yang Anda inginkan adalah himpunan tepi dari pinggiran ke pinggiran Ini juga dapat dengan mudah dipertahankan selama traversal: Cukup tambahkan tepi pada potongan ketika diperiksa, dan mengarah ke simpul yang belum dikunjungi, dan menghapusnya jika dilintasi (sehingga targetnya menjadi dikunjungi). Kemudian, setelah Ford-Fulkerson selesai, Anda akan memiliki min-cut Anda (atau, lebih tepatnya, salah satunya) di sana. Waktu berjalan akan (asimtotik) identik dengan Ford-Fulkerson (atau Edmonds-Karp atau versi apa pun yang Anda gunakan), yang akan memberi Anda apa yang Anda cari.stst

Magnus Lie Hetland
sumber
-1

Apakah ada referensi cepat untuk definisi aliran jarang?

Dalam kasus umum, memiliki max-flow cukup mudah untuk menentukan min-cut, melalui teorema max-flow, min-cut. Tepi-tepi yang sepenuhnya jenuh membentuk set cut, jadi dengan memilih satu simpul untuk setiap tepi tersebut, seseorang dapat membentuk min-cut. Sepele, ini adalah O (m) dalam kasus terburuk, dan juga jika seseorang membuat waktu berjalan keluaran-sensitif, maka jumlah tepi dalam aliran atau bahkan lebih baik, jumlah tepi jenuh dalam aliran, selalu merupakan bagian atas terikat pada waktu berjalan dari algoritma untuk menemukan min-cut dari max-flow. Jadi jika Anda memiliki modifikasi yang menemukan aliran ses dalam waktu linier dalam ukuran aliran, menemukan potongan minimum tidak akan mengubah runtime algoritma secara asimptotik.

chazisop
sumber
2
Saya tidak punya definisi khusus. Hanya sesuatu di mana ford-fulkerson secara asimptotik lebih cepat dari yang lainnya. Jika semua tepi saya memiliki kapasitas unit, bukankah banyak di antaranya jenuh, termasuk tepi yang jika dilepas dapat dengan mudah diganti tanpa memengaruhi volume aliran maks? Saya dapat menghapus semua tepi ini dan membentuk potongan, tetapi kemudian saya tidak yakin bagaimana saya akan mengganti yang sebenarnya tidak perlu saya hapus.
Elliot JJ
Itu tergantung pada grafik. Jika Anda memiliki kapasitas unit dan grafik yang padat, sangat mungkin bahwa Anda akan memiliki banyak aliran dengan nilai maksimal, ini pada gilirannya dapat diartikan sebagai Anda dapat memiliki sejumlah besar pemotongan min yang berbeda juga. Lihat juga referensi ini: en.wikipedia.org/wiki/Max-flow_min-cut_theorem
chazisop