Проектирование, виды проектирования в зависимости от степени автоматизации. Проектирование телекоммуникационных сетей на ЭВМ, страница 4

2.  Ребро

11.  Пути в графовых моделях сетевых структур, волновой алгоритм; определение расстояния во взвешенном графе.

Имеется два частных случая в поиске кратчайших путей:

1.  Если граф является не взвешенным применяется один из возможных алгоритмов – волновой.

2.  Граф является взвешенным и если они не отрицательны, применяется алгоритм Дейкстры.

Волновой алгоритм.

Состоит из двух шагов. Предназначен для построения дерева кратчайших путей из заданной вершины S.

Шаг 1: заданную вершину S обозначаем как вершину нулевого яруса. Далее найти смежные с ней вершины и обозначить как вершины первого яруса (при этом перерисовывают графовую модель из вершины S как из корня).

Шаг 2: рассмотреть множество вершин предыдущего яруса и ярус тех вершин, которые смежны с вершинами предыдущего яруса. Шаг 2 повторяем до тех пор, пока не будут просмотрены все вершины графа.

 Вывод: расстояние от заданной вершины S определяется номером яруса, на котором оказалась вершина х_i.

Пример: задан связный невзвешенный граф. Определить расстояние от первой вершины до всех остальных.

Аналог: рыболовная сеть.

Шаг 1:

Шаг 2:

Расстояние от 1 до 3=2, от 1 до 7=3, от 5 до 3®построить новый граф, где 5 будет корнем. Расстояние только от вершины, размещенной на нулевом ярусе. Если находим расстояние между двумя вершинами, находящимися на разных ярусах, но ни один из них не является нулевым, то графовую модель необходимо перестроить таким образом, чтобы одна из этой пары вершин располагалась на нулевом ярусе.

12.  Максимальный поток в графовой модели сети. Теорема Форда-Фалкерсона.

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

Пусть задан взвешенный граф G и выделены в нем 2 вершины: S –исток, Т-сток. S – означает начало потока, т – завершение потока.

Рассматриваем обычно случай, когда с(u)ÎZ. f(u) – поток по ребру не должен превышать пропускной способности, иначе система выходит из строя. Таким образом, 0£f(u)£c(u).

Свойства потоков:

1.  0£f(u)£c(u).

2.  åf  (u)-åf  (u)=0

uÎI_x – сумма входящих потоков в вершину х,

uÎI_x – сумма исходящих потоков из вершины .

I_x – множество ребер, инцидентных вершины х, по которым входит поток.

I_x – множество ребер инцидентных вершины х, по которым исходит поток.

3.  å⁺f_y(u)=c       поток величиной с выходит из вершины х и входит в вершину у   

4.  å^-f_x(u)=c

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

Теорема Форда-Фалкерсона.

Величина максимального потоков из вершины S в вершину t равна величине минимального разреза, отделяющего S от t.

13.  Метод насыщения ребер для определения максимального потока в графовой модели сети.

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

Алгоритм:

Шаг 1: найти в графе независимые по ребрам пути из вершины S в вершину t, которые можно определить с первого взгляда.

Шаг 2: рассмотреть последовательно каждый из найденных на шаге1 путей. В рассмотренном пути найти ребра с минимальной пропускной способностью, которые отметить как насыщенные. Остальные ребра на данном пути расщепить(пропускная способность всех ребер, полученных при расщеплении и соединяющих одну и ту же пару вершин, в сумме должна быть равна пропускной способности исходного ребра, соединяющего эту пару вершин).

Шаг 3: найти последовательно все остальные пути из вершины S в вершину t, используя и ребра, которые получены при расщеплении. Каждый раз на новом пути отмечать насыщенные ребра и расщеплять все остальные.

Шаг 4: построить всевозможные разрезы через насыщенные ребра.

Шаг 5: определить величины всех разрезов по первоначальным весам, входящих в эти разрезы ребер.

Шаг 6: найти минимальный по величине разрез.

Шаг 7: найти максимальный St поток из вершины S в вершину t, величина которого равна величине минимального разреза в графе в соответствие с теоремой Форда-Фалкерсона.Определить максимальный St поток в графовой модели сети1.Через вершины 1,2,4, насыщенное ребро через 2-4 2.Через вершины 1,3,4

3.Через вершины 1,2,3,4. Максимальный поток равен 80 единиц.

14.  Метод двойственного графа для определения максимального потока в графовой модели сети.

Способ построения графа двойственного заданному. Для построения двойственного графа необходимо:

1.  Провести прямую (мысленно) через вершину исток S и сток t. Построить (мысленно) плоскость, перпендикулярную плоскости чертежа через эту прямую.

2.  По обоим сторонам плоскости на чистом поле чертеже проставить вершины двойственного графа а и b.

3.  Остальные вершины двойственного графа проставляются внутри каждого «элементарного» цикла исходного графа G.

4.  Построить ребра двойственного графа, соединяя каждую вершину с вершинами a, b и с вершинами внутри соединенных «элементарных» циклов исходного графа.

Примечания:

1.  Каждое ребро двойственного графа должно пересекать один раз какое-то ребро исходного графа.

2.  Вес ребра двойственного графа равен весу пересекаемого им ребра исходного графа.

Вывод: основное свойство двойственного графа – все пути от вершины а до вершины b в двойственном графе является разрезами исходного графа.

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