Контрпример к алгоритмам максимального потока с иррациональными весами?

9

Известно, что Форд-Фулкерсон или Эдмондс-Карп с эвристикой толстой трубы (два алгоритма для максимального потока) не должны останавливаться, если некоторые веса нерациональны. На самом деле они могут даже сходиться на неправильном значении! Однако во всех примерах, которые я мог найти в литературе [ссылки ниже, плюс ссылки в них], используется только одно иррациональное значение: сопряженное золотое сечение и другие значения, которые либо рациональны, либо рациональны, кратны . Мой главный вопрос:φ'знак равно(5-1)/2φ'

Общий вопрос: что происходит с другими иррациональными ценностями?

Например (но не думаю, что вы должны отвечать на все эти вопросы, чтобы опубликовать их - я бы нашел интересный ответ на любой из них или на другие вопросы, которые подпадают под приведенный выше общий вопрос)

  1. При наличии любого , можно ли построить (или даже показать существование) такие контрпримеры?αр

  2. Более слабо: известны ли примеры, в которых используется иррациональное значение, существенно отличающееся отφ'? То есть есть лиα который не является рациональным кратным φ' (или более сильно не в Q(φ')) и такие, что существуют контрпримеры к Форду-Фулкерсону и / или Эдмондсу-Карпу, где лежат все веса Q(α)?

  3. В другом направлении, существует ли иррациональное αтакой, что Форд-Фулкерсон (соответственно, Эдмондс-Карп) останавливается с правильным значением на всех графиках , вес которых все изQ{Qα:QQ}? (Или более сильно, изQ(α)?)

Во всех случаях я хочу предположить что-то похожее на реальную модель ОЗУ, чтобы точные арифметические и точные сравнения действительных чисел выполнялись в постоянное время.

(Существуют другие алгоритмы с максимальным потоком, которые, как известно, выполняются за строго полиномиальное время, даже с произвольными действительными весами, и, возможно, поэтому этот тип вопроса, возможно, не был дополнительно исследован. Но только что я учил эти алгоритмы в моем классе алгоритмов старшекурсников Мне все еще интересно об этом.)

Ссылки

Джошуа Грохов
источник

Ответы:

12

Ответ в том, что для каждого иррационального числа рсуществует сеть

  • с Nзнак равно6 вершины и мзнак равно8 дуги,
  • в котором семь дуг имеют целочисленную емкость,
  • в котором одна дуга имеет емкость р,
  • и на котором Форд-Фулкерсон может не расторгнуть.

Это было доказано в статье

Тошихико Такахаши:
«Самая простая и самая маленькая сеть, в которой процедура максимального потока Форда-Фулкерсона может не завершиться»
Журнал обработки информации 24, стр. 390-394, 2016.
Ссылка: https: //www.jstage.jst.go. JP / статьи / ipsjjip / 24/2 / 24_390 / _article

Гамов
источник
-1

Спасибо за вопрос, который я нашел не совсем естественным, но тем не менее довольно забавным.

Я изучил часть Форда-Феркулсона и думаю, что нашел график, который является контрпримером и имеет только одно ребро с иррациональной способностью α (график может работать для любого α).

Вот PDF, подытоживающий мою попытку: https://louis.jachiet.com/tmp/jQwbrkSMLNU_draft.pdf (извините, на данный момент это немного лаконично, но не стесняйтесь задавать вопросы)

Очевидно, что Ford-Felkurson позволяет нам выбирать путь расширения по своему желанию ... Я не уверен, что это было бы возможно для Эдмонда-Карпа.

Луис
источник