Расширения: непересекающиеся пути в ненаправленных графах

Наконец, рассмотрим задачу непересекающихся путей в ненаправленном графе G. Несмотря на тот факт, что граф G стал ненаправленным, для получения путей в G, непересекающихся по ребрам, можно воспользоваться алгоритмом максимального потока.
Идея проста: каждое ненаправленное ребро (и, v) заменяется двумя на- правленными ребрами (и, v) и (v, и); так создается направленная версия G' графа G. (Ребра, входящие в 5 и выходящие из t, можно удалить, так как они бесполезны). Теперь к полученному направленному графу применяется алгоритм Форда-Фал- керсона. Тем не менее сначала необходимо разобраться с одним важным аспектом. Обратите внимание: два пути P1 и P2 могут быть непересекающимися по ребрам в направленном графе, но при этом использовать одно ребро в ненаправленном графе G: это происходит, когда P1 использует направленное ребро (и, v), а P2 ис- пользует ребро (v, и). Тем не менее, нетрудно убедиться в том, что всегда существует максимальный поток в любой сети, использующей не более одного из каждой пары противоположно направленных ребер.

(7.46) В любой потоковой сети существует максимальный поток f в котором для всех противоположно направленных ребер e = (и, v) и e' = (v, и) либо f(e) = 0, либо f (e') = 0. Если пропускные способности потоковой сети являются целочис- ленными, то также существует такой целочисленный максимальный поток.

Доказательство. Рассмотрим максимальный поток f и изменим его так, чтобы он удовлетворял заявленному условию. Пусть e = (и, v) и e' = (v, и) — противо- положно направленные ребра, f (e) ф 0 и f (e') ф 0. Обозначим δ меньшее из этих значений и изменимf сократив величину потока в e и e' на δ. Полученный поток f является допустимым; обладает такой же величиной, как f; а его величина на од- ном из ребер e и e' равна 0.

Теперь мы воспользуемся алгоритмом Форда-Фалкерсона и процедурой де- композиции пути из (7.42) для получения путей, непересекающихся по ребрам, в ненаправленном графе G.

(7.47) В ненаправленном графе G существуют к путей из 5 в t, непересекающих- ся по ребрам, в том и только в том случае, если максимальная величина потока s-t в направленной версии G' графа G равна по крайней мере к. Кроме того, алгоритм

Форда-Фалкерсона может использоваться для нахождения максимального мно- жества непересекающихся путей s-t в ненаправленном графе G за время O(mn).

Ненаправленная аналогия (7.45) тоже истинна, так как в любом разрезе s-t не более чем одно из двух противоположно направленных ребер может переходить со стороны s на сторону t разреза (потому что если одно ребро следует в нужном направлении, то другое должно проходить со стороны t на сторону s).

(7.48) В каждом ненаправленном графе с узлами s и t максимальное количество путей s-t, непересекающихся по ребрам, равно минимальному количеству ребер, удаление которых приводит к отделению s от t.

7.7.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Расширения: непересекающиеся пути в ненаправленных графах:

  1. 1.3.1. Ненаправленность
  2. НЕПЕРЕСЕКАЮЩЕЕСЯ СОСУЩЕСТВОВАНИЕ С ГОСУДАРСТВОМ
  3. 1.3.1 Ненаправленность.
  4. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  5. Расширение графического метода
  6. Самовоспитание как "расширение" сознания
  7. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  8. 3.12.2. Техника расширенного восприятия
  9. Расширение внутреннего кругозора
  10. 7.2.2. Расширение полноты ответа
  11. 7.2.2. Расширение полноты ответа
  12. Метод расширения сознания
  13. 2. Расширение круга наследников по закону в российском наследственном праве
  14. 2. Расширение сети вольной русской прессы в 1860-е годы
  15. Развивающие вопросы призваны способствовать расширению поля беседы в сторону уточнения деталей, эмоциональных переживаний героя, включая ее в более широкий контекст.
  16. Пути оттока
  17. Будьте верны своему пути