Теория графов

Федеральное агентство  по образованию

Государственное образовательное учреждение высшего

профессионального образования

«Ярославский  государственный технический университет»

Кафедра «Информационных  систем и технологий»

 

 

 

 

 

Контрольная работа защищена

с оценкой

Доцент

_____________А.Б. Петров

 

 

 

 

ТЕОРИЯ  ГРАФОВ

 

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

по дисциплине «Теория графов»

 

ЯГТУ 230201.65-001

 

 

 

 

 

 

Работу выполнил

студент гр. ДСИТ-37

_____________C.Б. Иванов

 

 

 

 

 

 

 

 

 

2011

 

Содержание

 

Задание 1………………………………………………………………………………..2 стр.

Задание 2………………………………………………………………………………..5 стр.

Задание 3………………………………………………………………………………..5 стр.

Задание 4………………………………………………………………………………..7 стр.

Задание 6………………………………………………………………………………..9 стр.

Задание 7………………………………………………………………………………..10 стр.

 

 

Задание 1.

Для заданного  графа написать матрицу смежности, матрицу инциденций и списки смежности.

 

Решение:

Матрица смежности  А(i,j), размерность 11*11, т.к. число вершин равно 11. Если из i-й вершины идет ребро в j-ю вершину, то элементу a_ij:=1, если нет то a_ij:=0

 

 

 

 

 

 

 

 

Матрица инциденций B(Vi,Ej), размерность 11*17, т.к. число вершин равно 11, а число ребер - 17. Если вершина Vi инцидентна ребру Ej, то b_ij:=1, если нет то b_ij:=0.

 

 

 

 

 

 

 

 

 

 

Список смежности. Для каждой вершины записываем смежные ей вершины.

1	7,2
2	1,3
3	2,4,8,10
4	3,5,7,11
5	4,6
6	5,7,8,9
7	1,4,6,8
8	3,6,7,10
9	6,10
10	3,8,9,11
11	4,16

 

 

 

 

Задание 2.

В заданном графе  построить Эйлеров цикл (алгоритм Эйлера).

Решение:

Так как граф замкнутый и число ребер каждой вершины четное, то Эйлеров цикл существует. Цикл начинается из произвольной вершины – 1, тогда цикл будет иметь вид:

1-2-3-8-10-3-4-11-10-9-6-5-4-7-8-6-7-1.

 

Задание 3.

В заданном означенном графе построить кратчайший остов (алгоритм Прима или Краскала).

 

 

Решение:

Используя алгоритм Прима 

Начальная точка  – 1

Выбираем ребро  идущее из вершины 1 с наименьшим весом – 5 (ребро ведущее к вершине 7).

Выбираем ребро идущее из вершины 7 с наименьшим весом – 5 (ребро ведущее к вершине 8).

Выбираем ребро идущее из вершины 8 с наименьшим весом – 8 (ребро ведущее к вершине 10).

Выбираем ребро  идущее из вершины 10 с наименьшим весом – 4 (ребро ведущее к вершине 3).

Выбираем ребро идущее из вершины 3 с наименьшим весом – 8 (ребро ведущее к вершине 4).

Выбираем ребро  идущее из вершины 4 с наименьшим весом – 3 (ребро ведущее к вершине 11).

Выбираем ребро  идущее из вершины 11 с наименьшим весом – 5 (ребро ведущее к вершине 10).

Выбираем ребро  идущее из вершины 10 с наименьшим весом – 7 (ребро ведущее к вершине 9).

Выбираем ребро идущее из вершины 9 с наименьшим весом – 10 (ребро ведущее к вершине 6).

Выбираем ребро  идущее из вершины 6 с наименьшим весом – 3 (ребро ведущее к вершине 5).

Выбираем ребро идущее из вершины 5 с наименьшим весом – 7 (ребро ведущее к вершине 4).

Выбираем ребро идущее из вершины 4 с наименьшим весом – 10 (ребро ведущее к вершине 7).

Выбираем ребро  идущее из вершины 7 с наименьшим весом – 5 (ребро ведущее к вершине 6).

Выбираем ребро  идущее из вершины 6 с наименьшим весом – 12 (ребро ведущее к вершине 8).

Выбираем ребро  идущее из вершины 8 с наименьшим весом – 9 (ребро ведущее к вершине 3).

Выбираем ребро идущее из вершины 3 с наименьшим весом – 8 (ребро ведущее к вершине 2).

Выбираем ребро идущее из вершины 2 с наименьшим весом – 7(ребро ведущее к вершине 1).

Граф имеет кратчайший остов равный 116.

 

 

Задание 4.

В заданном означенном графе построить дерево кратчайших путей из отмеченной вершины (алгоритм Дейкстры).

Решение:

1: Выберем начальную вершину – 1, присваиваем метку =0

 

2: Определяем  смежные вершины для 1 – 7,2

Пересчитываем временные метки:

7 – 0+5=5

2 – 0+7=7

Вершине 7 присваиваем постоянную метку = 5, вершине 2 присваиваем постоянную метку = 7

 

2: Определяем  смежные вершины для 7 – 6,4,8

Пересчитываем временные метки:

6 – 5+5=10

8 – 5+5=10

4 – 10+5=15

Вершине 8 присваиваем постоянную метку = 10

 

3: Определяем  смежные вершины для 8 – 6,10,3

Пересчитываем временные метки:

6 – 12+10=10 (оставляем  старое значение)

10 – 12+8=20

3 – 12+9=21

Вершине 6 присваиваем  постоянную метку = 10

 

4: Определяем  смежные вершины для 6 – 9,5

Пересчитываем временные метки:

5 – 3+10=13

9 – 10+10=20

Вершине 5 присваиваем  постоянную метку = 13

 

5: Определяем  смежные вершины для 5 – 4

Пересчитываем временные метки:

4 – 7+13=15 (оставляем старое значение)

Вершине 4 присваиваем постоянную метку = 15

 

6: Определяем  смежные вершины для 4 – 11,3

Пересчитываем временные метки:

11– 3+15=18

3 – 10+15=21 (оставляем старое значение)

Вершине 11 присваиваем постоянную метку = 18

 

7: Определяем  смежные вершины для 11 – 10

Пересчитываем временные метки:

10– 5+18=22 (оставляем старое значение)

Вершине 10 присваиваем постоянную метку = 20

 

8: Определяем  смежные вершины для 10 – 9,3

Пересчитываем временные  метки:

9 – 7+20=20 (оставляем старое значение)

3 – 4+20=21 (оставляем старое значение)

Вершине 9 присваиваем  постоянную метку = 20, вершине 9 присваиваем постоянную метку = 20

 

6: Определяем  смежные вершины для 2 – 3

Пересчитываем временные метки:

3 – 7+8=15

Вершине 3 присваиваем  постоянную метку = 15

 

Дерево кратчайших путей построено:

1	2	3	4	5	6	7	8	9	10	11
0	7	15	15	13	10	5	10	20	20	18

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 6.

С помощью алгоритма  последовательного раскрашивания  провести приемлемую  правильную вершинную  раскраску заданного графа.

 

Решение:

Раскраску графа начнем из вершины 1

Вершине 1 присваивается  цвет 1.

Проверяем смежные  вершины  2,7. Вершине 7 присваивается 2 цвет, 2 – 3 цвет.

Проверяем вершины  смежные вершине 7 – 4,6,8 Присваиваем  вершинам 4,8 - 1 цвет, 6 – 3 цвет.

Проверяем вершины  смежные вершине 6 – 5,9 Присваиваем вершинам 5,9 - 2 цвет.

Проверяем вершины  смежные вершине 9 – 10 Присваиваем  вершине 10 - 3 цвет.

Проверяем вершины  смежные вершине 10 – 3,11 Присваиваем  вершинам  3,11 - 2 цвет.

Задание 7.

Написать краткий  реферат  по алгоритмам укладки графа на плоскость.

Гамма-алгоритм

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

Итак, на вход подаются графы, обладающие следующими свойствами:

1. граф связный; 

2. граф имеет  хотя бы один цикл;

3. граф не  имеет мостов, т. е. ребер, после удаления которых, граф распадается на две компоненты связности.

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

Если нарушено свойство (2), то граф — дерево и нарисовать его плоскую укладку тривиально.

Случай нарушения  свойства (3) рассмотрим более подробно. Если в графе есть мосты, то их нужно  разрезать, провести отдельно плоскую  укладку каждой компоненты связности, а затем соединить их мостами. Здесь может возникнуть трудность: в процессе укладки концевые вершины моста могут оказаться внутри плоского графа. Нарисуем одну компоненту связности, и будем присоединять к ней другие последовательно. Каждую новую компоненту связности будем рисовать в той грани, в которой лежит концевая вершина соответствующего моста. Так как граф связности мостами компонент связности является деревом, мы сумеем получить плоскую укладку.

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

Изложим алгоритм на конкретном примере. Пусть дан  граф G (см. рис. 4).

 

 

 

 

 

Рис. 4

 

Первый шаг - инициализация алгоритма: выбираем любой простой цикл в G, пусть это будет {1, 2, 3, 4, 5, 6}, укладываем его на плоскости, и получаем две грани: Г1 — внешнюю и Г2 — внутреннюю (см. рис. 5).

 

 

 

 

 

 

 

Рис. 5

Уже уложенную  часть исходного графа будем  обозначать как G, тогда после первого  шага G представляет собой цикл {1, 2, 3, 4, 5, 6}.

На каждом шаге будем строить  множество сегментов. Каждый сегмент S относительно уже построенного графа G. представляет собой одно из двух:

• ребро, оба  конца которого принадлежат G., но само оно не принадлежит G;

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

Вершины, которые одновременно принадлежат G. и какому-то сегменту, назовем контактными вершинами. Для нашего примера сегменты изображены на рис. 6. Контактные вершины обведены в квадрат.

 

 

 

Рис. 6

 

 

 

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

Если все контактные вершины  сегмента S имеют номера вершин какой-то грани Г, то мы будем говорить, что грань Г вмещает этот сегмент, в этом случае будем использовать следующее обозначение: S Г. Однако, может быть так, что не одна грань вмещает в себя сегмент S, а несколько. Множество таких граней обозначим Г(S), а их число |Г(S)|.

Общий шаг алгоритма  следующий: выделяются все сегменты Si и определяются числа |Г(Si)|. Если хоть одно из них равно 0, то граф не планарен, конец. Иначе, выбираем сегмент, для которого число |Г(S)| минимально, или любой из них, если таких сегментов несколько. В этом сегменте найдем произвольную цепь между двумя контактными вершинами и уложим ее в любую из граней множества Г(S). При этом данная грань разобьется на две. Уже уложенная часть графа G’ после укладки цепи увеличится, а сегмент, из которого вынута цепь, исчезнет или развалится на

меньшие с новыми контактными вершинами, ведущими к  вершинам G.

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

Вернемся к  нашему примеру. Пока для любого i: Si {Г1, Г2}, |Г(Si)| = 2. Поэтому возьмем первый по номеру сегмент Si и в нем цепь {1, 4}; вставим эту цепь в грань Г2. После укладки цепи G’ увеличится и произойдут изменения в структуре сегментов (см. рис. 7 a, b).

 

 

 

 

 

 

 

Рис. 7

Определим, какие  грани вмещают новые сегменты. Теперь сегменты S1 и S3 можно уложить  только в одну грань Г1, в то время  как сегменты S2 и S4 можно уложить в две грани (для S2 это грани Г1 и Г2, для S4 - Г1 и Г3). Поэтому берем S1. Возьмем в нем цепь {2, 5} и уложим ее в Г1. Получим увеличенный граф G. и уменьшенную систему сегментов (см. рис. 8 a, b).

 

 

 

 

 

 

 

 

Рис. 8

 

Продолжая таким  образом, в итоге получим плоскую укладку исходного графа G (см. рис. 9).

 

 

 

 

 

 

 

Рис. 9

 

 

Гамма-алгоритм:

1. Инициализация.  Выберем любой простой цикл C исходного  графа G; изобразим его на плоскости  в виде грани, которую примем  за уже уложенную часть G.; сформируем сегменты Si; если множество сегментов пусто, то перейти к п. 3. В противном случае перейти к п.2.

2. Общий шаг: 

a. Для каждого  сегмента S найти множество Г(S). Если  существует сегмент S, для которого |Г(S)| = 0, то граф не планарный,  конец. 

b. Выбираем один из сегментов с минимальным числом, вмещающих его граней.