Таблицы Брадиса

База очевидна, докажем шаг индукции.

База очевидна, докажем шаг индукции.

Элементы математики в задачах - Г. А. Мерзон

Задача 15* (задача 17* из листка «Теория графов 1»). В полном неориентированном графе на ребрах как-то расставили стрелки. Докажите, что полученный граф гамильтонов (т. е. существует путь, проходящий по каждой вершине ровно по одному разу).

Решение. Доказательство проведем индукцией по числу вершин. База очевидна, докажем шаг индукции. Выбросим произвольную вершину А из графа, тогда в оставшемся графе есть гамильтонов путь из вер­шины с номером 1 в вершину с номером п — 1. Разберем несколько случаев. Если из вершины А идет стрелка в вершину 1, добавим ее в гамильтонов путь в начало, и все доказано. Если в вершину А идет стрелка из вершины п — 1, добавим ее в гамильтонов путь в конец, и снова все доказано.

Поэтому осталось рассмотреть случай, когда стрелки ведут из 1 в А и из А в п — 1. Заметим, что тогда обязательно найдется вершина с таким номером к (в гамильтоновом пути), что стрелка ведет из к в А и из А в к +1. Теперь нужно выкинуть из пути стрелку к ^ к + 1 и добавить стрелки к ^ А и А ^ к +1. Все случаи нами разобраны, шаг индукции доказан.

216                                    Теория графов 2

Задача 16*. В полном неориентированном графе с не менее чем тремя вершинами на ребрах как-то расставили стрелки. Докажите, что можно заменить не более одной дуги на противоположную так, чтобы полученный граф стал сильно связным.

Решение. Воспользуемся решением предыдущей задачи. Найдем в графе гамильтонов путь и рассмотрим в нем первую и последнюю вершины. Если стрелка ведет из последней в первую, то путь можно дополнить до цикла, а граф, в котором есть гамильтонов цикл, явля­ется сильно связным. Если же стрелка ведет из первой в последнюю, то заменим ее на противоположную.