Изменения

Перейти к: навигация, поиск

Теорема Дирака

2987 байт добавлено, 15 апрель
бред написан какой-то
==Лемма о длине цикла==
{{Лемма
|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>
}}
 
==Альтернативное доказательство==
 
{{Теорема
|about=Дирак {{---}} альтернативное доказательство
|statement=
Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <mathtex>n \ n > geqslant 3</mathtex> и <mathtex>deg\ v delta \ge geqslant n/2</mathtex> , то для любой вершины <mathtex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]].|proof=Для <tex>\ vforall k</mathtex> верна импликация <tex>d_k \leqslant k < n/2 \Rightarrow d_{n-k} \geqslant n-k</tex> графа '''G''', то '''поскольку левая её часть всегда ложна. Тогда по [[Теорема Хватала | теореме Хватала]] <tex>G''' </tex> {{--- }} гамильтонов граф.}}
{{Теорема|about = Вывод из [[Теорема Оре|теоремы Оре]]|proofstatement =По теореме Хватала: '''для''' Пусть <tex>G</tex> {{---}} неориентированный граф и <mathtex>\forall kdelta</mathtex> '''верна импликация''' {{---}} минимальная степень его вершин. Если <mathtex>d_k n \le k geqslant 3< /tex> и <tex>\delta \geqslant n/2 \Rightarrow d_</tex>, то <tex>G</tex> {{n-k--} } [[Гамильтоновы графы|гамильтонов граф]].|proof = Возьмем любые неравные вершины <tex> u, v \in G </tex>. Тогда <tex> \displaystyle \deg u + \deg v \geqslant \frac n 2 + \ge frac n-k2 = n </tex>. По теореме Оре <tex> G </mathtex> {{---}} гамильтонов граф.
}}
 
==См. также==
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Оре]]
* [[Теорема Поша]]
 
== Источники информации ==
* [[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.
 
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]
[[Категория: Гамильтоновы графы]]
Анонимный участник

Навигация