Теорема Дирака — различия между версиями
(→Теорема) |
|||
(не показано 14 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
+ | ==Лемма о длине цикла== | ||
{{Лемма | {{Лемма | ||
|about=о длине цикла | |about=о длине цикла | ||
− | |statement= Пусть <tex>G</tex> - произвольный неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>\delta \ | + | |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 | + | Рассмотрим путь максимальной длины <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> |
}} | }} | ||
+ | |||
+ | ==Теорема== | ||
{{Теорема | {{Теорема | ||
|about=Дирак | |about=Дирак | ||
|statement= | |statement= | ||
− | Пусть <tex>G</tex> - неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>n \ | + | Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]]. |
+ | |proof= | ||
+ | Пусть <tex>C</tex> {{---}} цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \geqslant \delta + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x \dots y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \geqslant n/2</tex>, а значит <tex>\delta \geqslant n - \delta > n - l = |V(G \backslash C)|</tex>. Поэтому каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>. | ||
+ | Заметим, что вершина <tex>x</tex> не может быть смежна: | ||
+ | * с вершинами из <tex>C</tex>, расстояние от которых до <tex>y</tex> (по <tex>C</tex>) не превышает m. Действительно, пусть вершина <tex>v \in C</tex> и расстояние от <tex>v</tex> до <tex>y</tex> по циклу меньше либо равно <tex>m</tex>. Тогда этот участок цикла можно заменить на <tex>v \rightarrow x \rightarrow P \rightarrow y</tex>, длина которого <tex>m + 1</tex>. Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикл <tex>C</tex>. | ||
+ | * двум смежным вершинам на <tex>C</tex>. Пусть <tex>u, v \in C</tex> и <tex>\{(u, v), (u, x), (x, v)\} \in E</tex>. Тогда заменив ребро <tex>(u, v)</tex> на <tex>u \rightarrow x \rightarrow v</tex>, увеличим длину цикла на <tex>1</tex>. | ||
+ | * вершинам из <tex>G \backslash (C \cup P)</tex>, поскольку <tex>P</tex> максимальный. | ||
+ | |||
+ | Получаем <tex>deg\ x \leqslant m + (l - 2m)/2 = l/2 < n/2 \leqslant \delta</tex>. Противоречие. | ||
+ | }} | ||
+ | |||
+ | ==Альтернативное доказательство== | ||
+ | |||
+ | {{Теорема | ||
+ | |about=Дирак {{---}} альтернативное доказательство | ||
+ | |statement= | ||
+ | Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]]. | ||
|proof= | |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. | ||
− | |||
− | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обходы графов]] | [[Категория: Обходы графов]] | ||
+ | [[Категория: Гамильтоновы графы]] |
Версия 00:32, 1 июня 2019
Содержание
Лемма о длине цикла
Лемма (о длине цикла): |
Пусть неориентированный граф и — минимальная степень его вершин. Если , то в графе существует цикл длиной . — произвольный |
Доказательство: |
Рассмотрим путь максимальной длины | . Все смежные с вершины лежат на . Обозначим . Тогда . Цикл имеет длину
Теорема
Теорема (Дирак): |
Пусть гамильтонов граф. — неориентированный граф и — минимальная степень его вершин. Если и , то — |
Доказательство: |
Пусть — цикл наибольшей длины в графе . По лемме его длина . Если - гамильтонов, то теорема доказана. Предположим обратное, т. е. . Рассмотрим путь наибольшей длины . Заметим, что по условию , а значит . Поэтому каждая вершина из смежна с некоторыми вершинами из . Заметим, что вершина не может быть смежна:
|
Альтернативное доказательство
Теорема (Дирак — альтернативное доказательство): |
Пусть гамильтонов граф. — неориентированный граф и — минимальная степень его вершин. Если и , то — |
Доказательство: |
Для теореме Хватала — гамильтонов граф. | верна импликация , поскольку левая её часть всегда ложна. Тогда по
Теорема (Вывод из теоремы Оре): |
Пусть гамильтонов граф. — неориентированный граф и — минимальная степень его вершин. Если и , то — |
Доказательство: |
Возьмем любые неравные вершины | . Тогда . По теореме Оре — гамильтонов граф.
См. также
Источники информации
- 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.