Введение

Концепция в теории оптимизации
В информатике и теории оптимизации теорема о максимальном потоке и минимальном разрезе утверждает, что в сети потоков максимальный объем потока от источника к стоку равен суммарному весу ребер в минимальном разрезе, то есть наименьшей сумме весов ребер, удаление которых отключит источник от стока. Это частный случай теоремы двойственности для линейного программирования и может быть использована для вывода теоремы Менгера и теоремы Кёнига — Эгервари.

Определения и формулировка

Теорема устанавливает равенство между двумя величинами: максимальным потоком в сети и минимальной пропускной способностью разреза сети. Чтобы сформулировать теорему, необходимо сначала определить каждое из этих понятий.

Основная теорема

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

Пример

На рисунке справа показана схема потока в сети. Числовая пометка на каждой дуге в формате f/c указывает поток (f) и пропускную способность (c) этой дуги. Потоки, выходящие из источника, в сумме составляют пять (2+3=5), как и потоки, входящие в сток (2+3=5), что подтверждает, что значение потока равно 5. Один s-t разрез со значением 5 задается множествами S={s,p} и T={o,q,r,t}. Пропускные способности дуг, пересекающих этот разрез, равны 3 и 2, что дает общую пропускную способность разреза 3+2=5. (Дуга от o к p не учитывается, поскольку она направлена из T обратно в S.)

Значение потока равно пропускной способности разреза, что показывает, что поток является максимальным, а разрез – минимальным. Обратите внимание, что поток по каждой из двух дуг, соединяющих S и T, достигает максимальной пропускной способности; это всегда верно: минимальный разрез представляет собой "узкое место" системы.

Теорема о максимальном потоке Седербаума

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

Теорема Менгера

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

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