Определение пропускной способности сетей связи

5.3.1. Постановка задачи определения максимального потока в сети связи

Пусть проектируется сеть связи. При проектировании задано множество источников информации S и множество получателей информации Т. Обычно эти множества пересекающиеся или могут быть тождественными S = Т, то есть узел источник может быть и узлом получателем. Каждый узел множества S порождает поток информации, которая должна быть передана узлам множества Т. Ветви графа могут иметь заданную пропускную способность с (u,v), между каждой парой узлов u и v, либо может потребоваться определить пропускную способность каждой ветви. Пропускная способность ветви (ребра) может рассматриваться как максимальная скорость передачи информации вдоль данной ветви.

Задана, топология сети, то есть установлено соответствие узлов и ветвей, задана матрица весов ветвей A [ u,v ], где в качестве весов выступает пропускная способность каждой ветви.

Какие задачи уже можно решить при этих исходных данных? Очевидно, можно выделить множество связанных узлов. Можно найти кратчайшие пути между всеми парами вершин. Можно найти, наконец, все пути между вершинами s и t. При этом каждый путь должен отличаться от другого, хотя бы одной ветвью или узлом. Однако, решение ни одной ив этих задач не позволит нам получить ответ на вопрос - какое максимальное количество информации в единицу времени можно передать от узла s к узлу t, либо от группы узлов множества S к группе узлов множества. Т. Решенные вышеизложенные задачи не помогут также решить и обратную задачу - сколько и с какими пропускными способностями требуется ветвей, чтобы пропустить все информационные потоки между множеством узлов S и множеством узлов Т. Такая задача, кстати для реальных сетей и не решена (не позволяет размерность задачи и неопределенность исходных данных).

Для постановки задачи формализуем некоторые понятия. Припишем каждой ветви (u,v) некоторый вес f (u,v), называемый потоком от u к v. Значение потока в ветви (u,v) можно рассматривать как скорость, с которой передается информация в данной ветви.

Тогда величина, называемая дивергенцией потока f в вершине v

div f (v) = Δ f (v) = ∑ f (v, u) - ∑ f (u, v),

где ∑ f (v,u) - поток, выходящий из вершины v, ∑ f (u,v) - поток, входящий в вершину v, определяет количество потока, выходящего из вершины u.

Эта величина может быть отрицательной (когда в v больше входит, чём выходит), положительной (когда из v больше выходит, чем входит) и равной 0. Последний случай будет интересовать нас более всего. Это значит, что поток не накапливается и не возникает ни в одной из вершин, кроме s и t.

Под потоком из s в t будем понимать функцию, для которой выполняются условия

0 ≤ f (u, v) ≤ c (u, v)

(5.1)

для каждой ветви (u,v) W. Кроме того

div f (v) = Δ f (v) = 0

(5.2)

для каждой вершины v, причем v ≠ s, v ≠ t (кроме источника s и стока t).

Для вершины s величина

div f (s) = Δ f (s) = f (s, V) – f (V, s)

положительна и называется исходящим потоком.

Для вершины t величина

div f (t) = Δ f (t) = f (t, V) – f (V, t)

отрицательна и называется входящим потеком.

Таким образом, можно записать

div f (i) = Δ f (i) = f (s, V) - f (V, i) =

(5.3)

Выражение (5.3) отражает факт сохранения потока для всех вершин кроме s и t.

М = div f (s) = - div f (t) - мощность потока. Если М = 0, то поток называется циркуляцией.

Такой поток может описывать поток электрической мощности, поток воды в водопроводной сети или информационные потоки в сетях связи. Задача состоит в том, чтобы найти поток f максимальной мощности, удовлетворяющий приведенным выше условиям (1, 2).

Возьмем произвольный ориентированный граф с выделенными вершинами s и t.

Рис. 5.20

Отметим, что неориентированный граф всегда можно заменить ориентированным следующим образом

 

 

 

Рис. 5.21

Рассечем ветви (1,2), (3,4) и (5,6), разделив тем самым множество вершин V на два подмножества (s, v ₁, v ₃, v ₅) и (v ₂, v ₄, v ₆, t).

Какой поток, может быть передан от s к t через эти ветви? Очевидно, учитывая, что ветви ориентированные

max f (s,t) = ∑ c (i,j)

i = 1, 3, 5 j = 2, 4, 6

то есть он будет равен сумме пропускных способностей ветвей, входящих в разрез.

Под разрезом сети R (A) соответствующим А V (А подмножество V), А ≠ V, А ≠0, будем понимать множество дуг, (u,v) таких что (u,v) W, u А и v V \ А.

Для произвольного потока f в сети поток через разрез определится очевидным образом

тогда, если представить, что s A, a t V \ A. то поток из s в t определится как

Введем понятие минимального разреза. Под минимальным разре­зом, разделяющим s и t, мы будем понимать произвольный разрез R (A), s А и t V \ A с минимальной пропускной способностью.

Пример. Сформулируем классическую теорему теории потоков в сетях. Эта теорема о максимальном потоке и минимальном разрезе:

Величина каждого потока из s в t, не превосходит пропускной способности минимального разреза, причем существует поток, достигающий этого значения.

Максимальный поток в сети

Все известные алгоритмы построения максимального потока основываются на последовательном увеличении потока, причем модификация потока, увеличивающая его величину, чаще всего опирается на метод увеличивающих цепей (или путей наращивания).

Введем ряд понятий, которые понадобятся нам при дальнейшем изложении материала.

Будем говорить, что дуга m сети G является допустимой дугой из u в v относительно потока f, если

m = < u,v > удовлетворяет условию f (m) < c (m),

(5.4)

т.е. величина потока f (m), проходящего через дугу меньше пропускной способности этой дуги или

m = < v,u > удовлетворяет условию f (m) > 0,

(5.5)

пропускная способность этой дуги имеет положительное значение. Причем условие (5.4) применяется для прямых дуг (направление которых совпадает с общим направлением сети от s к t), а условие (5.5) - для обратных дуг (направление которых противоположно, общему направлению сети).

Увеличивающей цепью (путем наращивания) для данного потока f из s в t называется произвольная знакопеременная последовательность (попарно различных) вершин и дуг

v 0, m 1, v 1, m 2, v 3, …, vl -1, ml, vl

(5.6)

такая, что v _o = s, v_l = t, и для каждого i ≤ l дуга m_i допустима из v_{i -1} в v_i относительно потока f. Другими словами увеличивающая цепь должна обеспечивать путь из s в t и содержать только допустимые дуги. Увеличивающих цепей в сети может быть несколько или же не одной.

Введем такое понятие, как остаточная емкость пути наращивания. Остаточная емкость r (π _{s , t}) пути наращивания в ориентированном графе определяется как

r (π s, t) = min [ min [ f (i, j)], min [ c (i, j)- f (i, j)]], по обратным дугам по прямым дугам (i, j) π s , t (i, j) π s , t

(5.7)

где π _s, _t – увеличивающая цепь в сети.

Возьмем фрагмент графа, содержащего путь наращивания от s до t.

 

Рис. 5.22

Вверху указаны пропускные способности, внизу потоки. Найдем остаточную емкость пути наращивания

r (π _{s , t}) = min (min [3], [2]; min [3-l] [4-l]) = 2.

Приведем теперь алгоритм наращивания потока в сети.

Шаг 1. Проанализировать граф сети и выделить в нем допустимые прямые и обратные дуги.

Шаг 2. Составить из допустимых дуг пути наращивания (s - t) с остаточной емкостью r (π _{s , t}) > О.

Шаг 3. Определить величину остаточной емкости пути r(π _{s , t}).

Шаг 4. Увеличить поток в пути наращивания на r(π _{s , t}). Для этого в прямых ветвях потоки необходимо увеличить на r (π_{s, t}), в обратных ветвях - уменьшить на r (π _{s , t}).

Шаг 5. Повторять шаги 2 и 4 до тех пор, пока не останется ни одного пути наращивания, то есть r (π _{s , t}) всех путей станет равным 0.

Запишем теперь три эквивалентных условия для окончания работы -алгоритма.

1. Поток ив s в t максимален.

2. Не существует ни одного пути наращивания из s в t.

3. Существует такое множество А, что

f (s, t) = c (A, V \ A) =

(5.8)

т.е. величина потока f равна пропускной способности в сети.

Рассмотрим пример:

Сеть связи задана графом G рис.5.3. Возле дуг цифры без скобок обозначают величину потока f в дуге, в скобках - пропускную способность с дуги.

Необходимо определить:

1. Пропускную способность сети c (A) (максимальный поток в минимальном разрезе).

2. Увеличить поток в сети.

Рис. 5.23.

Решение.

1. Определим вначале минимальный разрез сети. Очевидно, что минимальные разрезы в данной сети находятся возле ее вершин s и t. Это дуги <1,2>; <1,3> и <6,8>; <7,8>. Максимальный поток через разрез будет равен сумме потоков этих дуг

c (А) = f <1,2> + f <1,3> = 4+6 = 10 или c (А) = f <6,8> + <7,8> = 10+0 = 10

(5.9)

2. Увеличение потока в сети проведем в соответствии с алгоритмом наращивания потока.

Шаг 1. Выделим в графе допустимые дуги:

прямые <1,3>; <2,3>; <4,5>; <5,6>; <7,8>;

обратные <5,2>; <7,6>.

Шаг 2. Составим путь наращивания. Это путь 1 - 3 - 2 - 5 - 6 - 7 - 8. Заметим, что в пути прямая дуга <4,5> перешла в обратную. Дуга <4,5> не входит в путь наращивания.

Шаг 3. Величина остаточной емкости пути будет равна

r (π _s, _t) = min (min [4], [6], [4]; min [9-6], [l-0], [2-0]) = 1.

Шаг 4. Увеличим поток в пути наращивания. Для этого в прямых дугах увеличим поток на величину r (π _{s , t}) = 1, а в обратных – уменьшим на эту же величину.

f <1,3> = 6+1 = 7; f <5,6> = 0+1 = 1; f <7,8> = 0+1 = 1;

f <2,3> = 4-1 = 3; f <5,2> = 6-1 = 5; f <7,6> = 4-1 = 3.

Шаг 5. Проанализировав еще раз граф можем сделать вывод, что путей наращивания больше нет. Следовательно, задача решена. Сеть с максимальным потоком будет иметь вид рис 5.24.

Нетрудно убедиться, что поток теперь максимален (нет ни одного пути наращивания).

 

Рис. 5.24.

Величина максимального потока будет равна

с (А) = f <1,2> + f <1,3> = 4 +7 = 11;

или с (А) = f <6,8> + f <7,8> = 10 +1 = 11