Билет 34

Произвольно вычерчиваемые из заданной вершины графы

Определение:

Граф называется произвольно вычерчиваемым из вершины (англ. Arbitrarily traceable graph), если любая цепь с началом в

вершине может быть продолжена до эйлерового цикла графа .

Утверждение:

Любой произвольно вычерчиваемый из вершины граф является эйлеровым графом.

Теорема:

Эйлеров граф , содержащий хотя бы одно ребро, является произвольно вычерчиваемым из вершины вершина

принадлежит всем циклам графа .

Доказательство:

Пусть в цикл .

Рассмотрим (здесь и далее это означает удаление только ребер, не трогая вершины). При удалении цикла все

степени вершин остались четными, потому что каждая вершина содержит четное количество ребер цикла, и следовательно

— эйлеров. Тогда в эйлеров цикл. Если начать обход по эйлерову циклу из , то и закончится он в . Если теперь

вернуть цикл , то мы никак не сможем его обойти, так как из вершины больше нет не посещенных ребер не

свободно вычерчиваемый из .

Пусть дан эйлеров граф , вершина принадлежит всем его циклам.

Рассмотрим произвольный путь . Пусть . Возможны 2 случая:

11. Если , то — цикл, значит степени всех вершин в остались четными — эйлеров.

12. Если , то так как эйлеров граф эйлеров путь .

Покажем, что в обоих случаях эйлеров обход пройдет по всем ребрам .

В единственная компонента связности, содержащая ребра. При удалении их количество не могло увеличится, иначе

должен быть цикл, не содержащий (смотри рисунок). Значит в единственная компонента связности содержащая ребра,

причем либо полуэйлеров, либо эйлеров в эйлерова цепь эйлеров цикл в

графе .

Билет 35

Описание алгоритма

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

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

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

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