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

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

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

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

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

  1. 6. Таблица минимальных и максимальных размеров и сроков наказаний по Уголовному кодексу РФ 1996 г.
  2. Установите минимальный срок для начала работы
  3. коян: Восходящий узел - включение в общий поток; Нисходящий узел - исключение из общего потока.
  4. Критерий для подбора индивидуальных приемов — критерий мастерства, критерий оптимальности, критерий минимального усилия, критерий автоматизма.
  5. НЕПЕРЕСЕКАЮЩЕЕСЯ СОСУЩЕСТВОВАНИЕ С ГОСУДАРСТВОМ
  6. 12. ВЕРСИЯ
  7. Наличие максимально полной информации о допрашиваемом
  8. 11.1. Криминалистическая версия. Понятие, виды
  9. Продвинутая версия
  10. ВЕРСИЯ
  11. ДИСФУНКЦИЯ МОЗГОВАЯ МИНИМАЛЬНАЯ
  12. МЕТОД ИЗМЕНЕНИЙ МИНИМАЛЬНЫХ