ТГ

[resolventa]

Народ!!... Помогите... СРОЧНО нужно понять, что есть такое *аугментальный путь*!!!!!!! Это из Теории графов. Напишите, что знаете по этому поводу?!???!!! Поисковики не дают ничего путного, кроме ссылки на сайт Суетовой с условием моей же задачи...

Comments

[fedor_tsarev]

Это тоже самое, что и "дополняющий путь". :)

[resolventa]

Вот-вот. Написала письмо Суетовой, она ответила: "Дополняющий - то же, что аугментальный." Ты: "Аугментальный - то же, что дополняющий..." =) Вот так и живём. А Эдмондс-Карп ни при чём, я методом Форда-Фалкерсона работаю... ;)

[fedor_tsarev]

Да уж... Ты Кормена читала. Там написано, что алгоритм Эдмондса-Карпа --- это реализация метода Форда-Фалкерсона. От некоторых других реализаций он отличается тем, что работает за полиномиальное время.

Почитай вот здесь.

В этом документе, правда, они называются "увеличивающие цепи". Но, ты же понимаешь, это вопрос терминологии :)

[fedor_tsarev]

Алгоритм Эдмондса-Карпа на каждом шаге ищет путь из истока в сток в остаточной сети. Потом "проталкивает" по нему поток. Этот путь как раз и называется аугментальным, или дополняющим (по-английски, augmenting path).

[resolventa]

Не нравится мне что-то Кормен... Много всего лишнего. Доказательства каких-то теорем, которые не имеют прямого отношения к реализации алгоритма. По-моему, в этом плане "Новиков" удобней... =/