Kontrprzykład do algorytmów maksymalnego przepływu z irracjonalnymi wagami?

Wiadomo, że Ford-Fulkerson lub Edmonds-Karp z heurystyczną grubą rurą (dwa algorytmy dla maksymalnego przepływu) nie muszą się zatrzymywać, jeśli niektóre ciężary są nieracjonalne. W rzeczywistości mogą nawet zbierać się na niewłaściwej wartości! Jednak wszystkie przykłady, które mogłem znaleźć w literaturze [odnośniki poniżej oraz odnośniki w nich] wykorzystują tylko jedną wartość nieracjonalną: sprzężony złoty współczynnik$\phi' = (\sqrt{5}-1)/2$oraz inne wartości, które są albo wymierne, albo są racjonalnymi wielokrotnościami $\phi'$. Moje główne pytanie brzmi:

Pytanie ogólne: Co dzieje się z innymi irracjonalnymi wartościami?

Na przykład (ale nie czuję się tak, jakbyś musiał odpowiedzieć na wszystkie z nich, aby opublikować - znajdę interesującą odpowiedź na jedno lub inne pytania, które wchodzą w zakres powyższego pytania ogólnego):

1. Biorąc pod uwagę dowolny $\alpha \in \mathbb{R}$, czy można skonstruować (lub nawet wykazać istnienie) takich kontrprzykładów?

2. Słabiej: czy istnieją znane przykłady, które wykorzystują irracjonalną wartość zasadniczo inną niż$\phi'$? Czy to jest jakieś$\alpha$ który nie jest racjonalną wielokrotnością $\phi'$ (lub bardziej zdecydowanie nie w $\mathbb{Q}(\phi')$) i takie, że istnieją kontrprzykłady do Forda-Fulkersona i / lub Edmondsa-Karpa, w których leżą wszystkie ciężary $\mathbb{Q}(\alpha)$?

3. W przeciwnym kierunku istnieje irracjonalność $\alpha$tak, że Ford-Fulkerson (odpowiednio. Edmonds-Karp) zatrzymuje się z prawidłową wartością na wszystkich wykresach, których wagi są od$\mathbb{Q} \cup \{q\alpha : q \in \mathbb{Q}\}$? (Lub silniej, z$\mathbb{Q}(\alpha)$?)

We wszystkich przypadkach chcę założyć coś takiego jak prawdziwy model pamięci RAM, aby dokładne arytmetyki i dokładne porównania liczb rzeczywistych były wykonywane w stałym czasie.

(Istnieją inne algorytmy maksymalnego przepływu, o których wiadomo, że działają w silnie wielomianowym czasie, nawet z dowolnymi rzeczywistymi wagami, i być może dlatego tego rodzaju pytania nie były dalej badane. Ale właśnie nauczyłem tych algorytmów w mojej klasie algorytmów licencjackich , Nadal mnie to ciekawi.)

Bibliografia

• Minimick kontrprzykład dla Forda-Fulkersona podał Zwick TCS 1999

• Kontrprzykład dla Edmondsa-Karpa podał Queyranne lub Queyranne Math. Oper. Res. 1980 , choć nie wiem czy to minimalne.

• Oba można znaleźć w notatkach z wykładu Jeffa Ericksona , z których pierwszy w części 23.5, a drugi jako ćwiczenie 14 wykładu 23.

Odpowiedź brzmi: dla każdej nieracjonalnej liczby $r$istnieje sieć

• z $n=6$ wierzchołki i $m=8$ łuki,
• w których siedem łuków ma całkowitą pojemność,
• w którym jeden łuk ma pojemność $r$,
• i na których Ford-Fulkerson może nie zostać rozwiązany.

Zostało to udowodnione w artykule

Toshihiko Takahashi:
„Najprostsza i najmniejsza sieć, w której procedura maksymalnego przepływu Ford-Fulkerson może nie zostać
zakończona ” Journal of Information Processing 24, str. 390-394, 2016.
Link: https: //www.jstage.jst.go. jp / article / ipsjjip / 24/2 / 24_390 / _article

Dziękuję za pytanie, które nie było dla mnie naturalne, ale mimo wszystko dość zabawne.

Zajrzałem do części Forda-Ferkulsona i wydaje mi się, że znalazłem wykres, który jest kontrprzykładem i ma tylko jedną krawędź o nieracjonalnej pojemności α (wykres może działać dla dowolnego α).

Oto plik PDF podsumowujący moją próbę: https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf (przepraszam, na razie jest trochę lakoniczny, ale nie wahaj się zadawać pytań)

Oczywiście Ford-Felkurson pozwala nam wybrać ścieżkę powiększania, jak sobie życzymy ... Nie jestem pewien, czy byłoby to możliwe dla Edmond-Karp.