Билет 33

Покрытие рёбер графа путями

Следующее утверждение являются следствием из критерия Эйлеровости графа:

Теорема:

Пусть — граф, в котором вершин имеют нечётную степень. Тогда множество рёбер можно покрыть

рёберно-простыми путями.

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

Необходимость

Докажем, что можно покрыть рёберно-простыми путями.

Добавим рёбер таких, что степени вершин и нечётные. Тогда степени всех вершин станут чётными, и в

появится Эйлеров цикл (критерием Эйлеровости графа является отсутствие нечётных вершин в связном мультиграфе).

Удалим из добавленные рёбра. Заметим, что теперь цикл распадается на простых путей. В самом деле: возьмем Эйлеров

цикл и удалим из него рёбер. Теперь полученный граф можно разбить на (или меньше) цепей между этими удалёнными

рёбрами.

Достаточность

Докажем, что нельзя покрыть менее, чем рёберно-простыми путями.

Предположим, что такое возможно, и существует набор рёберно-простых путей , такой что он

покрывает все рёбра . Пусть й путь из этого набора имеет вид . Добавим в все рёбра

вида (соединяют конец предыдущей и начало следующей цепи) и ребро (соединяет конец последней и

начало первой цепей).

В новом графе появится Эйлеров цикл, т.к. мы добавили рёбра, соединяющие конец и начало и пути соответственно.

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

нечётной степени, что не удовлетворяет критерию Эйлеровости графа.

Противоречие. Значит, такого набора, что его мощность меньше , не существует.

Критерий эйлеровости

Теорема:

Для того, чтобы граф был эйлеровым необходимо чтобы:

1. Все вершины имели четную степень.

2. Все компоненты связности кроме, может быть одной, не содержали ребер.

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

1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в

вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является

стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода

эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение

неверно.

2. Если в графе существует более одной компоненты связности с ребрами, то очевидно, что нельзя пройти по их ребрам одним

путем.

Алгоритм напоминает поиск в ширину. Главное отличие состоит в том, что пройденными помечаются не вершины, а ребра графа. Начиная со стартовой вершины v строим путь, добавляя на каждом шаге не пройденное еще ребро, смежное с текущей вершиной. Вершины пути накапливаются в стеке S. Когда наступает такой момент, что для текущей вершины w все инцидентные ей ребра уже пройдены, записываем вершины из S в ответ, пока не встретим вершину, которой инцидентны не пройденные еще ребра. Далее продолжаем обход по не посещенным ребрам.