АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Необходимость. () Пусть G имеет цикл Эйлера и С - это некоторый такой цикл в G.

1. Всякое прохождение внутренней вершины цикла С использует ровно два ребра, выходящих из этой вершины.

2. Первое и последнее рёбра, проходимые при движении по циклу, образуют еще одну пару ребер, инцидентные такой вершине цикла, которая является начальной и заключительной одновременно.

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

Достаточность. ()

Покажем, что всякий четный граф G = (V, U) имеет цикл Эйлера.

Если G содержит единственную вершину, то доказываемое утверждение очевидно, поскольку такой граф не имеет ребер и единственный цикл Эйлера в нем - это цикл длины 0.

Рассмотрим случай, когда G имеет хотя бы одно ребро.

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

Пусть v ₁ - это некоторая вершина из V. Возьмем произвольное ребро (v ₁, v ₂), выходящее из v ₁, и перейдем по нему в вершину v ₂.

Поскольку степень v ₂ является четной, то из этой вершины выходит еще хотя бы одно ребро. Возьмем любое такое ребро (v ₂, v ₃) и продолжим движение в графе G.

Движение по G продолжаем до тех пор, пока очередное выбранное ребро не приведет в одну из уже пройденных вершин. Выделим вершину, которая встретилась второй раз.

Поскольку множество вершин в G является конечным, то описанный процесс закончится за конечное число шагов.

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

2. Покажем, что в G имеется цикл Эйлера.

Докажем это индукцией по числу k ребер в графе G.

Дата добавления: 2015-09-27 | Просмотры: 434 | Нарушение авторских прав