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

Потоковая сеть представляет собой ориентированный граф, удовлетворяющий некоторым специальным условиям и обладающий некоторыми дополнительными (по отношению к произ-вольным графам) параметрами. Необходимые понятия и определения теории графов даны в предыдущей главе 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) ■