Определение. Потоком в транспортной сети 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-03-31