5304.Учебная работа .Тема:Графы: основные понятия и определения

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (4 оценок, среднее: 4,75 из 5)
Загрузка...

Тема:Графы: основные понятия и определения»,»

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

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

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

по дискретной математике

Вариант №21

Выполнил: студент группы

АУЗ 161с Тюляева И.А.

Проверил: Акулов Л.Г.

Волгоград 2010

Дано вариант №21:

Задание 1

Задать граф следующими способами: перечислением, матрицами смежности и инцидентности.

Решение:

Способ перечисления:

Множество вершин:

={x1, x2, x3, x4, x5}

Множество связей:

={<x1 x2>, <x1 x3>, <x2 x4>, <x3 x4>, <x3 x5>}

Множество изолированных вершин: пусто.

Матрица инцидентности:

V1V2V3V4V5X111000X210001X301110X400011X500100

Матрица смежности:

X1X2X3X4X5X101100X200010X300011X400000X500000

Задание 2

Определить следующие основные характеристики графа:

число ребер и дуг;

число вершин;

коэффициент связности графа;

степени всех вершин;

цикломатическое число графа.

Решение:

Число ребер 0. Число дуг 5.

Число вершин 5.

Коэффициент связности графа 1.

Степени всех вершин:

Х1Х2Х3Х4Х5Полустепень исхода21200Полустепень захода01121Степень22320

Цикломатическое число графа = (число связей число вершин) + коэффициент связности.

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

55+1=1;

цикломатическое число равно 1.

Задание №3

Определить, является ли данный граф:

планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);

двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);

деревом (обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева);

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

Решение:

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

Данный граф не является двудольным, т.к. имеет циклы нечетной длины. Преобразуем данный граф в двудольный путем добавление новой вершины X6, новой связи V6 и переносом связи V4 в другое положение:

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

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

Преобразуем данный граф в мультиграф:

Преобразуем данный граф в псевдограф:

Задание 4

Привести пример подграфа, частичного графа и частичного подграфа.

Решение:

Подграф:

Частичный подграф:

Частичный граф:

Задание 5

Произвести реберную и вершинную раскраски графа с определением вершинного и реберного хроматического числа.

Решение:

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

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

Вершинная раскраска:

Хроматическое число равно 2

Реберная раскраска:

Хроматическое число равно 3

Задание 6

Упорядочить граф матричным способом и построить порядковую функцию, функцию Гранди.

Решение:

В основе алгоритма упорядочивания лежит матрица смежности.

X1X2X3X4X5X101100X200010X300011X400000X500000Таблица

L121200L2000**

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

Функция Гранди:

Порядковая функция:

Задание 7

Определить метрические характеристики графа: диаметр, радиус, эксцентриситет каждой вершины, центральные вершины.

Решение:

. Определим расстояния между парами вершин:

(x1,x2) = 1(x1,x3) = 1 d(x2,x3) = 2(x1,x4) = 2 d(x2,x4) = 1 d(x3,x4) = 1(x1,x5) = 2 d(x2,x5) = 3 d(x3,x5) = 1 d(x4,x5) = 2

. Определим диаметр как

d(G) = max d(xi, xj): d(G)=3

. Определим эксцентриситет каждой вершины:

r(x1) = 2 r(x2) = 3 r(x3) = 2 r(x4) = 2 r(x5) = 3

. Определим радиус графа как

r(G) = min r(xi): r(G) = 2

граф функция диаметр матричный

5. Определим центральные вершины: x1, x3, x4.