Расширения: непересекающиеся пути в ненаправленных графах
Наконец, рассмотрим задачу непересекающихся путей в ненаправленном графе G. Несмотря на тот факт, что граф G стал ненаправленным, для получения путей в G, непересекающихся по ребрам, можно воспользоваться алгоритмом максимального потока.
Идея проста: каждое ненаправленное ребро (u, v) заменяется двумя направленными ребрами (u, v) и (v, u); так создается направленная версия G’ графа G. (Ребра, входящие в s и выходящие из t, можно удалить, так как они бесполезны). Теперь к полученному направленному графу применяется алгоритм Форда–Факкерсона.
Тем не менее, нетрудно убедиться в том, что всегда существует максимальный поток в любой сети, использующей не более одного из каждой пары противоположно направленных ребер.
(7.46) В любой потоковой сети существует максимальный поток f, в котором для всех противоположно направленных ребер e = (u, v) и e’ = (v, u) либо f (e) = 0, либо f (e’) = 0. Если пропускные способности потоковой сети являются целочисленными, то также существует такой целочисленный максимальный поток.
Доказательство. Рассмотрим максимальный поток f и изменим его так, чтобы он удовлетворял заявленному условию. Пусть e = (u, v) и e’ = (v, u) — противоположно направленные ребра, f (e) ≠ 0 и f (e’) ≠ 0.
Обозначим δ меньшее из этих значений и изменим f, сократив величину потока в e и e’ на δ. Полученный поток f ‘ является допустимым; обладает такой же величиной, как f; а его величина на одном из ребер e и e’ равна 0.
Теперь мы воспользуемся алгоритмом Форда–Фалкерсона и процедурой декомпозиции пути из (7.42) для получения путей, непересекающихся по ребрам, в ненаправленном графе G.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу