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

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

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

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

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

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

Вариант №21

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

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

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

Волгоград 2010

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

Задание 1

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

Решение:

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

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

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

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

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

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

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

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

Задание 2

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

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

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

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

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

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

Решение:

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

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

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

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

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

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

5-5+1=1;

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

Задание №3

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

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

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

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

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

Решение:

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

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

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

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

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

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

Задание 4

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

Решение:

Подграф:

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

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

Задание 5

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

Решение:

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

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

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

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

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

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

Задание 6

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

Решение:

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

Таблица

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

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

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

Задание 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.