Задача 6:

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

Решение:

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

Задача 7:

Докажите, что в дереве любые две вершины соединены ровно одним простым путем.

Решение:

Предположим противное и рассмотрим те две вершины, которые соединены двумя разными простыми путями. На первый взгляд кажется, что пройдя от одной вершины к другой по первому пути, и вернувшись по второму, мы получим цикл. К сожалению, это не совсем так. Дело в том, что первый и второй пути могут иметь общие вершины (кроме начала и конца), а по определению цикла вершины в нем не должны повторяться. Для того, чтобы выделить настоящий цикл из уже полученного нужно сделать следующее:

1) выбрать первую точку, в которой пути расходятся

2) за выбранной точкой на пути 1 найти первую точку, принадлежащую также и пути 2

Теперь участки первого и второго пути между точками A и B образуют простой цикл.

Задача 8:

Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).

Решение:

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

Задача 9:

В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.

Решение:

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

Задача 10:

Докажите, что при удалении любого ребра из дерева оно превращается в несвязный граф.

Решение:

Предположим, что концы удаленного ребра в новом графе соединены простым путем. Тогда этот путь вместе с удаленным ребром образует в исходном графе цикл.

Задача 11:

В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?

Решение:

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

Задача 12:

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

Решение:

Если нет, то удалением нескольких ребер из него можно получить дерево.

Задача 13:

Волейбольная сетка имеет вид прямоугольника размером 50 × 600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?

Решение:

Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами – веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Будем убирать ребра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число ребер в нашем графе в этот момент. Количество вершин осталось тем же – 51 • 601 = 30651. Число ребер в дереве на 1 меньше числа вершин и, следовательно, в нашем дереве будет 30650 ребер. Сначала же их было 601 • 50 + 600 • 51 = 60650. Таким образом, можно удалить 30000 ребер, то есть у волейбольной сетки можно перерезать 30000 веревочек (но не более!).

Задача 14:

В некоторой стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый?

Решение:

Ответ: 30 • 29/2 – 29 = 406.

Задача 15:

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

Решение:

Выделите максимальное дерево и удалите его висячую вершину.

Задача 16:

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более а) 198 перелетов; б) 196 перелетов.

Решение:

а), б) Рассмотрите «максимальное» дерево и выберите путь, соединяющий две висячие вершины.