Потоки в сетях

Пусть – произвольная ориентированная сеть, каждому ребру которой приписано неотрицательное число – пропускная способность ребра. Функция , заданная на множестве всех ребер и принимающая неотрицательные значениями, называется потоком в сети , если:

· для любой дуги величина , называемая потоком по дуге , не превосходит пропускной способности дуги;

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

Поскольку сумма значений по всем внутренним вершинам сети равна нулю, то .

Сечением сети называется множество ребер, при удалении которого сеть становится несвязной, причем полюсы попадают в разные компоненты связности. Ясно, что каждая цепь (а тем более каждый путь из в ) проходит хотя бы через одно ребро сечения. В сети на рис. 3.22 примерами сечений являются , , . Сечение будем называть простым, если при удалении любого его ребра, оно перестает быть сечением. Так , являются простыми сечениями, в то время как таковым не является.

Если в связной цепи удаляется простое сечение, то сеть распадается ровно на две части: левую часть, содержащую , и правую часть, содержащую . Каждое ребро простого сечения связывает вершины из разных частей. Будем называть ребро прямым, если в сети оно ориентировано слева направо, и обратным – в противном случае. Будет ли ориентированное ребро прямым или обратным, вообще говоря, зависит от выбора сечения. Так, в нашем примере (рис. 3.22) ребро е в сечениях и – обратное, а в сечении – прямое.

Каждому простому сечению припишем пропускную способность , равную сумме пропускных способностей всех его прямых ребер. В примере на рис. 3.22 сечение имеет пропускную способность 5+1=6, а сечение – 3+2+3+2=10. Если сеть несвязна и ее полюсы находятся в разных компонентах связности, то естественно считать единственным простым сечением сети пустое множество, а его пропускную способность нулевой.