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

Доказательство. Возьмем произвольную циклическую последовательность (1), состоящую из всех вершин графа G(рис

Возьмем произвольную циклическую последовательность (1), состоящую из всех вершин графа G (рис. 5.21).

a ₁ a ₂ ... a_n (1)

Рис. 5.21

Будем говорить, что в последовательности (1) имеется разрыв между вершинами a_i и a_{i+ 1}, если (a_i, a_i+1) Ï U, т.е. если эти вершины не соединяет ребро.

Понятно, что в последовательности (1) может иметься лишь конечное число разрывов.

Покажем, что эту последовательность можно преобразовать в такую циклическую последовательность, которая не содержит разрывов и, следовательно, является циклом Гамильтона в G.

Последнее утверждение является верным, если в (1) нет разрывов.

Предположим, что в (1) имеются разрывы.

Без ограничения общности можно считать, что в (1) имеется разрыв между вершинами a ₁и a ₂. В противном случае следует по-другому определить начало этой циклической последовательности.

Покажем, что среди остальных вершин последовательности (1) найдутся такие две последовательно идущие вершины a_i и a_{i+ 1}, что (a ₁, a_i) U и (a ₂, a_{i+ 1}) U.

Так как вершины a ₁ и a ₂ не являются соседними, то вершины, соседние с a ₁ или a _2, содержатся среди n - 2 вершин последовательности:

Предположим, что в (2) нет двух последовательно идущих

вершин, первая из которых является соседней с a ₁, а вторая - соседней с a ₂.

В последовательности (2) содержится не менее чем
d (a ₁) - 1 вершин, не соседних с a ₂. Это следует из того, что после всякой вершины в (2), соседней с вершиной a ₁, следует вершина, которая не является соседней с a ₂.

Среди элементов последовательности (2), отличных от a_n, содержится не менее чем d (a ₁) - 1 вершин, соседних с a ₁ и после каждой такой вершины расположена вершина, не соседняя с вершиной a ₂.

Поскольку вершины a ₁ и a ₂ также не являются соседними с вершиной a ₂, то общее число вершин графа G, не соседних с a ₂, не менее d (a ₁) + 1.

Всякая вершина в G либо является соседней с a ₂ либо не является соседней с a ₂. Поэтому общее число вершин графа G должно удовлетворять неравенству

n d (a ₁) + d (a ₂) + 1.

Последнее неравенство противоречит условиям теоремы, из которых следует, что d (a ₁) + d (a ₂) ³ n.

Следовательно, в последовательности (1) имеется пара соседних вершин a_i и a_{i+ 1}, для которых (a ₁, a_i) U и (a₂, a _{i+ 1}) U.

Воспользуемся доказанным свойством вершин a ₁ и a₂ и переставим вершины в (1) так, как это указано на рис. 5.22.:

a ₁ a _{2 ..} a_i a_{i + 1} ... a_n (3)

Рис. 5.22

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

Будем повторять описанное преобразование до тех пор, пока в получаемых циклических последовательностях имеются разрывы.

Через конечное число шагов из последовательности (1) будет получена циклическая последовательность вершин, не содержащая разрывов. Она образует цикл Гамильтона в графе G.

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