Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





Дата публикования: 2015-03-29; Прочитано: 188 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.008 с)...