Непересекающиеся пути в направленных и ненаправленных графах - Нахождение потока в сети

В разделе 7.1 мы описывали поток f как своего рода сетевой “трафик”. Однако наше определение потока выглядит статично: с каждым ребром е просто связывается число f(e), которое определяет величину потока, проходящего через е. Посмотрим, нельзя ли перейти к более динамичной концепции, ориентированной на сетевой трафик, и формализовать концепцию “перемещения” потока из источника к стоку. Это динамическое представление потока приводит нас к задаче о непересекающихся путях.

Задача

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

Множество путей является непересекающимся по ребрам, если их множества ребер не пересекаются, то есть никакие два пути не содержат ни одного общего ребра, даже если они проходят через некоторые общие узлы. Для заданного направленного графа G = (V, E) с двумя выделенными узлами s, t ∈ V задача непересекающихся по направленным ребрам путей заключается в нахождении максимального количества путей s-t, непересекающихся по направленным ребрам. Задача непересекающихся по ненаправленным ребрам путей заключается в нахождении максимального количества путей s-t в ненаправленном графе G. Родственный вопрос нахождения путей, непересекающихся не только ребрам, но и по узлам (разумеется, кроме узлов s и t), будет рассматриваться в упражнениях этой главы.

Разработка алгоритма

Как направленная, так и ненаправленная версия задачи исключительно естественно решаются с использованием потоков. Начнем с направленной задачи. Для графа G = (V, E) с двумя выделенными узлами s и t мы определим потоковую сеть, в которой s и t — источник и сток соответственно, а каждое ребро имеет пропускную способность 1. Предположим, существуют к путей s-t, непересекающихся по ребрам. Мы можем сделать так, чтобы по каждому из таких путей передавалась одна единица потока: в каждом пути одному ребру e назначается f(e) = 1, а всем остальным ребрам — f(e') = 0; так определяется допустимый поток с величиной k.

(7.41) Если в направленном графе G от s к t существуют к путей, непересекающихся по ребрам, то величина максимального потока s-t в G не меньше k.

Предположим, мы также сможем продемонстрировать утверждение, обратное (7.41): если существует поток с величиной k, то существуют к путей s-t, непересекающихся по ребрам. Тогда мы просто сможем вычислить максимальный поток s-t в G, и объявить (обоснованно) это значение максимальным количеством непересекающихся по ребрам путей s-t.

Начнем с доказательства этого обратного утверждения, которое позволит убедиться в том, что метод с потоком действительно дает правильный ответ. В ходе анализа также будет получен способ извлечения k путей, непересекающихся по ребрам, из целочисленного потока, передающего k единиц из s в t. Следовательно, вычисление максимального потока в G даст не только максимальное количество путей, непересекающихся по ребрам, но и сами пути.

Анализ алгоритма

Доказательство (7.41) в обратном направлении лежит в основе анализа, так как оно немедленно устанавливает оптимальность алгоритма на базе потока для нахождения непересекающихся путей.

Чтобы доказать это, рассмотрим поток с величиной не менее k и построим к путей, непересекающихся по ребрам. Согласно (7.14) мы знаем, что существует максимальный поток f с целыми величинами потоков. Так как пропускная способность всех ребер ограничивается 1, а поток является целочисленным, каждое ребро, передающее поток в f, имеет ровно одну единицу потока. Следовательно, необходимо доказать следующее.

(7.42) Если f — поток с величиной v, состоящий из 0 и 1, то множество ребер с величиной потока f(e) = 1 содержит множество из v путей, непересекающихся по ребрам.

Доказательство. Воспользуемся индукцией по количеству ребер в f передающих поток. Если v = 0, доказывать нечего. В противном случае должно существовать ребро (s, u), передающее одну единицу потока. Проверим путь из ребер, которые должны передавать поток: так как (s, u) передает единицу потока, из ограничения сохранения потока следует, что должно существовать ребро (v, w), по которому передается единица потока; и т. д. Если продолжать перебор, со временем произойдет одно из двух: либо мы достигнем t, либо узел v будет достигнут во второй раз.

В первом случае мы нашли путь из s в t, и этот путь будет использоваться как один из наших путей v. Обозначим f' поток, полученный уменьшением величины потока на ребрах из P до 0. Новый поток f' имеет величину v - 1, и в нем меньше ребер, передающих поток. Применяя индукционную гипотезу для f', мы получаем v - 1 путей, непересекающихся по ребрам, которые вместе с путем P образуют заявленные v путей.

Если P достигает узла v во второй раз, значит, ситуация выглядит примерно так, как показано на рис. 7.12. (Все ребра на схеме передают одну единицу потока, а пунктирные ребра обозначают текущий пройденный путь, который только что достиг узла v во второй раз.) В этом случае можно действовать иначе.

Рис. 7.12. Все ребра на схеме передают одну единицу потока. Путь P из пунктирных ребер — один из возможных путей в доказательстве (7.42)

Рассмотрим цикл C из ребер, посещенных между первым и вторым посещением v. Новый поток f' получается из f уменьшением величин потока на ребрах от C до 0. Новый поток f' имеет величину v, но меньшее количество ребер, передающих поток. Применяя индукционную гипотезу к f', мы получаем v путей, непересекающихся по ребрам, как и требовалось. ■

Объединение (7.41) и (7.42) дает следующий результат.

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

Также обратите внимание на то, как доказательство (7.42) предоставляет процедуру построения k путей для заданного целочисленного максимального потока в графе G. Эта процедура иногда называется декомпозицией потока, потому что она “раскладывает” поток на множество путей. Соответственно мы показали, что наш алгоритм на базе потока находит максимальное количество путей s-t, непересекающихся по ребрам, а также предоставляет механизм построения самих путей.

Граница времени выполнения

Для этой задачи так как существуют не более |V| ребер из s, каждое из которых имеет пропускную способность 1. Следовательно, применяя границу O(mC) из (7.5), мы получаем целочисленный максимальный поток за время O(mn).

Процедуру декомпозиции из доказательства (7.42), позволяющую получить сами потоки, также можно привести к выполнению за время O(mn). Для этого заметьте, что эта процедура при некоторых усилиях может построить один путь из s в t с максимум постоянной работой на ребро в графе — а следовательно, за время O(m). Всего существуют максимум n - 1 путей из s в t, непересекающихся по ребрам (все они должны использовать разные ребра, выходящие из s), а следовательно, на построение всех путей потребуется время O(mn).

Итак, мы показали следующее:

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

Версия теоремы о максимальном потоке и минимальном разрезе для непересекающихся путей

При помощи теоремы о максимальном потоке и минимальном разрезе (7.13) можно получить оценку максимального количества путей s-t, непересекающихся по ребрам. Говорят, что множество ребер F ⊆ E отделяет s от t, если после удаления ребер F из графа G в графе не остается ни одного пути s-t.

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

Доказательство. Если удаление множества F ⊆ E отделяет s от t, то каждый путь s-t должен использовать по крайней мере одно ребро из F, а следовательно, количество путей s-t, непересекающихся по ребрам, не превышает |F|.

Чтобы доказать другое направление, мы воспользуемся теоремой о максимальном потоке и минимальном разрезе (7.13). Согласно (7.43) максимальное количество путей, непересекающихся по ребрам, равно величине v максимального потока s-t. Из (7.13) следует, что существует разрез s-t (A, B) с пропускной способностью v. Обозначим F множество ребер, переходящих из A в B. Каждое ребро обладает пропускной способностью 1, так что |F| = v, и по определению разреза s-t удаление этих v ребер из G приводит к отделению s от t. ■

Итак, этот результат может рассматриваться как естественный частный случай теоремы о максимальном потоке и минимальном разрезе, в котором пропускные способности всех ребер равны 1. Собственно, этот частный случай был доказан Менгером в 1927 году задолго до того, как полная теорема о максимальном потоке и минимальном разрезе была сформулирована и доказана; по этой причине (7.45) часто называется теоремой Менгера. Кстати говоря, в доказательстве теоремы Холла (7.40) для двудольных паросочетаний используется приведение к графу с единичными пропускными способностями ребер, поэтому для доказательства можно воспользоваться теоремой Менгера вместо общей теоремы о максимальном потоке и минимальном разрезе. Иначе говоря, теорема Холла является частным случаем теоремы Менгера, которая в свою очередь является частным случаем теоремы о максимальном потоке и минимальном разрезе. Этот порядок соответствует историческим событиям, потому что теоремы доказывались именно в таком порядке с интервалом в несколько десятилетий².

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

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

(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. Обозначим s меньшее из этих значений и изменим f, сократив величину потока в e и e' на s. Полученный поток f является допустимым; обладает такой же величиной, как f; а его величина на одном из ребер e и e' равна 0.

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

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

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

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