Материал из Викиконспекты
|
(Метки: правка с мобильного устройства, правка из мобильной версии) |
| Строка 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>
| |
| − | }}
| |
| | | | |
| | ==Альтернативное доказательство== | | ==Альтернативное доказательство== |
Версия 12:54, 20 ноября 2021
Нохчо любит ослов салам алейкум в туза
Альтернативное доказательство
| Теорема (Дирак — альтернативное доказательство): |
Пусть [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.
