Определение потоковой сети

Потоковая сеть представляет собой ориентированный граф, удовлетворяющий некоторым специальным условиям и обладающий некоторыми дополнительными (по отношению к произ-вольным графам) параметрами. Необходимые понятия и определения теории графов даны в предыдущей главе 6; будем пользоваться введёнными там понятиями без дополнительных разъ-яснений, останавливаясь лишь на новых (ранее не определённых) понятиях и терминах.

При определении сети в базовом простейшем случае рассматривают ориентированные связные графы, обладающие следующими специальными свойствами:

1) существует ровно одна вершина, в которую не входит ни одна дуга (эта вершина называется источником);

2) существует ровно одна вершина, из которой не выходит ни одна дуга (эта вершина называет-ся стоком);

3) ни одна дуга не является петлёй.

Потоковой сетью) называется граф указанного типа, у которого каждой дуге v_j (j = 1, 2,..., m) сопоставлено положительное число с_j (j = 1, 2,..., m), называемое пропускной способнос-тью дуги v_j. Пример потоковой сети приведен на рис.1. Пропускные способности проставлены в кружках около дуг.

Рис.1

Таким образом, потоковая сеть - это ориентированный граф, в котором заданы пропуск-

ные способности дуг. В дальнейшем будем удобно занумеровать вершины графа так, чтобы вершина с минимальным номером (x ₁) являлась источником, а вершина с максимальным номе-ром (x_n) являлась стоком сети. Потоковую сеть будем обозначать через S.

Введем обозначения:

- множество номеров всех дуг, входящих в вершину x_i;

- множество номеров всех дуг, выходящих из вершины x_i.

Пример 1. В сети, показанной на рис.1:

n = 7, m = 12,

= {1,2},

= {1,3}, = {4,5}, = {2,6}, = {3,7}, = {5}, = {6,8,9,11},

= {4,8}, = {10}, = {7,9}, = {12},

= {10,11,12},

= = Æ (по определению сети, так как у источника нет входящих, а у стока - выходящих дуг);

с ₁=3, с ₂=1, с ₃=2, с ₄=1, с ₅=4, с ₆=3, с ₇=2, с ₈=5, с ₉=1, с ₁₀=6, с ₁₁=1, с ₁₂=3 ■

Потоком в сети называется вектор u = (u ₁, u ₂,..., u_m)

удовлетворяющий условиям

0 ≤ u_j ≤ с_j (j = 1, 2,..., m), (1)

(i = 2, 3,..., n -1). (2)

Компонента u_j вектора u = (u ₁, u ₂,..., u_m) называется потоком по дуге v_j (j = 1, 2,..., m). Таким образом, условие (1) означает, что поток по любой дуге - неотрицательное число, не превос-ходящее пропускной способности этой дуги. Условие (2) означает, что сумма потоков по всем дугам, входящих в вершину, равна сумме потоков по всем дугам, выходящих из этой же верши-ны (кроме источника и стока).

Содержательно поток описывает распределение по дугам сети некоторого продукта, до-ставляемого из источника в сток. При этом поток u_j по дуге v_j - это количество продукта, пере-даваемого по данной дуге от её начала к её концу. Условие (1) выражает ограничение на поток по каждой дуге: нельзя передать больше, чем эта дуга может пропустить. Условие (2) выражает закон сохранения: сколько продукта поступило в промежуточную вершину, столько же оттуда отправлено далее.

Величиной Р (u) потока u называется сумма потоков во всех дугах, выходящих из источ-ника, т.е. общее количество передаваемого по сети продукта.

Пример 2. Для иллюстрации введённых понятий рассмотрим сеть, показанную на рис. 2.

Векторы

u ¹ = (2, 0, 1, 1, 1, 0, 0, 2, 0);

u ² = (0, 1, 0, 0, 0, 1, 1, 1, 0);

u ³ = (1, 0, 1, 0, 0, 1, 0, 0, 1);

u ⁴ = (2, 1, 1, 1, 1, 1, 0, 2, 1)

являются различными потоками в этой сети (проверьте это!). Легко видеть, что

Р (u ¹) = 2, Р (u ²) = 1, Р (u ³) = 2, Р (u ⁴) = 3

Интересно изобразить эти четыре потока графически, сопоставив каждой единице потока по дуге пунктирную линию вдоль этой же дуги. Такое представление дается на рис.3.

Рис.2 ■

Рис.3

Задание 1. Установить, является ли указанный вектор потоком в сети, изображённой на рис.2. В случае положительного ответа представить данный поток графически, как сделано в примере 2 (см. рис.3).

u ¹ = (0, 0, 0, 0, 0, 0, 0, 0, 0);

u ² = (1, 0, 1, 0, 1, 0, 0, 1, 0);

u ³ = (0, 1, 0, 0, 1, 0, 0, 1, 0);

u ⁴ = (0, 1, 0, 0, 0, 1, 0, 0, 1);

u ⁵ = (1, 1, 0, 1, 1, 0, 0, 2, 0);

u ⁶ = (1, 2, 0, 1, 1, 1, 0, 2, 1);

u ⁷ = (3, 0, 1, 2, 0, 1, 0, 2, 1);

u ⁸ = (0, 2, 0, 0, 2, 0, 0, 2, 0);

u ⁹ = (1, 2, 0, 1, 1, 1, 0, 2, 1);

u ¹⁰ = (1, 1, 1, 0, 2, 0, 0, 2, 0) ■