Панциклический граф — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство теоремы J Bondy завершено)
(Убрал теорему Schmeichel & Hakimi, добавил утверждение с теоремой Оре)
Строка 16: Строка 16:
 
[[Файл:Circle 1.jpg|200px|left]] [[Файл:Circle 2.jpg|200px|right]]
 
[[Файл:Circle 1.jpg|200px|left]] [[Файл:Circle 2.jpg|200px|right]]
  
Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамильтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности, тогда ребра, не принадлежащие <tex> C </tex>, можно считать хордами.  
+
Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамильтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности.
  
 
Пусть в графе нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_i v_{i+1} </tex> и вместе с ними рассмотрим следующие пары:  
 
Пусть в графе нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_i v_{i+1} </tex> и вместе с ними рассмотрим следующие пары:  
Строка 45: Строка 45:
 
}}
 
}}
  
{{Теорема
+
{{Утверждение
|about=Schmeichel & Hakimi
+
|id = statement
|statement=
+
|statement = <tex>G(V, E), |V| = n , |E| = m,  \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>
<tex>G(V, E) </tex> {{---}} гамильтонов граф, <tex>|V| = n, v_1 v_2 v_3 \ldots v_n v_1 </tex> {{---}} его гамильтонов цикл, для которого выполняется неравенство <tex> deg(v_1) + deg(v_n) \geqslant n </tex>. <br>
+
Тогда верно одно из двух утверждений:
Тогда <tex> G </tex> {{---}} панциклический граф, двудольный граф или граф, в котором нет только цикла длины <tex>(n-1)</tex>.
+
#<tex> G </tex> {{---}} панциклический граф
 +
#<tex> G </tex>  = <tex>K_{n / 2, n / 2}</tex>
 +
|proof=По [https://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9E%D1%80%D0%B5 теореме Оре] <tex> G </tex> - гамильтонов граф. Покажем, что <tex> m \geqslant n^2/4 </tex>. Пусть <tex> k </tex> - минимальная степень вершины в графе.
 +
# <tex> k \geqslant n/2 </tex>, тогда <tex> 2m = \sum\limits_{i=1}^n deg(v_i) >= \sum\limits_{i=1}^n k = k * n \geqslant n^2/2 </tex> 
 +
# <tex> k < n/2 </tex>. Пусть существует x вершин, так что их степени равны <tex> k </tex>, тогда они все должна быть связаны, так как иначе мы получим противоречие с утверждением теоремы <tex> \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>. Понятно, что <tex> x \leqslant k + 1 </tex>, но так как граф является гамильтоновым, то он связен, а значит <tex> x < k + 1 </tex> ...
  
 +
<tex> m \geqslant \genfrac{}{}{}{}{1}{2}((n-k-1)(n-k)+k^2+k+1) = \genfrac{}{}{}{}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{}{n^2+1}{4} </tex>
  
 +
Итоге граф подходит под условия теоремы.
 
}}
 
}}
  

Версия 18:56, 5 декабря 2017

Определение:
Панциклический граф (англ. pancyclic graph) — граф, в котором есть циклы всех длин от [math] 3 [/math] до [math] n [/math] . Если граф содержит все циклы от [math] r [/math] до [math] n [/math], то такой граф называют [math] r [/math]-панциклическим.


Предпосылки к теореме. Теорема Мантела(частный случай теоремы Турана) утверждает, что для любой граф на [math] n [/math] вершинах, у которого количество ребер не меньше [math] n^2 / 4 [/math], либо содержит треуголник либо является [math]K_{n / 2, n / 2}[/math].

Теорема (J. A. Bondy):
[math]G(V, E) [/math] — гамильтонов граф, [math]|V| = n, |E| \geqslant n^2/4 [/math].

Тогда верно одно из двух утверждений:

  1. [math] G [/math] — панциклический граф
  2. [math] G [/math] = [math]K_{n / 2, n / 2}[/math]
Доказательство:
[math]\triangleright[/math]
Circle 1.jpg
Circle 2.jpg

Обозначим как [math] C=v_1 v_2 v_3 \ldots v_n [/math] гамильтонов цикл в графе [math] G [/math]. Для простоты расположим [math] C [/math] на окружности.

Пусть в графе нет цикла длины [math] l [/math], [math] 3 \leqslant l \leqslant n-1 [/math] (по условию в графе существует гамильтонов цикл, длина которого равна [math] n [/math]). Рассмотрим две соседние вершины [math] v_i v_{i+1} [/math] и вместе с ними рассмотрим следующие пары:

Для [math]k[/math] таких, что [math] j + l - 1 \leqslant k \leqslant j + l - 2 [/math] рассмотрим пары ([math]v_j, v_k[/math]) и ([math]v_{j+1}, v_{k-l+3}[/math])

Для [math]k[/math] таких, что [math] j + 2 \leqslant k \leqslant j + l - 2 [/math] рассмотрим пары ([math]v_j, v_k[/math]) и ([math]v_{j+1}, v_{k-l+1}[/math])

При добавлении таких пар ребер в графе появляется цикл длины [math] l [/math], а значить в [math] G [/math] может входить максимум одно ребро из таких пар. Тогда можно утверждать, что [math] deg(v_j) + deg(v_{j + 1}) \leqslant n [/math].

Докажем методом от противного, что [math] n [/math] — четно. Пусть [math] n [/math] является нечетным, тогда из рассуждений выше существует вершина [math] v_x [/math], для которое верно, что [math] deg(v_x) \leqslant \genfrac{}{}{}{}{n-1}{2} [/math]. Пусть это не так, тогда [math] \forall i, 1 \leqslant i \leqslant n : deg(i) \geqslant \genfrac{}{}{}{}{n-1}{2} + 1 = \genfrac{}{}{}{}{n+1}{2} [/math], значит [math] \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{}{n+1}{2} + \genfrac{}{}{}{}{n+1}{2} = n + 1 [/math], то есть мы получили противоречие с тем, что [math] deg(v_j) + deg(v_{j + 1}) \leqslant n [/math]. Без потери общности пусть [math] v_x = v_n [/math] Рассмотрим [math] 2|E| = \sum\limits_{i=1}^n deg(v_i) = \sum\limits_{i=1}^{(n - 1)/2} (deg(v_{2i-1}) + deg(v_{2i})) + deg(v_n) \leqslant \genfrac{}{}{}{}{n(n-1)}{2} + \genfrac{}{}{}{}{n-1}{2} \lt [/math] [math] \genfrac{}{}{}{}{n^2}{2} [/math], то есть [math] |E| \lt \genfrac{}{}{}{}{n^2}{2} [/math], но по условию [math] |E| \geqslant n^2/4 [/math] - получили противоречие. Таким образом [math] n [/math] является четным. Тогда верно, что [math] 2|E| \leqslant \sum\limits_{i=1}^n deg(v_i) = \sum\limits_{i=1}^{n/2} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{}{n^2}{2} [/math], а так как по условию [math] |E| \geqslant n^2/4 [/math], то [math] |E| = \genfrac{}{}{}{}{n^2}{4} [/math]. Данное равенство достигается, если верно, что:

Circle 3.jpg
  • [math] j + l - 1 \leqslant k \leqslant j + l - 2 [/math] : [math] (v_j, v_k) \in E [/math] и [math](v_{j+1}, v_{k-l+3}) \notin E [/math]
  • [math] j + 2 \leqslant k \leqslant j + l - 2 [/math] : [math](v_j, v_k) \in E [/math] и [math](v_{j+1}, v_{k-l+1}) \notin E [/math]

Пусть [math] G [/math] не [math] K_{n/2, n/2} [/math], тогда существует такое четное число [math] k [/math], что в графе [math] G [/math] существует ребро [math] (v_j, v_{j+k}) [/math]. Докажем, что в таком случае существует ребро [math] (v_j, v_{j+2}) \in E [/math]. Пусть это не так и минимальное четное [math] k [/math], что [math] \exists (v_j, v_{j+k}) \in E [/math] больше двух, т.е. [math] k \geqslant 4 [/math]. Тогда существует три случая:

  1. [math] 4 \leqslant k \leqslant n - l [/math]
    [math] (v_j, v_{j+k}) \in E \Rightarrow (v_{j+1}, v_{j+k+l-3}) \notin E \Rightarrow (v_{j+2}, v_{j+k}) \in E [/math]
    [math] \exists l = k-2 : (v_i, v_{i+l}) \in E [/math] - противоречие с минимальностью [math] k [/math]
  2. [math] n - l + 2 \leqslant k \leqslant 2n - 2l [/math]
    [math] (v_j, v_{j+k}) \in E \Rightarrow (v_{j-1}, v_{j+k+l-1}) \notin E \Rightarrow (v_{j-2}, v_{j+k+2l-4}) \in E [/math]
    однако [math] 2n - k - 2l + 2 \leqslant k - 2 [/math] - противоречие с минимальностью [math] k [/math]
  3. [math] 2n - 2l + 2 \leqslant k \leqslant n - 2 [/math]
    [math] (v_j, v_{j+k}) \in E \Rightarrow (v_{j-1}, v_{j+k+l-1}) \notin E \Rightarrow (v_{j-2}, v_{j+k+2l-2}) \in E [/math]
    однако [math] k + 2l - 2n \leqslant k - 2 [/math] - снова проиворечие с минимальностью выбранного k
Таким образом, в [math] G [/math] существует ребро [math] (v_j, v_{j+2}) [/math], но тогда [math] (v_j, v_{j+l}) \notin E [/math], а следовательно [math] (v_{j+1}, v_{j+3}) \in E [/math]. Если продолжить по всему графу, то получим, что [math] \forall j : (v_j, v_{j+2}) \in E [/math] и, как следствие, [math] G [/math] - панциклический.
[math]\triangleleft[/math]
Утверждение:
[math]G(V, E), |V| = n , |E| = m, \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n [/math]

Тогда верно одно из двух утверждений:

  1. [math] G [/math] — панциклический граф
  2. [math] G [/math] = [math]K_{n / 2, n / 2}[/math]
[math]\triangleright[/math]

По теореме Оре [math] G [/math] - гамильтонов граф. Покажем, что [math] m \geqslant n^2/4 [/math]. Пусть [math] k [/math] - минимальная степень вершины в графе.

  1. [math] k \geqslant n/2 [/math], тогда [math] 2m = \sum\limits_{i=1}^n deg(v_i) \gt = \sum\limits_{i=1}^n k = k * n \geqslant n^2/2 [/math]
  2. [math] k \lt n/2 [/math]. Пусть существует x вершин, так что их степени равны [math] k [/math], тогда они все должна быть связаны, так как иначе мы получим противоречие с утверждением теоремы [math] \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n [/math]. Понятно, что [math] x \leqslant k + 1 [/math], но так как граф является гамильтоновым, то он связен, а значит [math] x \lt k + 1 [/math] ...

[math] m \geqslant \genfrac{}{}{}{}{1}{2}((n-k-1)(n-k)+k^2+k+1) = \genfrac{}{}{}{}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{}{n^2+1}{4} [/math]

Итоге граф подходит под условия теоремы.
[math]\triangleleft[/math]


Ссылки