27. Разрез, его пропускная способность
К списку вопросов
Разрезом сети N? с источником V и стоком W называется такое минимальное множество дуг, при удалении которых поток из V в W становится нулевым, причем этим свойством не обладает ни одно из подмножеств этого множества.
Разрезов, вообще говоря может быть несколько у данной сети.
Разрезы (а1; а2); (а1; а3 ; а5) (а2 ; а4)
Разрез обладает тем свойством, что любая простая орцепь из V в W проходит через дугу, принадлежащую разрезу. Пропускной способностью разреза называется сумма пропускных способностей принадлежащих ему дуг.
Разрезы, обладающие наименьшей возможной пропускной способностью, называются минимальными разрезами. Величина любого потока не превосходит пропускной способности любого разреза и в частности, величина любого максимального потока не превосходит пропускной способности минимального разреза.
К списку вопросов
