ОПРЕДЕЛЕНИЕ. Потоком в транспортной сети N = (G, c) называется всякая функция y: U ® R+, для которой выполнены условия:
Потоком в транспортной сети N = (G, c) называется всякая функция y: U ® R+, для которой выполнены условия:
1) " u Î U (0 £ y (u) £ c (u));
2) " v Î V  .
Здесь  (v) - множество ребер, выходящих из вершины v, а  (v) - множество ребер, ведущих в эту вершину.
Значение y(u) для произвольного ребра u называется величиной потока, проходящего по этому ребру.
Тогда условие 1 приведенного определения означает, что величина потока по любому ребру транспортной сети не превосходит пропускной способности этого ребра.
Второе из приведенных условий означает, что суммарный поток, приходящий в произвольную внутреннюю вершину сети, равен суммарному потоку, выходящему из этой вершины.
Величиной потока y в транспортной сети N называется суммарный поток, выходящий из истока I. Величина потока y в транспортной сети N обозначается как y(N).
Условие 2 в определении потока для транспортной сети гарантирует, что значение y(N) равно суммарной величине потока, поступающего на сток сети. Доказательство этого факта содержится в следующей теореме.
Дата добавления: 2015-09-27 | Просмотры: 345 | Нарушение авторских прав
|
