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

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавление первых картинок)
(Первая часть доказательства)
Строка 17: Строка 17:
 
Обозначим как <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> 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> и вместе с ними рассмотрим следующие пары:
<tex> j + l - 1 \leqslant k \leqslant j + l - 2 </tex> <br>
+
 
<tex> j + 2 \leqslant k \leqslant j + l - 2 </tex>
+
Для <tex>k</tex> таких, что <tex> j + l - 1 \leqslant k \leqslant j + l - 2 </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>)
 +
 
 +
Для <tex>k</tex> таких, что <tex> j + 2 \leqslant k \leqslant j + l - 2 </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>)
 +
 
 +
При добавлении таких пар ребер в графе появляется цикл длины <tex> l </tex>, а значить в <tex> G </tex> может входить максимум одно ребро из таких пар. Тогда можно утверждать, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
 +
 
 +
Докажем методом от противного, что <tex> n </tex> {{---}} четно. Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что  <tex> deg(v_x) \leqslant \genfrac{}{}{}{}{n-1}{2} </tex>.
 +
Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(i) \geqslant \genfrac{}{}{}{}{n-1}{2} + 1 = \genfrac{}{}{}{}{n+1}{2} </tex>, значит <tex> \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 </tex>, то есть мы получили противоречие с тем, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
 +
Без потери общности пусть <tex> v_x = v_n </tex> Рассмотрим <tex> 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} < </tex> <tex> \genfrac{}{}{}{}{n^2}{2} </tex>, то есть <tex> |E| < \genfrac{}{}{}{}{n^2}{2} </tex>, но по условию <tex> |E| \geqslant n^2/4 </tex>  - получили противоречие. Таким образом <tex> n </tex> является четным.
 +
 
 +
 
 +
 
 
}}
 
}}
  
Строка 25: Строка 36:
 
|about=Schmeichel & Hakimi
 
|about=Schmeichel & Hakimi
 
|statement=
 
|statement=
<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) \geq n </tex>. <br>
+
<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>(n-1)</tex>.
 
}}
 
}}

Версия 15:13, 4 декабря 2017

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


Теорема (J. A. Bondy):
[math]G = \lt V, E\gt [/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] 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]\triangleleft[/math]
Теорема (Schmeichel & Hakimi):
[math]G = \lt V, E\gt [/math] — гамильтонов граф, [math]|V| = n, v_1 v_2 v_3 \ldots v_n v_1 [/math] — его гамильтонов цикл, для которого выполняется неравенство [math] deg(v_1) + deg(v_n) \geqslant n [/math].
Тогда [math] G [/math] — панциклический граф, двудольный граф или граф, в котором нет только цикла длины [math](n-1)[/math].


Ссылки