Методы обхода графа

Задачи

3.1. Сколько ребер в лесе с n вершинами и k компонентами связности?

3.2. Сколько ребер в графе с n вершинами, если в нем имеется единственный цикл?

3.3. Перечислите все абстрактные деревья с 6 (7) вершинами.

3.4. В дереве имеется 40 вершин степени 4, все остальные вершины – листья. Сколько

листьев в этом дереве?

3.5. В дереве имеется ровно три листа , причем , ,

. Сколько всего вершин в этом дереве?

3.6. Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр

этого дерева?

3.7. Постройте код Прюфера для дерева, изображенного на рисунке.

3.8. Восстановите дерево по коду Прюфера (4, 1, 6, 2, 2, 2, 7, 6).

3.9. Сколько имеется помеченных корневых деревьев с n вершинами?

3.10. Сколько различных (помеченных) каркасов у графа ?

3.11. Сколько попарно неизоморфных каркасов у графа ?

3.12. С помощью теоремы Кирхгофа найдите число каркасов у графа .

3.13. Найдите два неизоморфных дерева с одинаковыми наборами степеней вершин.

3.14. Найдите дерево с наименьшим числом вершин, не имеющее нетривиальных

автоморфизмов.

3.15. Постройте канонический код дерева из задачи 3.8, взяв в качестве корня вершину 2.

3. 16. Восстановите дерево по каноническому коду .

3.17. Какие из следующих графов являются двудольными: 1) ; 2); 3) ;

4) ?

3.18. Сколько различных абстрактных двудольных графов можно получить, добавляя одно

ребро к графу а) ; б) ; в) ?

3.19. Какое наименьшее число ребер нужно удалить из графа , чтобы получился

двудольный граф?

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

разбить на две доли?

3.21. При каких значениях k граф является двудольным?

3.22. Какие из следующих графов планарны: 1) ; 2); 3); 4) ?

3.23. Какое наибольшее число граней может быть у плоского графа с 5 вершинами?

3.24. Какое наименьшее число ребер нужно удалить из графа , чтобы получился

планарный граф?

3.25.Какое наименьшее количество новых ребер нужно добавить к графу , чтобы

получился непланарный граф?

3.26. При каких значениях k граф является планарным?

3.27. Примените алгоритм распознавания планарности а) к графу из задачи 1.2; б) к графу

.

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

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

Очередной шаг обхода начинается с выбора какой-либо вершины из множества открытых, она становится активной. Если в окрестности активной вершины есть неисследованные вершины (вершина могла уже быть активной раньше и ее окрестность может быть частично исследована), то выбирается такая вершина . Если новая, то она посещается, ребро при этом классифицируется как прямое. Если же не новая, то ребро считается обратным (ведущим в уже посещенную вершину). Если все вершины из окрестности активной вершины уже исследованы, она становится закрытой. Эти действия повторяются до тех пор, пока множество открытых вершин не станет пустым. Если при этом еще остались новые вершины, то выбирается и посещается одна из таких вершин и процесс повторяется.

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

Основное различие между поиском в ширину и поиском в глубину состоит в том, как выбирается активная вершина.