Теорема Дирака — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |statement= Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math> для любой вершины <math>\ v</math> графа '''G''', т…»)
 
(бред написан какой-то)
(не показано 35 промежуточных версий 9 участников)
Строка 1: Строка 1:
 +
==Лемма о длине цикла==
 +
{{Лемма
 +
|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>.
 +
|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>
 +
}}
 +
 +
==Альтернативное доказательство==
 +
 
{{Теорема
 
{{Теорема
 +
|about=Дирак {{---}} альтернативное доказательство
 
|statement=
 
|statement=
−
Если <math>\ n > 3</math> и <math>deg\ v \ge n/2</math>  для любой вершины <math>\ v</math> графа  '''G''', то  '''G''' - гамильтонов граф
+
Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]].
 +
|proof=
 +
Для <tex>\forall k</tex> верна импликация <tex>d_k \leqslant k < n/2 \Rightarrow d_{n-k} \geqslant n-k</tex>, поскольку левая её часть всегда ложна. Тогда по [[Теорема Хватала | теореме Хватала]] <tex>G</tex> {{---}} гамильтонов граф.
 +
}}
  
−
|proof=
+
{{Теорема
−
По теореме Хватала: '''для''' <math>\forall k</math> '''верна импликация''' <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</math>  
+
|about = Вывод из [[Теорема Оре|теоремы Оре]]
 +
|statement =  
 +
Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то  <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]].
 +
|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> {{---}} гамильтонов граф.
 
}}
 
}}
 +
 +
==См. также==
 +
* [[Гамильтоновы графы]]
 +
* [[Теорема Хватала]]
 +
* [[Теорема Оре]]
 +
* [[Теорема Поша]]
 +
 +
== Источники информации ==
 +
* [[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.
 +
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Версия 01:43, 15 апреля 2021

Лемма о длине цикла

Лемма (о длине цикла):
Пусть [math]G[/math] — произвольный неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]\delta \geqslant 2[/math], то в графе [math]G[/math] существует цикл [math]C[/math] длиной [math]l \geqslant \delta + 1[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим путь максимальной длины [math]P = v_0 v_1 \dots v_s[/math]. Все смежные с [math]v_0[/math] вершины лежат на [math]P[/math]. Обозначим [math]k = \max \{i: v_0 v_i \in E\} [/math]. Тогда [math]\delta \leqslant \deg v_0 \leqslant k[/math]. Цикл [math]C = v_0 v_1 \dots v_k v_0[/math] имеет длину [math]l = k + 1 \geqslant \delta + 1[/math]
[math]\triangleleft[/math]

Альтернативное доказательство

Теорема (Дирак — альтернативное доказательство):
Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф.
Доказательство:
[math]\triangleright[/math]
Для [math]\forall k[/math] верна импликация [math]d_k \leqslant k \lt n/2 \Rightarrow d_{n-k} \geqslant n-k[/math], поскольку левая её часть всегда ложна. Тогда по теореме Хватала [math]G[/math] — гамильтонов граф.
[math]\triangleleft[/math]
Теорема (Вывод из теоремы Оре):
Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф.
Доказательство:
[math]\triangleright[/math]
Возьмем любые неравные вершины [math] u, v \in G [/math]. Тогда [math] \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n [/math]. По теореме Оре [math] G [/math] — гамильтонов граф.
[math]\triangleleft[/math]

См. также

Источники информации

  • 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.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Дирака&oldid=80794»