Теорема Дирака — различия между версиями
Shersh (обсуждение | вклад) (→Источники) |
(бред написан какой-то) |
||
(не показано 8 промежуточных версий 6 участников) | |||
Строка 2: | Строка 2: | ||
{{Лемма | {{Лемма | ||
|about=о длине цикла | |about=о длине цикла | ||
− | |statement= Пусть <tex>G</tex> {{---}} произвольный неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>\delta \geqslant 2</tex>, то в графе <tex>G</tex> существует цикл <tex>C</tex> длиной <tex>l \geqslant \delta + 1</tex>. | + | |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= | |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> | Рассмотрим путь максимальной длины <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> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
Строка 45: | Строка 29: | ||
* [[Теорема Хватала]] | * [[Теорема Хватала]] | ||
* [[Теорема Оре]] | * [[Теорема Оре]] | ||
+ | * [[Теорема Поша]] | ||
− | == Источники == | + | == Источники информации == |
* [[wikipedia:en:Dirac's_Theorem|Wikipedia {{---}} Dirac's Theorem]] | * [[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. | * 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. | ||
Строка 53: | Строка 38: | ||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обходы графов]] | [[Категория: Обходы графов]] | ||
+ | [[Категория: Гамильтоновы графы]] |
Версия 01:43, 15 апреля 2021
Лемма о длине цикла
Лемма (о длине цикла): |
Пусть неориентированный граф и — минимальная степень его вершин. Если , то в графе существует цикл длиной . — произвольный |
Доказательство: |
Рассмотрим путь максимальной длины | . Все смежные с вершины лежат на . Обозначим . Тогда . Цикл имеет длину
Альтернативное доказательство
Теорема (Дирак — альтернативное доказательство): |
Пусть гамильтонов граф. — неориентированный граф и — минимальная степень его вершин. Если и , то — |
Доказательство: |
Для теореме Хватала — гамильтонов граф. | верна импликация , поскольку левая её часть всегда ложна. Тогда по
Теорема (Вывод из теоремы Оре): |
Пусть гамильтонов граф. — неориентированный граф и — минимальная степень его вершин. Если и , то — |
Доказательство: |
Возьмем любые неравные вершины | . Тогда . По теореме Оре — гамильтонов граф.
См. также
Источники информации
- 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.