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

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

Прочитайте:
  1. Доказательство
  2. Доказательство
  3. Доказательство
  4. Доказательство
  5. Доказательство
  6. Доказательство
  7. Доказательство
  8. Доказательство
  9. Доказательство

Необходимость. () Пусть 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-09-27 | Просмотры: 476 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.002 сек.)