Теорема о максимальном потоке и минимальном разрезе

В приложениях теории графов при анализе потоков в сетях с одним источником s и одним стоком r и ограниченной пропускной способностью основной задачей является поиск максимального потока в сети с постоянными пропускными способностями дуг и изменяемыми интенсивностями источника и стока (то есть потока максимальной величины, втекающего в сток, а не потока максимальной обобщенной стоимости в смысле выражения (2)). Алгоритм поиска максимального потока строится на базе того простейшего факта, что поток через разрез не может быть больше его пропускной способности, что, в свою очередь, приводит к теореме Форда и Фалкерсона (о максимальном потоке и минимальном разрезе):

в любой сети с одним источником и одним стоком величина максимального потока от источника к стоку равна величине минимального разреза.

Так, для сети (рис. 6) минимальный разрез C _min = {[1,2]; (1, 3)}; а его величина R_c = 3 + 2 = 5 равна величине максимально возможного потока из узла 1 в узел 4 (см. рис. 7).