07. Основные виды графов

Рассмотрим граф , Имеющий P вершин и Q ребер.

1. Пустой граф.

P Пустым называется граф, состоящий только из изолированных вершин.

В пустом графе , .

2. Тривиальный граф.

P Тривиальным называется граф, имеющий только одну вершину.

В тривиальном графе , .

3. Полный граф.

P Полным называется граф, каждая пара вершин которого является смежной.

Для обозначения полного графа используется специальный символ .

Например, на рис. 4 представлена диаграмма полного графа .

Рис. 4. Диаграмма полного графа

Из всех графов с P вершинами полный граф имеет наибольшее число ребер .

4. Двудольный граф.

P Двудольным называется граф, множество вершин которого разбивается на два Непересекающихся Подмножества V1 и V2 так, что Каждое ребро графа соединяет вершины из Разных подмножеств.

P Полным двудольным графом называется двудольный граф, в котором Каждая из M вершин множества V1 соединяется ребром с каждой из N вершин множества V2.

Например, граф задачи 4.6 является полным двудольным графом .

P Полный двудольный граф называется звездным или звездой.

Например, на рис. 5 представлена диаграмма звездного графа .

Рис. 5. Диаграмма звездного графа

5. Регулярный граф.

P Регулярным Степени K называется граф, все вершины которого имеют одну и ту же степень K.

Например, на рис. 6 представлена диаграмма графа Петерсена, который является регулярным графом третьей степени.

Рис. 6. Диаграмма графа Петерсена

6. Платонов граф.

P Платоновыми называются графы, образованные вершинами и ребрами пяти правильных многогранников – платоновых тел.

В табл. 1 приведены числовые характеристики правильных многогранников.

Таблица 1

Числовые характеристики правильных многогранников

Название

Многогранника

Число граней

Вид

Грани

Число вершин

Число ребер

Число ребер, примыкающих к одной

Вершине

Тетраэдр

4

Правильный треугольник

4

6

3

Гексаэдр

6

Квадрат

8

12

3

Октаэдр

8

Правильный треугольник

6

12

4

Додекаэдр

12

Правильный пятиугольник

20

30

3

Икосаэдр

20

Правильный треугольник

12

30

5

Например, на рис. 7 представлена диаграмма платонова графа для гексаэдра.

Рис. 7. Диаграмма платонова графа для гексаэдра

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

Например, на рис. 8 представлена диаграмма простого цикла с тремя вершинами .

Рис. 8. Диаграмма простого цикла

Задачи и упражнения

22. Постройте диаграмму пустого графа, имеющего 3 вершины.

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

24. Найдите в графе Петерсена циклы длиной 5 и 8. Вычислите цикломатическое число графа Петерсена.

25. Составьте матрицу смежности графа и укажите её характерную особенность.

26. Составьте матрицу смежности графа и укажите её характерную особенность.

27. Постройте диаграмму звездного графа .

28. Постройте платоновы графы для тетраэдра и октаэдра.

29. Всего в двух делегациях 20 человек. При встрече члены одной делегации обменялись рукопожатиями с членами другой. Найдите численный состав каждой делегации, если известно, что всего было сделано 96 рукопожатий.

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

© 2011-2024 Контрольные работы по математике и другим предметам!