Дипломная работа: Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей

Пусть xX. Обозначим E+(x) – множество дуг графа, входящих в х, E-(x) – выходящих из х.

Множества начальных вершин дуг из Е+(х) и множество конечных вершин дуг из Е-(х) обозначим соответственно S+(x) и S-(x).

E+(x) E-(x)

y x y

S+(x) S-(x)

Рис. 3. Окрестность вершины графа.

Граф Г называют транспортной сетью , если каждой дуге u соответствует целое число c(u)>=0 и найдутся x0 и z из Х такие, что Е+(х0)=

Е-(z)= . Вершина х0 называется истоком , z-стоком , c(u) – пропускной способностью дуги .Потоком в транспортной сети называют целочисленную функцию ф(u), удовлетворяющую следующим условиям :

1) 0<=ф(u)<=с(u)

2) ф(u) - ф(u) = 0 для любой вершины x=/=x0, x=/=z.

uЕ+(х) uЕ-(х)

При этом поток не может «накапливаться» ни в одной вершине транспортной сети, кроме истока х0 и стока z, поэтому

ф(u) = ф(u) = Ф.

uЕ+(х) uЕ-(х)

Величину Ф называют потоком транспортной сети. Дуга u называется насыщенной , если ф(u)=c(u). Поток Ф называется полным , если каждый путь из х0 в z содержит хотя бы одну насыщенную дугу.

Рассмотрим разбиение R множества вершин сети Х = Х1UX2,

X1X2X1X2=, x0X1, zX2, называемое разрезом сети.

Сумма пропускных способностей множества {(xi,xj), xi из X1, Xj из Х2} определяет пропускную способность разреза R : r(R) = c(u),

u{(xi,xj):xi X1, xjX2}

Поскольку для любой дуги u выполняется неравенство ф(u)<=c(u), то Ф<=r(R).

Теорема Форда-Фалкерсона : максимальный поток в сети равен минимальной величине разрезов в этой сети.

Алгоритм нахождения максимального потока, предложенный Фордом и Фалкерсоном, состоит в постепенном увеличении допустимого потока Ф до максимальной величины Ф*. Начальное значение потоков полагается равным нулю. Процесс увеличения потока состоит в поиске путей, на которых возможно увеличение потока, с соответствующей разметкой вершин сети.

Алгоритм Форда-Фалкерсона

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

I. Увеличение потока.

1. Присвоить истоку х0 пометку (+х0, d(x0) = ). Это означает, что вход в исток не ограничен; величина d всегда показывает, на сколько может быть увеличен поток, входящий в помеченную вершину. Здесь символ обозначает достаточно большое число – начальное значение пометки.

2. Взять некоторую вершину xi с пометкой, которая в общем случае имеет вид (+ или – xk, d(xi)), где xk – обозначение вершины, d(xi) – некоторое число. Каждой непомеченной вершине xj из S-(xi), для которой ф(xi,xj)<с(xi,xj), присвоить пометку (+xi, min[d(xi),c(xi,xj)-ф(xi,xj)]). Это означает, что поток в дуге (xi,xj) может быть увеличен (знак плюс) на величину, определяемую минимумом. Каждой непомеченной вершине xj из S+(xi), такой, что ф(xj,xi)>0 присвоить пометку (-xi, min[d(xi), ф(xj,xi)]), что означает возможность уменьшения потока на величину, определяемую минимумом.

3. Если сток не помечен и можно пометить какую-либо вершину, кроме стока, то перейти к п.2.

4. Если оказался помеченным сток z, и в его пометку входит число d(z), то между вершинами x0 и z найдется цепь, все вершины которой помечены номерами предыдущих вершин. Для каждой помеченной вершины х в этой цепи изменить величину потока : ф'(y,x)=ф(y,x)+d(z), если х имеет пометку (+y,d(x)) или ф'(y,x)=ф(y,x)-d(z), если х имеет пометку (-y,d(x)). Пометка вершины х стирается, назначенные потоки запоминаются. При достижении (в процессе стирания пометок вершин цепи) истока х0 перейти к п.1; если же ни одну вершину пометить не удается и сток z не помечен, то перейти к построению разреза.