Методологические основы моделирования

• Название: Методологические основы моделирования
• Анкор: sobrannye_lektsii_1_2.docx
• Дата: 07.03.2018
• Размер: 2.94 Mb.
• Имя файла: sobrannye_lektsii_1_2.docx
• Тип: Лекция; #16341
• страница: 8 из 19

Теорема 5. Упорядоченная пара (а,в) является парой связности для вершин u и v графа G тогда и только тогда, когда существует а вершинно- непересекающихся (u-v) путей, и в реберно- непересекающихся (u-v) путей не имеющих общих ребер с а предыдущими путями и, кроме того, наибольшие возможные числа таких путей равны именно а и в.

На графе рис.27. между вершинами S и t существуют, как было показано ранее, 5 реберно – независимых путей:

¹_st = < e₁, e₈ ,e₁₉>1, v₂, v₇,v₁₁ >

²_st = < e₃, e₁₀ ,e₂₃>1, v₆, v₈,v₁₁ >

³_st = < e₅, e₁₄>1, v₅, v₁₁>

⁴_st = < e₂, e₉ ,e₁₅, e₁₇ ,e₂₁>1, v₃, v₇, v₆, v₉, v₁₁ >

⁵_st = < e₄, e₁₁ ,e₂₂, e1₈ >1, v₄, v₆,v₁₀ , v₁₁ >
При этом, первые три пути являются и вершинно- независимыми, проходящими через вершины {v₅, v₆, v₇ }, которые составляют минимальное сечение по вершинам, т.е. определяют вершинную связность графа æ(G).

Это означает, что в данном случае λ(G)=5, æ(G) =3 и упорядоченные пары (0, λ), (æ, 0) являются парами связностей для вершин S и t (v₁и v₁₁).

Построим функцую связности для вершин s и t :

σ(æ)	λ(s,t)
5	(5, 0)
4	(4, 1)
3		(3, 2)
2
1		(0, 3)	æ(s,t)

0 1 2 3
Рис.29. Функция связности σ (s,t)

Координаты функции связности для вершин (s,t) показывают, сколько вершин и ребер нужно изъять, чтобы нарушить связность между этими вершинами. Всего таких пар æ + 1, в нашем примере их 4.

Так, из рис.1.28. видно, что при сохранившихся вершинах {v₅, v₆, v₇}, необходимо нарушить все ⁱ_st путей (i=1,5).

При удалении одной из трех вершин, необходимо нарушить 4 пути, при удалении 2 вершин –3 пути, а при удалении всех 3^х вершин автоматически нарушается все 5 реберно – независимых путей.

Теорема 6: В каждом графе наибольшее число реберно- непересекающихся реберных разрезов, разделяющих две вершины u и v, равно наименьшему числу ребер простого пути, соединяющего u и v, т.е. равно расстоянию (выраженному через минимальное число ребер) между этими вершинами, т.е. d(u,v).

Например на графе рис.28 наибольшее число реберно- непересекающихся разрезов между вершинами S(v₁ ) и t(v₁₁) равно 2,т.к минимальный путь (цепь), состоит из 2^х ребер е₅ и е₁₄ (³_st = 5 , e₁₄> ).

Такими сечениями являются:

S₁= < e₁ ,e₂ ,e₃ ,e₄ ,e₅> и S₂= < e₁₄ ,e₁₉ ,e₂₁ ,e₂₂ ,e₂₃>

Все остальные сечения будут содержать одно из ребер е₅ или е₁₄ .

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

Проще всего анализ начать с выявления мостов и точек сочленения.

Выявление точек сочленения и мостов производится по одному алгоритму:
1.i=1, n (для мостов j=1, m).

2.Удалить вершину v_i (ребро е_j).

3.Проверить связность графа.

4.Если нет, то v_i (е_j) точка сочленения (мост) выполнить 5, иначе выполнить пункт 6.

5.Подсчитать точки сочленения (мосты).

6.Восстановить вершину v_i (ребро е_j).

7.Вывод результатов.

Простейший способ устранения точек сочленения и мостов заключает в том, что в компонентах связности G₁ и G₂ графа G, полученных после удаления точки сочленения (моста), определяют вершины d_imin(G₁) и d_imin(G₂) и соединяют их ребром.

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

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

Одним из наиболее экономичных (быстрых) алгоритмов определения связности является алгоритм Уоршелла. Алгоритм Уоршелла (Warshall) предназначен для определения связности графов. Он преобразует матрицу смежности А(ij) в матрицу наличия прямых или транзитных путей соответствующим переписыванием матрицы А(ij), поэтому говорят, что алгоритм работает “на месте”. Каждая вершина обрабатывается один раз, поэтому задача решается за один проход. Достоинством алгоритма является достаточно высокая скорость работы, недостатком - отсутствие контроля числа транзитов в пути, если для этого не принять специальных мер. Число транзитов может измениться от 0 до n-1. Результирующая матрица показывает, есть ли путь между произвольными вершинами исходного графа.

Суть алгоритма Уоршелла заключается в следующем. Задается исходный граф G, размерностью nxn. Алгоритм строит последовательность таких графов, что Gⁱ≤ Gⁱ⁺¹ , т.е. граф Gⁱ является подграфом Gⁱ⁺¹ , а исходный граф G = G⁰ , 0≤ i ≤ n-1. Граф Gⁱ (i ≥ 1) получается из графа G^i-1 после обработки вершины i в графе G^i-1. Обработка вершины i в графе G^i-1 включает добавление новых ребер в G^i-1 следующим образом. Пусть в графе G^i-1 присутствуют ребра , , , исходящие из вершины i ,тогда для каждого ребра , заходящего в вершину i добавляют в графе G^i-1 ребра , , , если они еще не присутствовали в графе G^i-1 .

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

1.Ввести матрицу смежности графа A(i, j)

2.Положить i =1 до n

3.Положить j =1 до n

4.Если элемент матрицы смежности a( i, j ) равен нулю то перейти к 8

5.Положить k =1 до n

6.a( j, k ) = a( j, k ) or a( i, k )

7.Положить k = k+1, если k <= n, то перейти к 5

8.Положить j = j+1, если j<= n, то прейти к 3

9.Положить i = i+1, если i<= n то перейти к 2

10.Результирующую матрицу проверить на полную связность.

Работу алгоритма Уоршелла рассмотрим на примере:
G⁰ G¹



i=1 :< 1, 2 >;< 1, 6 >

:< 4, 1 >

: < 4, 2 >;< 4, 6 >

G¹ G²
i=2 :< 2, 5 >

:< 1, 2 >;<3,2>;<4,2>

:< 1, 5 >;< 3, 5 >;<4,5>

G² G³



i=3 :< 3, 2 >;< 3, 5 >

:< 4, 3 >;< 6, 3 >

: < 4, 2 > ;< 4, 5 >

<6, 2><6,5>


G³ G⁴

i=4 :< 4, 1 >;< 4, 2 >;<4,3>

< 4, 5 >;< 4, 6 >

:< 5, 4 >

:< 5, 1 >;< 5, 2 ><5,3>

< 5, 4 >; < 5, 6 >

G⁴G⁵
i=5 :< 5, 1 >;< 5, 2 >;<5,3>

< 5, 4 >;< 5, 6 >

:< 1, 5 >;< 2, 5 >;<3,5>

< 4, 5 >;< 6, 5 >

:< 1, 2 >;< 1, 3 >;<1,4>

< 1, 6 > ;< 2, 1> ;<2,3>;

<2,4>;<2,5>;< 2, 6>;<3,1>;<3,2>;<3,4>;<3,5>;<3,6>; <6,1>;<6,2>; <6,3>; <6,4>;<6,5>

G⁵G⁶

При i = 5 получен полносвязный ориентированный граф, эквивалентныйнеориентированному.

Ребра -исходят из i-й вершины

Ребра -заходят в i-ю вершину

Ребра -добавляют к ребрам графа G^i-1, если их не было ранее

Добавляемые ребра на каждом этапе показаны пунктиром.

На этом работа алгоритма заканчивается.


Лекция 11

СИНТЕЗ СЕТЕЙ С МАКСИМАЛЬНОЙ СВЯЗНОСТЬЮ
1. Степенная последовательность вершин графа
При синтезе сетей связи с заданными свойствами важное значение имеют показатели степеней вершин. Степенной последовательностью называют список степеней вершин графа. Чаще всего этот список задают в виде упорядоченного (вариационного ) ряда по мере убывания или возрастания степеней.

Свойства графов связаны со свойствами степенных последовательностей как минимум на уровне необходимых условий. Так, чтобы графы были изоморфными, необходимым условиям является равенство степенных рядов, чтобы граф был максимально связен, необходимо равенство степеней или максимум однородности степеней и т.д. таким образом, свойства степенных последовательностей во многом определяют свойства графов, и по заданным степенным последовательностям иногда удается синтезировать графы с заданными свойствами.

Прежде всего возникает вопрос- по всякой ли конечной последовательности целых чисел d₁, d₂,…,d_n можно построить граф. Последовательность целых чисел называют графической, если можно построить такой граф, чтобы члены последовательности были степенями вершин.

Чтобы последовательность была графической, она должна быть сжимаемой.

Степенную последовательность называют правильной если выполняются два условия:

n-1≥ d₁≥d₂….≥d_n;

- четное число.

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

Пусть задана последовательность чисел, удовлетворяющая условию

k₁≥ k₁≥….≥k_n

П₁=5 ; 4; 3; 3; 2; 1.

Последовательность сжимается путем выполнения следующих операций:

из k₁ вычитается k₁ ;

из k₂; k₃; k₃;…; k_k+1; вычитается 1

полагается k₁ = 0;

из оставшихся чисел формируется новая последовательность k₁ ≥ k₂ ≥….≥ k_n;

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

k₁; k₂; k₃; k₄ ; k₅; k₆ k₁; k₂; k₃; k₄ k₂; k₃

5; 4; 3; 3; 2; 1 3; 2; 2; 1 1; 1

3; 2; 2; 1; 0 1; 1; 0 0

v₁; v₂; v₃; v₄; v₅; v₆ v₂; v₃; v₄ v₃; v₄
Последовательность сжимаемая, значит графическая, граф состоит из 6 вершин со степенями к_i = d_i .

Первый шаг сжатия последовательности является первым шагом построения графа, т.е. из вершины k₁ проводятся k₁=5ребер в вершины v₂; v₃; v₄; v₅; v₆.(Ребра показаны сплошными линиями).

Второй шаг сжатия последовательности является вторым шагом построения графа. Из вершины v₂ с k₁ =3 проводятся 3 ребра в вершины v₃; v₄; v₅.(Ребра показаны пунктирными линиями).

Третий шаг –из вершины v₃ проводятся ребро в v₄ граф со степенным рядом вершин d:{5;4;3;3;2;1} построен.(ребро V₃V₄ показана штрих-пунктирной).


Рис. 1. Граф G₁ (П₁)

Пусть теперь последовательность имеет вид:

П₂ = 5; 4; 4; 3; 2; 2

Первый шаг – ведущая вершина v₁(5) соединяется с вершинами v₂; v₃; v₄; v₅; v₆, степенная последовательность принимает вид : 0 3 3 2 1 1

Второй шаг- ведущая вершина v₂(3) соединяется с вершинами v₃; v₄; v_5, сжимаемая последовательность принимает вид: 0 0 2 1 0 1.

Третий шаг- ведущая вершина v₃ соединяется с вершинами v₄; v₆ , конец.


Рис. 2. Граф G₂(П₂)

Для последовательностей П₁, П₂ выполняется одно из необходимых условий изоморфного вхождения графа G₁(П₁) в граф G₂(П₂), а именно П₂≥ П₁, т.е. . В данном случае этого условия достаточно, чтобы граф G₁ вкладывался в граф G₂. Графы будут изоморфны, если удалить ребро v₃v₆, в этом случае совпадут и последовательности П₁ и П₂. Однако в общем случае этого условия не достаточно.

Изложенный способ построения графа по заданной степенной последовательности называют ℓ- процедурой, а вершину k₁ на каждом шаге- ведущей вершиной.
2. Алгоритм синтеза графов с максимальной связностью
В зависимости от выбора ведущей вершины ℓ- процедура может строить различные реализации графов, в том числе и с заданными свойствами. Так с помощью ℓ- процедуры можно построить такую реализацию графа, у которой реберная связность (G) будет максимальной. Основанием для этого служит теорема Д. Уэла: каждая правильная графическая степенная последовательность имеет реализацию, число реберной связности которой (G)=d_n.

Такая реализация строится ℓ- процедурой, на каждом шаге которой ведущей является вершина с минимальной степенью.

Пример. Задана последовательность:

П₃= 5 4 4 3 2 2.

Построить граф с максимальной реберной связностью

1шаг- ведущая вершина v₆(2) соединяется с v₁ и v₃, последовательность принимает вид: 4 3 4 3 2 0;

2шаг- ведущая вершина v₅(2) соединяется с вершинами v₁,v₃, последовательность принимает вид: 3 3 3 3 0 0;

3^-ий шаг- ведущая вершина v₁(3) соединяется с вершинами v₂, v₃ и v₄, последовательность принимает вид : 0 2 2 0 0;

4^-ый шаг- ведущая вершина v₂(2) соединяется с v₃, v₄, последовательность принимает вид 0 0 1 1 0 0;

5^-ый шаг- соединяются вершины v₃ и v₄, конец.




Рис.3. Граф G₃(П₃).

Полученный граф G₃(П₃) изоморфен графу G₂(П₂) . Изоморфность доказывается равенством последовательностей П₂ = П₃( необходимое условие) и наличием гамильтоновых циклов:

С₂ = v₁ v₆ v₃ v₄ v₂ v₅ v₁

C₃ = v₁ v₅ v₃ v₄ v₂ v₆ v₁ , которые совпадают при подстановке v₅→v₆ и наоборот, т.е. при перенумерации вершин v₅ и v₆ любого из графов (достаточное условие).
3. Алгоритмы синтеза графов с максимальной связностью при заданном числе вершин и ребер.
Рассмотрены случаи построения графов, в том числе и с максимальной реберной связностью, когда заданы степенные последовательности вершин.

Однако чаще задача формализуется другим образом.

Задано: n – число вершин графа и m –число ребер, которые нужно распределить на вершинах графа таким образом, чтобы граф обладал наибольшей реберной связностью.

Харари показал, а Свами привел подробную процедуру построения графа H_k,n, который является k-связным и содержит ровно m=[kn/2] ребер. Процедура заключается в том, что в графе H_k,n между i-й и j-ой вершинами ребра прокладываются по следующим правилам:

I-случай k=2r-четно: тогда H_2r,n строится на вершинах v₀,v₁,…,v_n-1 и две вершины v_i и v_jсмежны, если i-r ≤ j ≤ i+r .

II-случай k =2r+1: n- четно: тогда H_2r+1,n получается из графа H_2r,n введением ребер, соединяющих вершины v_i и v_jдля i=0,1,2,…,n/2 и j=i+n/2(modn).

III-случай k=2r+1: n-нечетно, тогда H_2r+1,n получается из графа H_2r,n введением ребер, соединяющих вершины v_i и v_jдля i=0,1,2,…,(n-1)/2 и j=i+(n+1).2(mod n). Блок –схема алгоритма, реализующего процедуру Свами-Хараи приведена на рис.4.

Процедура работает при соблюдении равенства m=[k.n/2] с учетом выполнения требования . В этом ограничение процедуры.

При произвольном m и n и естественном ограничении хорошо работает алгоритм Колесникова-Федорова.

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

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

Метод работает при любом соотношении m и n. Тонким моментом алгоритма является выбор вершины перехода на очередную диагональ, поскольку его иногда не удается формализовать, но реализовать эвристически просто из-за наглядности “ручной” реализации.

Оба алгоритма дают одинаковые результаты, когда k = 2m/n – целое число. Для исключения эвристических решений, когда k = 2m/n – не целое число, метод может быть усовершенствован и существенно упрощен путем переноса процесса оптимизации из области формирования последовательных структур в область формирования оптимальных (рациональных) степенных последовательностей вершин синтезируемого графа.

Рис.4. Блок-схема алгоритма, реализующего процедуру Свами-Харари.

При этом требование максимальной равномерности степеней вершин и равномерного распределения оставшихся ребер удовлетворяется следующим образом.

Определяется минимальная степень вершин d_imin=[2m/n] в остатке получается 1≤ r ≤ n-1 вершин, это значит, что n-r вершин имеют степень d_imin, а r- вершин имеют степень d_imах= d_imin+1. Причем порядок распределения вершин с разными степенями должен быть также максимально равномерным. При этом , если r_imах, если r≥n/2, то распределяются d_imin.

Естественно, что количество оставшихся вершин должно быть четным (каждое ребро содержит 2 вершины), а получаемая последовательность - графической.

Далее по полученной степенной последовательности строится граф максимальной связности с использованием ℓ-процедуры [1 ].

Пример. Дано n=4, m=5 построить граф максимальной связности.

Решение

Определим k= d_imin = (2m /n)+r = 2.5/4 =2+2(mod4).

d_imax = d_imin +1=3

Определим степенную последовательность- это П₁= {2;3;2;3} или П₂ = {3;2;3;2}.

С помощью ℓ-процедуры строим граф по П₁:


2 3 2 3 1. Соединяем 1 со 2^-ой и 4^-ой вершин
0 2 2 2 2. Соединяем 2^-ой со 3^-й и 4^-й вершин
0 0 1 1 3. Соединяем 3^-ю и 4^-ю вершин

Построим граф по П₂:


3 2 3 2 1. Соединяем 2^-ю с 1^-й и 3^-й вершин
2 0 2 2 2. Соединяем 1^-ой с 3^-й и 4^-й вершин
0 0 1 1 3. Соединяем 3^-ю и 4^-ю вершин
Графы изоморфны, граф G₂(П₂) получается из графа G₁(П₁) поворотом на 90 ^ο против часовой стрелки вокруг центра симметрии с помощью подстановки

1 2 3 4

t = 4 1 2 3

Как и следовало ожидать, оба графа имеют максимальное ( при заданных m и n ) число остовных деревьев- 8.