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

2.1. Понятие сети

Сетью будем называть ориентированный связный граф без петель и параллельных рёбер. Потоки в неориентированных графах можно изобразить в виде потоков в соответствующих ориентированных. Поток в петле не влияет на распределение потока между вершинами. Рассмотрим сеть G = (V, E), | V | = n, | E | = m. Пускай каждой дуге е_j E поставлено в соответствие неотрицательное действительное число с_j , которое назовём пропускнойспособностьюдуги е_j. Обозначим через v_i → V множество дуг, выходящих из вершины v_i, через V → v_i – множество дуг, заходящих в вершину v_i.

Потоком в сети G из вершины v_s в вершину v_t величины w называется неотрицательная, определенная на дугах е_j, функция φ: Е → R₊ {0}, такая, что

– = (1)

φ (е_j) ≤ c_j, j = 1, …, m.

Вершина v_s называется источником, вершина v_t – стоком, а остальные вершины – промежуточными узлами. Число Q(v_i) = - называется чистым потоком из вершины v_i относительно φ. Число φ(е) называется потоком по дуге е. Если “реальный” поток по дуге отрицательный, то его можно сделать положительным, выбрав соответствующую ориентацию дуги e. Систему уравнений (1) можно переписать в векторном виде:

ВФ = l, (2)

где В – матрица инцидентной размерности n m, Ф = (φ (e₁) … φ (e_m)) ^T, l = (0..0 w 0..0 – w 0..0) ^T. Поскольку ранг матрицы инциденций равен n – 1, то система уравнений (1) избыточна: . Также можно сказать, что поток φ из v_s в v_t величины w есть поток величины - w из v_t в v_s.

Пример:

Рис. 2.1.1. Поток величины 3

Сеть, изображённая на рис. 2.1.1, состоит из пяти узлов и восьми дуг. Будем рассматривать поток от v₁ до v₅. Каждой дуге приписаны два числа: первое – величина потока по дуге, второе – пропускная способность дуги. Величина этого потока равна 3. Действительно,

Q (v₁) = 5 - 2 = 3,

Q (v₂) = 7 – (5 + 2) = 0,

Q (v₃) = –4 – 0 +2 + 2 = 0, (3)

Q (v₄) = –4 + 4 = 0,

Q (v₅) = 4 + 0 – 7 = –3.

Систему уравнений (3) можно записать в векторном виде ВФ = l (2):

, , .

---

Дата добавления: 2015-08-09