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

При помощи теоремы о максимальном потоке и минимальном разрезе (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) для двудольных паросочетаний используется приведение к графу с единичными пропускными способностями ребер, поэтому для доказательства можно воспользоваться теоремой Менгера вместо общей теоремы о максимальном потоке и минимальном разрезе.

Иначе говоря, теорема Холла является частным случаем теоремы Менгера, которая в свою очередь является частным случаем теоремы о максимальном потоке и минимальном разрезе.

Этот порядок соответствует историческим событиям, потому что теоремы доказывались именно в таком порядке с интервалом в несколько десятилетий.