Ответы, указания и решения

• 1. Любая компонента связности однородного кубического графа G также является однородным графом третьей степени. Рассмотрим некоторую компоненту связности G; и предположим, что в ней не содержится цикла. Тогда G) — это связный граф без циклов, т. е. — дерево. По лемме о висячей вершине в графе Gi существует вершина степени 1. Мы пришли к противоречию с тем, что все вершины графа имеют степень 3. Следовательно, в графе G/ (и в исходном графе G) содержится цикл.
• 2. По условию задачи граф дорог в государстве является деревом, содержащим 201 вершину. Следовательно, он содержит 200 ребер.
• 3. Граф G волейбольной сетки имеет I v! —51 -601 =30 651 вершин и / El =51 -600+50−601 = 60 650 ребер. Мы можем удалять ребра в этом графе до тех пор, пока он не превратится в дерево С/ (одно из покрывающих деревьев исходного графа). Дерево G/ имеет IV/I =1 Vl =30 651 вершин и /Eil =1 V/l-1 =30 650 ребер. Следовательно, необходимо удалить IeI-IEjI= 60 650- 30 650=30000 ребер.
• 5. Эта задача так же, как и предыдущая, решается методом выделения покрывающего дерева. Для исходного графа

можно записать: / W =и, / El = С] = ——. Для.

покрывающего дерева имеем: / V_tl =1 Vl =п, IEj =п-1.

6. Если исходный граф является деревом, то он имеет висячую вершину. После удаления этой вершины вместе с инцидентным ей ребром получим искомый связный подграф. В случае, если исходный граф G не является деревом, то можно выделить в нем любое покрывающее дерево G/. Пусть А — висячая вершина дерева G/. Удалим из графа G вершину А вместе со всеми инцидентными ей ребрами. В результате этой операции получим искомый связный подграф графа G.

Итак, необходимо удалить / El -I EJ = —— -(п-1) =

= = ребе,.

• 5. Граф дорог в государстве является полным графом с 30 вершинами. Используя задачу 4, получаем, что можно закрыть на ремонт = 406 дорог.
• 7. Перечислим все возможные типы деревьев с 6 вершинами. Каждое такое дерево имеет 5 ребер, а сумма степеней всех 6 вершин равна 10 (удвоенному числу ребер). При нахождении 6 возможных степеней, дающих в сумме 10, возникают следующие случаи:
  • • 1+1+1+1+1+5. Этому случаю соответствует

единственный тип графа (см. рис. 40а);

• • 1+1+1+1+2+4. Этому набору степеней соответствует также единственный тип графа (см. рис. 406);
• • 1+1+1 + 1+3+3. В этом случае снова приходим к единственному типу графа (см. рис. 40в);
• • 1+1 + 1+2+2+3. Этой ситуации соответствует два типа неизоморфных графов (см. рис. 40 г и 406);
• • 1 + 1+2+2+2+2. Для такого набора степеней существует единственный граф (см. рис. 40с).

Так как по условию заданы 7 деревьев с 6 вершинами, а всего существует 6 неизоморфных типов таких деревьев, то по принципу Дирихле хотя бы 2 из 7 исходных деревьев будут изоморфны.

• 8. Рассмотрим висячую вершину дерева и обозначим ее через Л. Так как а (А₀)=], то Aq имеет смежную вершину, которую мы обозначим через А/. Для вершины А/ сг (Л/)> 1. Если a (Aj)=], то Aj — искомая вторая висячая вершина. Если о (А/)>/, то вершина А/ имеет смежную вершину, отличную от А₀ которую мы обозначим через А₂. Продолжая далее этот процесс, мы получим последовательность различных вершин (так как дерево не имеет циклов). Если бы дерево не содержало второй висячей вершины, то описанный процесс никогда бы не закончился и мы получили бы бесконечную последовательность А₀, А_], Л₂,… различных вершин. Но так как дерево является конечным графом, то описанный процесс будет конечным, и на каком-то шаге мы придем ко второй висячей вершине
• 9. Всего насчиз ывается 23 типа неизоморфных деревьев с 8 вершинами.
• 10. Выберем в дереве некоторую висячую вершину и обозначим ее Ао. Будем говорить, что вершина В удалена от вершины А₀ на расстояние р, где peN, если кратчайший путь, соединяющий А₀ и В, состоит из р ребер. Легко показать, что если разбить все вершины дерева на два подмножества, в одном из которых будут находиться вершины, удаленные от А₀ на четное расстояние, а в другом — вершины, удаленные от А₀ на нечетные расстояния, то получим двудольный граф.

Полный двудольный граф является деревом лишь в том случае, если в одной из его «долей» содержится всего одна вершина. Например, дерево, изображенное на рис. 41, является полным Рис. 41 двудольным графом.