Теорема Дирака

2022-04-22T11:20:30Z

94.29.124.91: /* Лемма о длине цикла */

9м топ остальным по лицу хлоп

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

{{Теорема
|about=Дирак {{---}} альтернативное доказательство
|statement=
Пусть <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> {{---}} гамильтонов граф.
}}

{{Теорема
|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.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]

Викиконспекты - Вклад участника [ru]

Теорема Дирака