Контрольная работа по дискретной математике

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

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

Вариант № 21

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

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

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

Волгоград 2010

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

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

Решение:

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

Множество вершин: X={x1, x2, x3, x4, x5}

Множество связей: V={<x1 x2>, <x1 x3>, <x2 x4>, <x3 x4>, <x3 x5>}

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

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

	V1	V2	V3	V4	V5
X1	1	1	0	0	0
X2	-1	0	0	0	1
X3	0	-1	1	1	0
X4	0	0	0	-1	-1
X5	0	0	-1	0	0

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

	X1	X2	X3	X4	X5
X1	0	1	1	0	0
X2	0	0	0	1	0
X3	0	0	0	1	1
X4	0	0	0	0	0
X5	0	0	0	0	0

Задание 2.

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

число ребер и дуг;
число вершин;
коэффициент связности графа;
степени всех вершин;
цикломатическое число графа.

Решение:

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

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

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

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

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

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

Задание №3.

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

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

Решение:

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

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

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

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

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

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

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

Решение:

Подграф:

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

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

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

Решение:

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

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

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

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

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

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

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

Решение:

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

	X1	X2	X3	X4	X5
X1	0	1	1	0	0
X2	0	0	0	1	0
X3	0	0	0	1	1
X4	0	0	0	0	0
X5	0	0	0	0	0

1	2	1	2	0	0
2	0	0	0	*	*

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

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

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

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

Решение:

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

d(x1,x2) = 1

d(x1,x3) = 1 d(x2,x3) = 2

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

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

2. Определим диаметр как d(G) = max d(xi, xj): d(G)=3

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

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

4. Определим радиус графа как r(G) = min r(xi): r(G) = 2

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

Уровни

Контрольная работа по дискретной математике