Вопросы для самопроверки

1. Что такое ориентированный граф (орграф)?

2. Чем различаются свойства инцидентности и смежности в графе?

3. Что собой представляет положительная полустепень вершины орграфа?

4. О чем говорит лемма о рукопожатиях?

5. Что обозначают элементы матрицы смежности вершин орграфа и неориентированного графа?

6. Что обозначают элементы матрицы инцидентности орграфа и неориентированного графа?

7. Что такое изоморфизм графов?

8. Перечислите локальные операции над графами

9. Объясните операцию пересечения графов и прямого произведения графов.

10. Объясните, что означают маршрут, цепь, цикл в неориентированном графе.

11. Что описывает матрица расстояний в графе?

12. Чем отличается радиус графа от диаметра?

13. Что такое бикомпонента?

14. Дайте определение шарниру и мосту.

15. Что такое конденсация графа?

16. Дайте определение полуэйлерова графа.

17. Опишите алгоритм Флери.

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

19. Дайте определение дерева.

20. Что такое корневое дерево?

21. Как может быть найдено число остовов графа?

22. Теорема о числе рёбер неориентированного графа, которые необходимо удалить для получения остова.

23. Что такое взвешенный граф?

24. Опишите алгоритм Краскаля.

25. Расскажите о нахождении кратчайших путей с помощью алгоритма Дейкстры.

26. Что такое хроматическое число графа?

27. Как максимально независимые системы вершин связаны с раскраской графа?

Задачи по теме «Теория графов»

Задача 1. Чему равны степени вершин графа?

v₄

Ответ: степени вершин графа: , , , (если считать вклад в степень вершины петли равным двум).

З адача 2. Для неориентированного графа, изображенного на рис. 52, постройте матрицу смежности А и матрицу инцидентности B.

Ответ: , .

Задача 3. Сравнить графы и указать, являются ли они дополнениями друг для друга?

Ответ: да.

Задача 4. Доказать, что в полном графе с п вершинами присутствует ребер.

Решение. Каждой вершине в полном графе с п вершинами принадлежит ребро, но в произведении каждое ребро учтено дважды (так как одно ребро инцидентно двум вершинам). Следовательно, число ребер в полном графе с вершинами равно .

Задача 5. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с остальными по одному разу). Покажите, что в любой момент времени найдутся два шахматиста, сыгравшие одинаковое число партий.

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

Каждая вершина графа с девятью вершинами может иметь степень 0, 1, 2, 3, 4, 5, 6, 7, 8. Предположим, что существует граф G, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, 3, 4, 5, 6, 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть, так как если в графе есть вершина степени 0, то в нем найдется вершина со степенью 8. Эта вершина и, должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с , поэтому степень вершины не может равняться 0. Таким образом, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой. Таким образом, доказано, что в любой момент найдутся хотя бы два шахматиста, сыгравшие одинаковое число партий.

Задача 6. Найти число бикомпонент орграфа (рис. 54)

Ответ: три.

Задача 7. Для графа, изображенного на рис. 55, построить конденсацию.

Ответ:

Задача 8. Построить остовы для графа, изображенного на рис. 57.

Задача 9. Построить с помощью алгоритма Флери эйлеров цикл для графа, изображенного на рис. 58.

Задача 10. Найти хроматическое число графа на рис. 59.

Ответ: пять.