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

Версия 19:50, 20 марта 2022

Лемма (о длине цикла):

Пусть — произвольный неориентированный граф и — минимальная степень его вершин. Если , то в графе существует цикл длиной .

Доказательство:

Рассмотрим путь максимальной длины . Все смежные с вершины лежат на . Обозначим . Тогда . Цикл имеет длину

Теорема (Дирак — альтернативное доказательство):

Пусть — неориентированный граф и — минимальная степень его вершин. Если и , то — гамильтонов граф.

Доказательство:

Для верна импликация , поскольку левая её часть всегда ложна. Тогда по теореме Хватала — гамильтонов граф.

Теорема (Вывод из теоремы Оре):

Пусть — неориентированный граф и — минимальная степень его вершин. Если и , то — гамильтонов граф.

Доказательство:

Возьмем любые неравные вершины . Тогда . По теореме Оре — гамильтонов граф.

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.

@@ Строка 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>
+}}
 ==Альтернативное доказательство==