31

Математические основы теории сетей

Другое

Экономическая теория и математическое моделирование

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

Русский

2012-11-14

986.5 KB

70 чел.

Министерство Образования и Науки Украины

ДВНЗ «Донецкий национальный технический университет»

Кафедра автоматики и телекоммуникаций

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к выполнению лабораторных и контрольной работ по курсу

«Математические основы теории сетей»

для студентов-заочников специальности

«Телекоммуникационные системы и сети»

Утверждено на заседании

кафедры « Автоматика

и телекоммуникации»,

протокол №.__от ____.200_г.

Донецк 2008 г.


УДК

Методические указания к выполнению лабораторных и контрольной работ по курсу «Математические основы теории сетей» для студентов специальности «Телекоммуникационные системы и сети» / доц. Жукова Н.В., асс. Зайцева Э.Е. – Донецк, ДонНТУ, 2008. -   с.

Представлены указания к выполнению лабораторных и контрольной работ по курсу «Математические основы теории сетей» для студентов заочников специальности «Телекоммуникационные системы и сети» дневной формы обучения.

Составители:   доц. Жукова Н.В.

    асс. Зайцева Э.Е.

Рецензент     доц. Ладыженский Ю.В.

Ответственный за выпуск:  доц. Бессараб В.И.


Содержание

1. Лабораторная работа №1. Неориентированные графы………………….

2. Лабораторная работа №2. Направленные ориентированные графы…....

3. Контрольная работа №1. Отказоустойчивые сети………………………


Лабораторная работа № 1

Тема: «Неориентированные графы»

Цель: Приобретение практических навыков работы с неориентированными графами

1.1. Теоретические сведения [1].

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

Мы будем  рассматривать только конечные графы, т.е. . Если  и , то граф  имеет порядок и размер . Говорят, также, что  – -граф. Для -графа истинным является неравенство .

Основные способы задания -графа  – следующие:

  1.  Перечисление в явном виде элементов множеств  и .
  2.  Графическое изображение, т.е. вершины графа изображаются кружками, а ребра – линиями, соединяющими пары кружков (в соответствии с этой интерпретацией и говорят, что ребро  соединят вершины  и , если вершины  и  инцидентны ребру ).
  3.  Матрица смежности вершин, т.е. булева матрица порядка , строки и столбцы которой занумерованы элементами множества . Элемент матрицы, расположенный на пересечении строки  и столбца  равен  тогда и только тогда, когда  и  – смежные вершины.
  4.  Матрица смежности ребер, т.е. булева матрица порядка , строки и столбцы которой занумерованы элементами множества . Элемент матрицы, расположенный на пересечении строки  и столбца  равен  тогда и только тогда, когда  и  – смежные ребра.
  5.  Матрица инциденций, т.е. булева матрица порядка , строки которой занумерованы элементами множества , а столбцы – элементами множества . Элемент матрицы, расположенный на пересечении строки  и столбца  равен  тогда и только тогда, когда вершина  инцидентна ребру .
  6.  Списки смежности вершин, т.е. совокупность  списков, занумерованных элементами множества . Список, занумерованный элементом , состоит из всех вершин, смежных с вершиной .
  7.  Списки смежности ребер, т.е. совокупность  списков, занумерованных элементами множества . Список, занумерованный элементом , состоит из всех ребер, смежных с ребром .

Пример 1.1. Граф

задан перечислением его множеств вершин и ребер: ,  .

Графическое изображение графа  показано на рис.1.1.

Матрицы смежности вершин и ребер, соответственно,  и , а также матрица инциденций  графа  имеют следующий вид:

,,

.

Списки смежности, определяющие граф , показаны на рис. 1.2.

В графе  множества вершин  и   называются, соответственно, открытой и замкнутой окрестностью вершины .

Таким образом, представление графа списками смежности – это перечисление замкнутых окрестностей всех его вершин.

Число   называется степенью вершины . Как правило (хотя это не является обязательным требованием), вершины графа нумеруются в порядке не убывания их степеней, т.е. если  – -граф, то предполагается, что . Отметим, что именно такая нумерация вершин графа принята в примере 1.1.

В 1736 году Л. Эйлер установил следующее свойство последовательности степеней вершин графа.

Теорема 1.1 (Лемма о рукопожатиях). Сумма степеней всех вершин графа  равна удвоенному числу его ребер, т.е. .

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

Два различных -пути  и  в графе  называются независимыми, если .

Пример 1.2. В графе  из примера 1.1:

  1.  Подграф , где , , является -путем длины 3;
  2.  Подграф , где , , путем не является;
  3.   пути  и , где ,  не являются независимыми.

Понятие ‘путь в графе’  дает возможность определить метрику (т.е. расстояние) на множестве  вершин следующим образом:

  1.   для всех ;
  2.   равно наименьшей длине –пути, если такой путь существует;
  3.   , если –путь не существует.

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

Пример 1.3. Для графа  из примера 1.1 , , .

Граф  – связный, если для любых двух его вершин  и  существует -путь. Максимальные связные подграфы графа  называются его компонентами связности. Ясно, что любая такая вершина  графа , что  (такая вершина называется изолированной) является компонентой связности графа .

Операции удаления вершин или ребер графа могут изменить количество компонент связности. В связи с этим выделяются следующие вершины и ребра:

  1.  вершина  графа  – точка сочленения, если число компонент связности графа  больше числа компонент связности графа ;
  2.  ребро  графа  – мост, если число компонент связности графа  больше числа компонент связности графа .

Пример 1.4. В графе  из примера 1.1 ребро  – мост, а вершина  – точка сочленения.

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

Такое определение предполагает, что зафиксирована ориентация от начальной вершины  к финальной вершине , что подчеркивается использованием термина: “-прогулка”.

След (a trail) (используется, также, термин цепь) – это прогулка, в которой все ребра  попарно различны.

Очевидно, что путь может рассматриваться как прогулка (или след) с попарно различными вершинами.

След  называется контуром (a circuit), если .

Для обозначения контура  используется запись . Подчеркнем, что контур  содержит ребро .

Отметим, что для цикла (как и для контура) предполагается отсутствие ориентации.

Пример 1.5. В графе  из примера 1.1

а) последовательность  является прогулкой;

б) последовательность  является следом;

в) последовательность  является контуром и, более того, эта последовательность является циклом.

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

Путь или цикл – гамильтонов, если он содержит все вершины графа.

Контур, след или прогулка – эйлеров, если он содержит все ребра графа.

Теорема 1.3. Связный граф содержит:

  1.  эйлеров контур тогда и только тогда, когда степень каждой его вершины – четная;
  2.  эйлеров -след тогда и только тогда, когда  и  – единственные вершины графа, имеющие нечетную степень.

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

2. Граф  не содержит ни эйлерова контура, ни эйлерова следа, так как он содержит 4 вершины, степень которых – нечетное число.

Теорема 1.4. Множество ребер графа  может быть разбито на циклы тогда и только тогда, когда степень  каждой вершины  – четное число.

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

Зафиксируем порядок на множестве ребер -графа , т.е. считаем, что .

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

Подпространство  называется пространством циклов графа , а число  называется циклическим рангом (или цикломатическим числом) графа .

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

Часто возникает необходимость размечать вершины и/или ребра графа элементами некоторого множества. Формально, разметка вершин, соответственно, ребер, графа  элементами множества  (или, более кратко, -разметка) – это отображение , соответственно, , возможно, удовлетворяющее некоторым дополнительным условиям. Среди -разметок вершин (соответственно, ребер) графа  выделяют раскраски, т.е. -разметки, у которых образы любых двух смежных вершин (соответственно, ребер) – различные.

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

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

От раскраски ребер легко перейти к раскраске вершин, если заменить граф  его реберным графом , где .

Ясно, что если  представляет собой -граф, то  представляет собой -граф, где  представляет собой последовательность степеней вершин графа .

Известен ряд оценок для вершинно-хроматического числа графа, среди которых отметим оценку .

Граф называется ациклическим (или лесом), если он не содержит циклов.

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

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

Пример 1.7. Число остовных подграфов графа  из примера 1.1, равно .

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

Пример 1.8. Многочисленные применения имеет следующая  задача, связанная с остовными деревьями. На множестве ребер графа  задана функция стоимости . Стоимость подграфа  определим числом .

Требуется для графа  найти остовное дерево наименьшей стоимости.

Рассмотрим четыре метода решения этой задачи для графа , изображенного на рис. 1.3. а).

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

Для того чтобы применить этот метод, выпишем ребра графа  в порядке не убывания их стоимости    (*)

Двигаясь по последовательности (*) слева направо, осуществляем выбор 5-и ребер (так как число ребер у дерева с  вершинами равно ). В результате получим дерево, изображенное на рис. 1.3.б).

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

Для того, чтобы применить этот метод двигаемся по последовательность (*) справа налево. В результате получим дерево, изображенное на рис. 1.3.б).

3-ий метод состоит в следующем. На 1-м шаге выбирается произвольная вершина  графа и, среди инцидентных ей ребер, ребро  наименьшей стоимости.

В результате порождено двухэлементное множество вершин  и одноэлементное множество ребер .

Далее  раза выполняется итеративная процедура в соответствии с правилом: если  и  – множества, соответственно, вершин и ребер, порожденных на -й итерации, то на –й итерации среди ребер вида , где  и  выбираем ребро   наименьшей стоимости,  и .

Применяем рассматриваемый метод.

Пусть выбрана вершина  графа . Оба инцидентных ей ребра  и  имеют одну и ту же стоимость, равную 4 (см. рис. 1.3.а). Выберем ребро . Таким образом , .

Применяем 4 раза описанную выше итеративную процедуру. Получим

                              ,                         ,

                              ,                   ,

                              ,              ,

                              ,        ,

т.е. построено остовное дерево, изображенное на рис. 1.3.г).

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

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

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

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

Применяем к полученному графу 4-й метод.

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

Таким образом, , .

Применяем описанную выше процедуру. Получим , . Следовательно, , .

Так как  – одноблочное разбиение множества вершин графа , то вычисления закончены. Построено остовное дерево графа , изображенное на рис. 1.3.г).

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

Число этих циклов равно .

Следовательно, указанные циклы образуют базис векторного пространства .

1.2. Задание.

Для связного графа с 10-ю вершинами (рис.1.4) выполнить следующие действия:

а) вычислить размер и порядок графа ;

б) представить граф : матрицами смежности вершин и ребер, матрицей инциденций, списками смежности вершин и ребер;

в) определить для каждой вершины  () открытую и замкнутую окрестности;

г) найти последовательность степеней вершин графа  и сумму степеней всех вершин;

д) найти диаметр, радиус, центр графа  и эксцентриситет каждой вершины;

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

Варианты заданий

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

Рис.1.4 Связный неориентированный граф

Лабораторная работа № 2

Тема: «Направленные ориентированные графы»

Цель: Приобретение практических навыков работы с ориентированными графами

2.1. Теоретические сведения [1].

Конструкция    называется направленным графом (а directed graph).

Способы задания:

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

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

3) в матрице инциденций (не являющейся булевой) направленного графа элемент, расположенный на пересечении строки  и столбца , равен:

а) 1 (т.е. единица), если  – начало дуги ;

б) –1 (т.е. минус единица), если  – конец дуги ;

в) 0 (т.е. нуль) в остальных случаях.

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

Отметим, что введенные выше открытые окрестности вершины характеризуют следующие типы вершин направленного графа :

а) вершина  – источник (иногда такую вершину называют граничной) тогда и только тогда, когда  и ;

б) вершина  – сток (в ориентированном дереве такую вершину называют висячей или листом) тогда и только тогда, когда  и ;

в) вершина  – изолированная тогда и только тогда, когда .

4) представлением направленного -графа  списками смежности вершин называется упорядоченная пара  -элементных последовательностей списков , , где:

- элементы каждого списка   представляют собой расположенные в порядке возрастания элементы множества ;

- элементы каждого списка   представляют собой расположенные в порядке возрастания элементы множества .

  1.  представлением направленного -графа  списками смежности дуг назовем упорядоченную четверку  -элементных последовательностей списков:

,

,

,

.

Пример 2.1. Представим списками вершин и дуг направленный -граф , графическое представление которого изображено на рис. 1.6.

Представление направленного графа  списками смежности вершин изображено на рис 1.7.

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


2.2. Задание
.

а) преобразовать неориентированный граф  из лабораторной работы № 1 в орграф, выбрав ориентацию его ребер от вершины с меньшим индексом к вершине с большим индексом;

б) представить полученный орграф : матрицами смежности вершин и ребер, матрицей инциденций, списками смежности вершин и ребер;

Контрольная работа № 1

Тема: «Отказоустойчивые сети»

Цель: Приобретение практических навыков при формировании отказоустойчивых сетей.

1.1. Теоретические сведения [1].

Рассмотрим задачу: для исходной системы, заданной в виде графа , требуется найти минимальный объемлющий граф , , такой, чтобы при «отказе» любой вершины или ребра в  (а значит и в ) в «неисправном» графе  существовал подграф , изоморфный . Для более наглядного восприятия представим графы в виде связных областей:

Изучаемые объекты  отказоустойчивые графы.

Свойства отказоустойчивых графов.

«Точки» спектра отказоустойчивых графов являются -вершинными однородными графами , имеющими порядок их группы симметрий не менее . В подавляющем большинстве случаев эти графы имеют, по крайней мере, одну из групп симметрии типа  (циклическую группу вращений порядка ),  или  (диэдральную группу симметрий соответственно порядка  или ). Графы, у которых  имеют еще и другие группы. Так, например, для  существуют 15 различных одноотказоустойчивых графов с симметрией  и 17 графов с симметрией .  (Здесь базовой подструктурой, понижающей порядок группы симметрии в два раза, выступает подграф «пятиконечная звезда» или вдвое прореженные «спицы», или их комбинация, имеющие симметрию .)

В каждый из этих графов может быть вложен некоторый 9-вершинный исходный (целевой) граф. Последний как раз и является инвариантом отказоустойчивого графа по отношению к «отказам» удалением вершины или связи в графе. Упомянутый «спектр» расщепленный, т.е. одной и той же симметрии может отвечать множество графов. Чем же различаются такие графы?

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

Введем нумерацию вершин по кольцу в выбранном направлении. Будем считать хордами все ребра, отличные от принадлежащих кольцу. Тогда хорда  соединяет две вершины  и  на кольце, и число ребер, лежащих на кольце между  и  при  назовем «шагом» между  и .

Число ребер  (по mod n) между вершинами  и  назовем расстоянием между ними, а хорду   «шагом» длиной  (по mod. n). Обозначим -вершинный отказоустойчивый граф .

Вершинную степень и набор  длин шагов в графе  будем рассматривать в качестве его характеристик (напомним, что отказоустойчивый граф однороден). Любой член «спектра» может быть выражен через эти характеристики.

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

Минимальное расширение цикла.

Начнем с простейшей структуры цикла, которая будет служить базовой во всех последующих рассмотрениях. Рассмотрим произвольный цикл из  вершин (), числовое значение  не играет существенной роли, для иллюстрации (см. рис. 3.4) возьмем .

Как минимально вложить этот цикл в 1-отказоустойчивый граф в предположении общей модели неисправностей (отказывают вершины и ребра)?

Приведём следующий алгоритм А1.

Выберем для ребро . Эта связь – хорда с шагом 2. На этом этапе «расширенный» цикл будет выглядеть следующим образом (рис. 2.15.).

Протранслируем единственную хорду в расширенном графе  по циклической группе . Найденный граф  есть минимальное 1-отказоустойчивое расширение для цикла  (рис. 2.16.). На рис. 2.16 жирным выделен целевой граф  в минимальном избыточном графе .

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

Простой «произвольный» граф.

На простейшем примере «несимметричного» графа можно проследить применение алгоритма А1 для нахождения минимального (или минимизированного) вложения его в 1-отказоустойчивый граф . Этот пример поможет более детально понять возможности отказоустойчивого вложения.

Согласно алгоритму А1, для 1-отказоустойчивого графа первой попыткой должно быть добавление одной избыточной вершины  в гамильтонов цикл, или путь целевого графа  (рис. 2.17), с сохранением всех инцидентностей вершин целевого графа. В рассматриваемом примере существует гамильтонов путь . Замыкание вершин  и  через дополнительно вводимую избыточную вершину  образует гамильтонов цикл . Расширение  показано на рис. 2.18.


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

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

Следующий шаг – симметрирование «расширенного» графа  до отказоустойчивого . Для этого все хорды в расширенном графе транслируются по циклической группе , в результате чего получается один из членов «спектра» 7-вершинных графов, приведенный на рис 2.19:

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

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

Напомним, что искомый автоморфизм всегда существует. Их может быть и больше одного (в «среднем» их два).Граф  имеет вид, приведённый на рис 2.21.

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

Общий алгоритм нахождения минимизированного вложения целевого графа  в 1-отказоустойчивый.

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

Алгоритм А2 (вложение)

  1.  Выбрать гамильтонов цикл, или гамильтонов путь, в целевом графе , если он существует. Если нет ни одной из этих двух конструкций или их нахождение затруднено, достроить целевой граф дополнительными ребрами так, чтобы образовалась хотя бы одна из них.
  2.  Отобразить выбранный цикл (путь) на естественный (в порядке возрастания номеров) -цикл. (Это облегчит нахождение нужных автоморфизмов.)
  3.  Расширить естественный -цикл на одну дополнительную вершину в соответствии с алгоритмом А1.
  4.  Построить расширенный целевой граф , восстановив инцидентности вершин целевого графа, нарушенные введением в цикл новой вершины.
  5.  Если а)   нечетное, то протранслировать хорды расширенного целевого графа по ; б)   четное, то хорды, имеющие четную длину, протранслировать по группе  и по группе . Различные комбинации указанных трансляций дают варианты вложения.
  6.  Оценить результаты вложения в полученных вариантах по величинам  и . Если достигнутый результат приемлем, то переходим к п.7, если полученный результат не удовлетворяет, то сделать новое расширение расширенного целевого графа  еще на одну дополнительную вершину, переход к п.4.
  7.  Конец.

Методика вложения произвольных гамильтоновых графов.

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

Общая методология вложения произвольных циклов:

  1.  В целевом графе выбирается гамильтонов цикл (достраивается до него, если это необходимо) и отображается на простой («естественный») nвершинный цикл.
  2.  Дополнить гамильтонов цикл инцидентностями вершин целевого графа и найти самую длинную хорду(ы) длиной s (по модулю n) в метрике выбранного цикла.
  3.  Расширить исходный nвершинный цикл до (n+1)вершинного добавлением одной вершины в исходный цикл так, чтобы не увеличивать длину sхорд, если это возможно.
  4.  Протранслировать все хорды в расширенном цикле по группе  или , если последнее возможно. Найденный граф будет 1отказоустойчивым.
  5.  Добавляя в (n+1)вершинный цикл еще одну избыточную вершину с сохранением старых инцидентностей вершин и транслируя все хорды по группе  (после п. 4 трансляция по группе  уже невозможна), находится 2отказоустойчивое решение и т.д.

Менее экономичное решение получится, если расширение цикла произошло с увеличением длины хотя бы одной sхорды.

Перейдем к более сложным примерам целевых графов, для которых ищутся kотказоустойчивые структуры, а именно: к решеткам.

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

Рассмотрим решетку  (рис 2.23). В ней 9 вершин, и поиск 1-отказоустойчивого вложения надо начинать с 10-вершинного объемлющего графа. В исходной решетке есть вершина степени 4 (ее номер 4), поэтому и искомый отказоустойчивый граф должен быть степени 4 или выше.

Выберем гамильтонов путь 0-1-2-3-4-5-6-7-8 и нанесем (отобразим) его на простой (9+1)вершинный цикл, имеющий «естественную» нумерацию по часовой стрелке.

Замкнем гамильтонов путь от вершины 8 через добавочную вершину 9 на 0. Связи (8,9), (9,0), (2,3), (6,5), не принадлежавшие выбранному гамильтонову пути, даны на рис. 3.13 тонкими линиями.

Нанесем на этот расширенный цикл инцидентности вершин целевого графа – решетки  (рис. 2.24).

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

Отметим, что здесь результат получен без увеличения максимальной степени вершин.

В табл. 3.1 приведены затраты на достижение 1отказоустойчивости решетки .

Таблица 3.1

Элементы решетки

Рабочие

Избыточные

Вершины

9

1

Ребра

6

4

Хорды

6

4

Связи (общ.)

12

8

Другой выбор исходной нумерации вершин целевого графа 0-1-2-3-4-5-6-7-8 и его отображение на «естественный» простой 10-вершинный цикл дает менее экономное решение с повышением степени вершин до 5, что дает большее число добавочных хорд в отказоустойчивом графе.


Список литературы

  1.  В.Г. Скобелев Конспект лекций по курсу «Математические основы теории сетей», Донецк: ДонНТУ, 2006 г. – 85с. Эл. Вар.
  2.  Харари Ф. Теория графов. – М.: Мир, 1973. – 300с.
  3.  


 

А также другие работы, которые могут Вас заинтересовать

63159. Урок-узагальнення з теми «Передня Азія» 35.66 KB
  Мета. Систематизувати та узагальнити знання учнів із теми; ознайомити з культурною спадщиною та релігійними віруваннями народів Передньої Азії; простежити взаємозвязок між господарським і духовним розвитком країн; розширити світогляд школярів...
63160. Урок-узагальнення з теми «Греція в II — першій половині І тис. до н. є.» 27.03 KB
  Кожна з чотирьох команд грає з усіма іншими тобто має відбутися 6 раундів І II І III І IV II III II IV III IV. 3 Кожний раунд включає чотири питання різного ступеня складності що оцінюються так: перше питання 1 бал друге 2 бали третє...
63161. Римська республіка II—І ст. до нашої ери 33.42 KB
  Мета: розглянути особливості устрою римської армії епохи республіки; ознайомитися з ходом перетворення Риму на центр величезної держави; визначити причини та наслідки суспільно-політичної боротьби в Римі...
63162. Ліси: хвойні, листяні, мішані 109.98 KB
  Корекційно-навчальна мета: формувати у дітей поняття ліс листяні ліси хвойні ліси мішані ліси; навчити розпізнавати види лісів за назвою та малюнками дерев. Обладнання: мультимедійна дошка проектор картки...
63163. Принципи здорового способу життя 20.74 KB
  Мета: Ознайомити учнів з поняттям €œздоровий спосіб життя продовжувати формувати в учнів активну мотивацію щодо дбайливого ставлення до власного здоров’я. Виховувати прагнення берегти своє здоров’я зважаючи на його цінність і значимість.
63165. Память как познавательный процесс 106 KB
  Память - это процессы организации и сохранения прошлого опыта, делающего возможным его повторное использование в деятельности или возвращение в сферу сознания. Память связывает прошлое человека с его настоящим и будущим и является важнейшей познавательной функцией
63166. Право як навчальний предмет. Мета, завдання, особливості курсу 22.77 KB
  Обладнання й матеріали: Конституція України Конвенція ООН про права дитини Загальна декларація прав людини плакати з висловами відомих людей про права людини. Мир прогрес права людини ці три цілі нерозривно повязані неможливо досягнути...
63167. Вступ до історії стародавнього світу 28.52 KB
  Мета: Сформувати уявлення про хронологічні межі та предмет історії стародавнього світу дати визначення понять стародавній світ історичне джерело археологічні памятки розвивати навички відліку часу до н. Після цього уроку учні зможуть...