Редактирование: Теорема Дирака

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
{{Лемма
 
{{Лемма
 
|about=о длине цикла
 
|about=о длине цикла
|statement= Пусть <tex>G</tex> {{---}} произвольный [[Основные определения теории графов#def_undirected_graph_1|неориентированный граф]] и <tex>\delta</tex> {{---}} минимальная [[Основные определения теории графов#def_graph_degree_1|степень]] его вершин. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует [[Основные определения теории графов#def_graph_cycle_1|цикл]] <tex>C</tex> длиной <tex>l \geqslant \delta + 1</tex>.
+
|statement= Пусть <tex>G</tex> - произвольный неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>\delta \ge 2</tex>, то в графе <tex>G</tex> существует цикл <tex>C</tex> длиной <tex>l \ge \delta + 1</tex>.
 
|proof=
 
|proof=
Рассмотрим путь максимальной длины <tex>P = v_0 v_1 \dots v_s</tex>. Все смежные с <tex>v_0</tex> вершины лежат на <tex>P</tex>. Обозначим <tex>k = \max \{i: v_0 v_i \in E\} </tex>. Тогда <tex>\delta \leqslant \deg v_0 \leqslant k</tex>. Цикл  <tex>C = v_0 v_1 \dots v_k v_0</tex> имеет длину <tex>l = k + 1 \geqslant \delta + 1</tex>
+
Рассмотрим путь максимальной длины <tex>P = v_0 v_1 .. v_s</tex>. Все смежные с <tex>v_0</tex> вершины лежат на <tex>P</tex>. Обозначим <tex>k = max\{i: v_0 v_i \in E\}</tex>. Тогда <tex>\delta \le deg\ v_0 \le k</tex>. Цикл  <tex>C = v_0 v_1 .. v_k v_0</tex> имеет длину <tex>l = k + 1 \ge \delta + 1</tex>
 
}}
 
}}
  
==Альтернативное доказательство==
+
==Теорема==
  
 
{{Теорема
 
{{Теорема
|about=Дирак {{---}} альтернативное доказательство
+
|about=Дирак
 
|statement=
 
|statement=
Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то  <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]].
+
Пусть <tex>G</tex> - неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>n \ge 3</tex> и <tex>\delta \ge n/2</tex>, то  <tex>G</tex> - [[Гамильтоновы графы|гамильтонов граф]].
 
|proof=
 
|proof=
Для <tex>\forall k</tex> верна импликация <tex>d_k \leqslant k < n/2 \Rightarrow d_{n-k} \geqslant n-k</tex>, поскольку левая её часть всегда ложна. Тогда по [[Теорема Хватала | теореме Хватала]] <tex>G</tex> {{---}} гамильтонов граф.
+
Пусть <tex>C</tex> - цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \ge \delta + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x..y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \ge n/2</tex>, а значит <tex>\delta \ge n - \delta > n - l = |V(G \backslash C)|</tex> и каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>.
 +
Заметим, что вершина <tex>x</tex> не может быть смежна:
 +
* с вершинами из <tex>C</tex>, расстояние от которых до <tex>y</tex> (по <tex>C</tex>) не превышает m. Действительно, пусть вершина <tex>v \in C</tex> и расстояние от <tex>v</tex> до <tex>y</tex> по циклу меньше либо равно <tex>m</tex>. Тогда этот участок цикла можно заменить на <tex>v \rightarrow x \rightarrow P \rightarrow y</tex>, длина которого <tex>m + 1</tex>. Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикл <tex>C</tex>.
 +
* двум смежным вершинам на <tex>C</tex>. Пусть <tex>u, v \in C</tex> и <tex>\{(u, v), (u, x), (x, v)\} \in E</tex>. Тогда заменив ребро <tex>(u, v)</tex> на <tex>u \rightarrow x \rightarrow v</tex>, увеличим длину цикла на <tex>1</tex>.
 +
* вершинам из <tex>G \backslash (C \cup P)</tex>, поскольку <tex>P</tex> максимальный.
 +
 
 +
Получаем <tex>deg\ x \le m + (l - 2m)/2 =l/2 < n/2 \le \delta</tex>. Противоречие.
 
}}
 
}}
 +
 +
==Альтернативное доказательство==
  
 
{{Теорема
 
{{Теорема
|about = Вывод из [[Теорема Оре|теоремы Оре]]
+
|about=Дирак {{---}} альтернативное доказательство
|statement =  
+
|statement=
Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то  <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]].
+
Пусть <tex>G</tex> - неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>n \ge 3</tex> и <tex>\delta \ge n/2</tex>, то  <tex>G</tex> - [[Гамильтоновы графы|гамильтонов граф]].
|proof =  
+
|proof=
Возьмем любые неравные вершины <tex> u, v \in G </tex>. Тогда <tex> \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n </tex>. По теореме Оре <tex> G </tex> {{---}} гамильтонов граф.
+
Для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>, поскольку левая её часть всегда ложна. Тогда по [[Теорема Хватала | теореме Хватала]] <tex>G</tex> - гамильтонов граф.
 
}}
 
}}
  
Строка 28: Строка 36:
 
* [[Гамильтоновы графы]]
 
* [[Гамильтоновы графы]]
 
* [[Теорема Хватала]]
 
* [[Теорема Хватала]]
* [[Теорема Оре]]
 
* [[Теорема Поша]]
 
 
== Источники информации ==
 
* [[wikipedia:en:Dirac's_Theorem|Wikipedia {{---}} Dirac's Theorem]]
 
* Graham, R.L., Groetschel M., and Lovász L., eds. (1996). ''Handbook of Combinatorics'', Volumes 1 and 2.  Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.
 
  
 +
== Источники ==
 +
Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: