Изменения
бред написан какой-то
==ТеоремаЛемма о длине цикла==
{{Лемма
|about=о длине цикла
|statement= Пусть <tex>G</tex> {{- --}} произвольный [[Основные определения теории графов#def_undirected_graph_1|неориентированный граф ]] и <tex>\delta</tex> {{--- }} минимальная [[Основные определения теории графов#def_graph_degree_1|степень ]] его вершин. Если <tex>\delta \ge geqslant 2</tex>, то в графе <tex>G</tex> существует [[Основные определения теории графов#def_graph_cycle_1|цикл ]] <tex>C</tex> длиной <tex>l \ge 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 \le leqslant \deg\ v_0 \le leqslant k</tex>. Цикл <tex>C = v_0 v_1 .. \dots v_k v_0</tex> имеет длину <tex>l = k + 1 \ge geqslant \delta + 1</tex>
}}
==Альтернативное доказательство==
{{Теорема
|about=Дирак{{---}} альтернативное доказательство
|statement=
Пусть <tex>G</tex> {{- --}} неориентированный граф и <tex>\delta</tex> {{--- }} минимальная степень его вершин. Если <tex>n \ge geqslant 3</tex> и <tex>\delta \ge geqslant n/2</tex>, то <tex>G</tex> {{--- }} [[Гамильтоновы графы|гамильтонов граф]].
|proof=
}}
==Альтернативное доказательствоСм. также==* [[Гамильтоновы графы]]* [[Теорема Хватала]]* [[Теорема Оре]]* [[Теорема Поша]]
== Источники информации ==* [[wikipedia:en:Dirac's_Theorem|Wikipedia {{Теорема---}} Dirac's Theorem]]|about=Дирак* Graham, R.L., Groetschel M., and Lovász L., eds. (альтернативное доказательство1996)|statement=Пусть <tex>G</tex> - неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>n \ge 3</tex> и <tex>\delta \ge n/''Handbook of Combinatorics'', Volumes 1 and 2</tex>, то . <tex>G</tex> Elsevier (North- гамильтонов графHolland), Amsterdam, and MIT Press, Cambridge, Mass.|proof=Для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{nISBN 0-262-k} \ge n07169-k</tex>, поскольку левая её часть всегда ложнаX.}}
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]