Проектирование и разработка сетевых броузеров на основе теоретико-графовых моделей (стр. 2 из 14)

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

Идентификаторы : d[s,t] – массив длин ребер графа для каждой пары вершин s,t X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.

х – вершина-источник графа <X,U>.

n=|X| - число вершин графа.

u,w,k – рабочие переменные.

D[w] – массив, в котором к концу работы алгоритма будут содержаться кратчайшие длины путей из х в w для всех вершин w X.

Begin

D[x]:=0; // Длина пути из источника x.

For w X do D[w]:=d[x,w]; // Инициализация матрицы расстояний

For k:=1 to n-2 do // Повторять n-2 раз

For w {X&bsol;{x}} do // Цикл по всем вершинам, кроме источника.

For u X do D[w]:=min(D[w],D[u]+d[u,w]); // выбор минимума.

End.

Этот алгоритм также основан на соотношении (принципе оптимальности) Беллмана. Всякий раз, когда находится путьчерез транзитную вершину u, который короче найденного пути из х в w, он заменяется на более короткий путь. Это соотношение должно проверяться для любой возможной из n-2 транзитных вершин при оценке пути в каждую вершину, поэтому в алгоритме имеется цикл, определенный в строке 4.

Алгоритм Дейкстры нахождения кратчайших расстояний от источника до всех остальных вершин применим только тогда, когда граф не имеет контуров или когда веса всех ребер неотрицательны.

Идентификаторы :

d[s,t] – массив длин ребер графа для каждой пары вершин

s,t X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число.

х – вершина-источник графа <X,U>.

n=|X| - число вершин графа.

u,w – рабочие переменные.

D[w] – массив, в котором к концу работы алгоритма будут содержаться кратчайшие

длины путей из x в w для всех вершин w X.

BEGIN

D[x]:=0;

For w X do D[w]:=d[x,w];

T:={X&bsol;{x}};

While T=&bsol;= do

Begin

w:=вершина r из T такая, что D[r]=min{D[p]:p из T};

T:={T&bsol;{w}};

For u T do D[w]:=min[D[w],D[u]+d[u,w]];

End

END

Алгоритм Форда-Фалкерсона нахождения максимального потока в сети.

Многие задачи исследования операций сводятся к анализу потоков, маршрутов, последовательностей событий, протекающих со времени, и других процессов, которые можно представить в виде множества взаимосвязанных элементов. Для математического представления таких процессов удобно их задание в виде графов.

Рассмотрим конечный ориентированный граф Г=(X,u), в котором Х={x1,...,xn}-множество вершин, U – множество дуг.

Пусть 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 не помечен, то перейти к построению разреза.

II.Построение разреза.

Искомый минимальный размер R определяется двумя множествами Х1 и Х2, где Х1 – все помеченные вершины, Х2 – вершины, которые не удается пометить. При этом полный поток Ф=Ф* должен быть равен величине полученного минимального разреза.

2.Сетевые структуры на базе

теоретико-графовых моделей

2.1. Методы построения сетевых структур

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

Соединения компьютеров в сети может осуществляться по-разному, и различным типовым способам присвоены различные наименования.

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

В сетях с архитектурой клиент-сервер специализированный компьютер (выделенный сервер) используется для установки всех разделяемых ресурсов. Такое решение ускоряет доступ пользователей к централизованным ресурсам сети и связано с рядом особенностей :

- сетевое администрирование проще за счет незначительного числа серверов в сети и их узкой специализации;

- предъявляются высокие требования к выделенному серверу : для обеспечения высокой производительности требуется установка на сервере большого количества оперативной памяти, диска большой емкости и использования в сервере производительного процессора;

- при нарушении работы сервера сеть становится практически неработоспособной.