Поток в транспортной сети. Разрез, пропускная способность разреза

Определение. Величиной потока j в транспортной сети D называется величина j, равная сумме потоков по всем дугам, заходящим в , или, что то же самое, величина, равная сумме потоков по всем дугам, исходящим из V1, т.е.:

Определение. Дуга x О X называется насыщенной, если поток по ней равен ее пропускной способности, т.е. если j(x)= c(x).Поток j называется полным, если любой путь в D из V1 в Vn содержит, по крайней мере, одну насыщенную дугу.

Определение. Поток j называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети D.

Очевидно, что максимальный поток j обязательно является полным. Обратное неверно. Существуют полные потоки, не являющиеся максимальными. Тем не менее, полный поток можно рассматривать как некоторое приближение к максимальному потоку.

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

Разрезом сети называется множество, которому принадлежит исток, и не принадлежит сток. Т.е. разрез - это минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.

Пропускной способностью разреза называется число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.

Отыскание минимального разреза - одна из основных задач анализа транспортных сетей.

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