Kontraxample ke algoritma max-flow dengan bobot yang tidak rasional?

Diketahui bahwa Ford-Fulkerson atau Edmonds-Karp dengan heuristic pipa gemuk (dua algoritma untuk max-flow) tidak perlu berhenti jika beberapa bobotnya tidak rasional. Bahkan, mereka bahkan dapat bertemu pada nilai yang salah ! Namun, semua contoh yang dapat saya temukan dalam literatur [referensi di bawah ini, ditambah referensi di dalamnya] hanya menggunakan nilai irasional tunggal: rasio emas konjugasi , dan nilai-nilai lain yang rasional, atau merupakan kelipatan rasional dari. Pertanyaan utama saya adalah:$\phi' = (\sqrt{5}-1)/2$$\phi'$

Pertanyaan Umum: Apa yang terjadi dengan nilai-nilai irasional lainnya?

Misalnya (tetapi jangan merasa Anda harus menjawab semua ini untuk diposkan - Saya akan menemukan jawaban yang menarik untuk salah satu dari mereka, atau untuk pertanyaan lain yang termasuk dalam pertanyaan umum di atas):

1. Dengan adanya , dapatkah seseorang membuat (atau bahkan menunjukkan keberadaan) contoh tandingan seperti itu?$\alpha \in \mathbb{R}$

2. Lebih lemah: apakah ada contoh yang diketahui yang menggunakan nilai irasional yang pada dasarnya berbeda dari ? Yaitu, adakah beberapa yang bukan kelipatan rasional dari (atau lebih kuat tidak dalam ) dan sedemikian rupa sehingga ada contoh tandingan untuk Ford-Fulkerson dan / atau Edmonds- Karp di mana semua bobot terletak di ?$\phi'$$\alpha$$\phi'$$\mathbb{Q}(\phi')$$\mathbb{Q}(\alpha)$

3. Di arah lain, apakah ada irasional sehingga Ford-Fulkerson (resp., Edmonds-Karp) berhenti dengan nilai yang benar pada semua grafik yang bobotnya semua dari ? (Atau lebih kuat, dari ?)$\alpha$Q ( α $\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$$\mathbb{Q}(\alpha)$

Dalam semua kasus, saya ingin mengasumsikan sesuatu seperti model RAM nyata, sehingga perhitungan aritmatika dan perbandingan angka nyata dilakukan dalam waktu yang konstan.

(Ada algoritma max-flow lain yang dikenal berjalan dalam waktu yang sangat polinomial, bahkan dengan bobot nyata yang sewenang-wenang, yang mungkin mengapa jenis pertanyaan ini mungkin belum dieksplorasi lebih lanjut. Tetapi setelah mengajarkan algoritma ini di kelas algoritma sarjana saya , Saya masih penasaran tentang ini.)

Referensi

• Contoh tandingan minimal untuk Ford-Fulkerson diberikan oleh Zwick TCS 1999

• Contoh tandingan untuk Edmonds-Karp diberikan oleh Queyranne atau Queyranne Math. Oper. Res. 1980 , meskipun saya tidak tahu apakah itu minimal.

• Keduanya dapat ditemukan dalam catatan kuliah Jeff Erickson , dengan yang pertama di Bagian 23.5 dan yang kedua sebagai Latihan 14 dari Kuliah 23.

$r$

• $n=6$$m=8$
• di mana tujuh busur memiliki kapasitas bilangan bulat,
• $r$
• dan yang tidak dapat diakhiri oleh Ford-Fulkerson.

Ini telah dibuktikan di koran

Toshihiko Takahashi:
"Jaringan Paling Sederhana dan Terkecil di mana Prosedur Aliran Maksimal Ford-Fulkerson Mungkin Gagal Dihentikan"
Jurnal Pemrosesan Informasi 24, hal 390-394, 2016.
Tautan: https: //www.jstage.jst.go. jp / artikel / ipsjjip / 24/2 / 24_390 / _article

Terima kasih atas pertanyaan yang saya temukan tidak benar-benar alami tetapi cukup lucu.

Saya telah melihat bagian Ford-Ferkulson dan saya pikir saya telah menemukan grafik yang merupakan contoh tandingan dan hanya memiliki satu sisi dengan kapasitas irasional α (grafik dapat bekerja untuk setiap α).

Ini adalah PDF yang merangkum usaha saya: https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf (maaf ini agak singkat untuk saat ini tetapi jangan ragu untuk bertanya)

Jelas Ford-Felkurson memungkinkan kita memilih jalur augmentasi seperti yang kita inginkan ... Saya tidak yakin ini akan mungkin untuk Edmond-Karp.