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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
Пусть <tex>C</tex> - цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \ge n + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x..y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \ge n/2</tex>, а значит <tex>\delta \ge n - \delta > n - l = |V(G \backslash C)|</tex> и каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>.
 
Пусть <tex>C</tex> - цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \ge n + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x..y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \ge n/2</tex>, а значит <tex>\delta \ge 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>C</tex>). Получаем <tex>deg x \le m + (l - 2m)/2 =l/2 < n/2 \le \delta</tex>. Противоречие.
 
Заметим, что вершина <tex>x</tex> не может быть смежна с вершинами из <tex>C</tex>, расстояние от которых до <tex>y</tex>(по <tex>C</tex>) не превышает m, а также двум смежным вершинам(это противоречило бы максимальности цикла <tex>C</tex>). Получаем <tex>deg x \le m + (l - 2m)/2 =l/2 < n/2 \le \delta</tex>. Противоречие.
 +
}}
  
По [[Теорема Хватала|теореме Хватала]]: для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>, поскольку левая её часть всегда ложна.
+
Заметим, что эта теорема является следствием из [[Теорема Хватала|теоремы Хватала]]. Действительно, для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>, поскольку левая её часть всегда ложна.
}}
 
  
 
== Источники ==
 
== Источники ==
Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
+
Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]

Версия 06:24, 21 ноября 2011

Эта статья находится в разработке!
Лемма (о длине цикла):
Пусть [math]G[/math] - произвольный неориентированный граф и [math]\delta[/math] - минимальная степень его вершин. Если [math]\delta \ge 2[/math], то в графе [math]G[/math] существует цикл [math]C[/math] длиной [math]l \ge \delta + 1[/math].
Доказательство:
[math]\triangleright[/math]
Рассмотрим путь максимальной длины [math]P = v_0 v_1 .. v_s[/math]. Все смежные с [math]v_0[/math] вершины лежат на [math]P[/math]. Обозначим [math]k = max\{i: v_0 v_i \in E\}[/math]. Тогда [math]\delta \le deg v_0 \le k[/math]. Цикл [math]C = v_0 v_1 .. v_k v_0[/math] имеет длину [math]l = k + 1 \ge \delta + 1[/math]
[math]\triangleleft[/math]
Теорема (Дирак):
Пусть [math]G[/math] - неориентированный граф и [math]\delta[/math] - минимальная степень его вершин. Если [math]n \ge 3[/math] и [math]\delta \ge n/2[/math], то [math]G[/math] - гамильтонов граф.
Доказательство:
[math]\triangleright[/math]

Пусть [math]C[/math] - цикл наибольшей длины в графе [math]G[/math]. По лемме его длина [math]l \ge n + 1[/math]. Если [math]C[/math] - гамильтонов, то теорема доказана. Предположим обратное, т. е. [math]G \backslash C \ne \varnothing[/math]. Рассмотрим путь [math]P = x..y : P \cap C = \{y\}[/math] наибольшей длины [math]m[/math]. Заметим, что по условию [math]\delta \ge n/2[/math], а значит [math]\delta \ge n - \delta \gt n - l = |V(G \backslash C)|[/math] и каждая вершина из [math]G \backslash C[/math] смежна с некоторыми вершинами из [math]C[/math].

Заметим, что вершина [math]x[/math] не может быть смежна с вершинами из [math]C[/math], расстояние от которых до [math]y[/math](по [math]C[/math]) не превышает m, а также двум смежным вершинам(это противоречило бы максимальности цикла [math]C[/math]). Получаем [math]deg x \le m + (l - 2m)/2 =l/2 \lt n/2 \le \delta[/math]. Противоречие.
[math]\triangleleft[/math]

Заметим, что эта теорема является следствием из теоремы Хватала. Действительно, для [math]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k[/math], поскольку левая её часть всегда ложна.

Источники

Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1