Задание 6.1. Нарисуйте граф с семью вершинами и шестью ребрами, не имеющий ни одного цикла.
Задание 6.2. Нарисуйте связный граф с семью вершинами и шестью ребрами.
Задание 6.3. Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь.
Все предлагаемые решения выносим на доску, обсуждая каждый предложенный ребятами вариант.
Рассмотрим внимательно рисунки, которые строили при ре­шении этих заданий. Что характерно для всех построенных графов? Во-первых, они связные; во-вторых, они не содержат цик­лов. Такие графы выделяются в отдельный класс, представители которого именуются деревьями.
                                                 
                                                                 Рис 36
Деревом называется всякий связный граф, не имеющий циклов (рис. 36).
Будем считать, что граф, состоящий из одной изолирован­ной вершины, тоже является деревом.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 36 висячие вершины выделенызакрашенными кружками).
                                             
                                                              Рис. 37
Лесом называется несвязный граф, представляющий объединение деревьев (рис. 37).
Задача 6.1.
В парке "Лотос" невозможно найти такой маршрут для прогулок по
его дорожкам, который начинается и оканчивается в одной и той же точке и каждую дорожку парка содержит не более раза. Докажите, что некоторые дорожки парка приводят в тупик.
Решение.
Построим граф G, в котором вершины соответствуют перекресткам и тупикам парка, а ребра — его дорожкам.
По условию задачи в графе Gнет циклов, и он является деревом. Существование тупиков в парке эквивалентно существованию висячих вершин в построенном дереве.
Предложение 2. В любом дереве есть висячая вершина. Предположим противное. Рассмотрим произвольную вершину v1 и перейдем из нее по любому ребру в вершину v2. Поскольку степень вершины v2не меньше двух, то из нее по новому ребру можно перейти в вершину v3 и так далее. Но число вершин в графе G конечно. Поэтому, в конце концов, мы приедем в одну из тех вершин, в которых были раньше (см. рис. 38).

                             Рис. 38
Это означает существование цикла в дереве G, что противоречит условию. Следовательно, в графе есть висячая вершина. Эта вершина будет соответствовать тупику в парке.
Задача 6.2.
Администрация парка "Лотос" (см. предыдущую задачу) решила про­
вести реконструкцию освещения парка. По новому проекту каждый
перекресток и тупик, должен будет освещаться четырьмя светильника­ми, а аллея, соединяющая два перекрестка или перекресток и тупик – шестью. Сколько светильников будет установлено, если в парке 18 перекрестков и тупиков.
Решение.
В предыдущей задаче мы установили, что граф G, описываю­щий перекрестки, тупики и аллеи парка "Лотос" является деревом. Най­дем соотношение между числом вершин и ребер любого дерева. Каждое дерево имеет висячую вершину (см. предыдущую задачу). Удалим вися­чую вершину v0 из дерева Gвместе с ребром, выходящим из этой вер­шины. Полученный граф G1 будет связным, и в нем будут отсутствовать циклы, т.е. граф G1 – также дерево. Из графа G1, найдя и затем удалив висячую вершину v1 вместе с выходящим из нее ребром, можно получить дерево G2 и так далее. Выполнив такие операции, мы получим последо­вательность деревьев, которая оканчивается деревом, состоящим из од­ной вершины и не имеющим ребер. Для этого дерена выполняется соот­ношение: m = n – 1, где n – число вершин графа, а m – число его ребер. Теперь будем добавлять в обратном порядке ранее удаленные вершины и ребра. При каждом возвращении добавляется одна вершина и одно ребро, и для каждого получающегося графа соотношение m = n – 1 будет выпол­няться. Следовательно, мы доказали теорему 9: в любом дереве число ребер на единицу меньше числа вершин.

Поскольку в парке 18 перекрестков и тупиков, то дерево Gбудет иметь 18 вершин и 17 ребер. В парке необходимо установить 18*4 + 17*6 = 174 светильника.