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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники информации)
(добавлена лемма о четности n)
(не показано 29 промежуточных версий 5 участников)
Строка 1: Строка 1:
 +
== Основные определения ==
 
{{Определение
 
{{Определение
|definition='''Панциклический граф''' (англ. ''pancyclic graph'') {{---}} граф, в котором есть циклы всех длин от <tex> 3 </tex> до <tex> n </tex> . Если граф содержит все циклы от <tex> r </tex> до <tex> n </tex>, то такой граф называют <tex> r </tex>-панциклическим.
+
|definition='''Панциклический граф''' (англ. ''pancyclic graph'') {{---}} граф, в котором есть циклы всех длин от <tex> 3 </tex> до <tex> n </tex>.
 
}}
 
}}
  
'''Предпосылки к теореме'''. [https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem#Mantel's_theorem Теорема Мантела](частный случай [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A2%D1%83%D1%80%D0%B0%D0%BD%D0%B0 теоремы Турана]) утверждает, что для любой граф на <tex> n </tex> вершинах, у которого количество ребер не меньше <tex> n^2 / 4 </tex>, либо содержит треуголник либо является <tex>K_{n / 2, n / 2}</tex>.
+
{{Определение
 +
|definition='''<tex> r </tex>-панциклический граф''' (англ. ''<tex> r </tex>-pancyclic graph'') {{---}} граф содержит все циклы от <tex> r </tex> до <tex> n </tex>.
 +
}}
  
 +
== Основная теорема ==
 
{{Теорема
 
{{Теорема
 
|about=J. A. Bondy
 
|about=J. A. Bondy
 
|statement=
 
|statement=
<tex>G(V, E) </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geqslant n^2/4 </tex>.
+
Пусть <tex>G(V, E) </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>.
 
Тогда верно одно из двух утверждений:
 
Тогда верно одно из двух утверждений:
 
#<tex> G </tex> {{---}} панциклический граф
 
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex>  = <tex>K_{n / 2, n / 2}</tex>
+
#<tex> G </tex>  = <tex>K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}</tex>
 
|proof=
 
|proof=
  
[[Файл:Circle 1.jpg|200px|left]] [[Файл:Circle 2.jpg|200px|right]]
+
[[Файл:Circle 1.jpg|200px|left|thumb| <tex> v_k </tex> на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> и ребра (<tex>v_j, v_k</tex>) и  (<tex>v_{j+1}, v_{k-l+3}</tex>) выделены. Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l]] [[Файл:Circle 2.jpg|200px|right|thumb| <tex> v_k </tex> на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> и ребра (<tex>v_j, v_k</tex>) и  (<tex>v_{j+1}, v_{k-l+1}</tex>) выделены. Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l]]
 +
 
 +
Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамильтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности. Также подразумевается, что все индексы при вершинах берутся по модулю, то есть <tex> v_j = v_{((j - 1)\bmod n) + 1} </tex>. 
 +
 
 +
Пусть граф не панциклический, тогда в неи нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_j v_{j+1} </tex> и вместе с ними рассмотрим следующие пары:
  
Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамильтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности.Также подразумевается, что все индексы при вершинах берутся по модулю, т.е. <tex> v_j = v_{(j - 1) mod n + 1} </tex>
+
Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>)
  
Пусть в графе нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_i v_{i+1} </tex> и вместе с ними рассмотрим следующие пары:
+
Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>)
  
Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>) (см. рисунок слева)
+
При добавлении таких пар ребер в графе появляется цикл длины <tex> l </tex>. Действительно:
 +
*Рассмотрим первый случай, когда <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> и существуют ребра (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>). Длина цикла равна <tex> len((v_{k - l + 3}, v_{k - l + 4}, v_{k})) + 3 = k - (k - l + 3) + 3 =  l - 3 + 3 = l </tex>.
 +
*Рассмотрим второй случай, когда <tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> и существуют ребра (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>). Тогда длина цикла равна <tex> len((v_{k}, v_{k - 1}, v_{k - l + 1})) - 1 + 2 = k - (k - l + 1) - 1 + 2 =  l - 1 - 1 + 2 = l </tex>.  
 +
Значит в <tex> G </tex> может входить максимум одно ребро из таких пар. Тогда можно утверждать, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
  
Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>) (см. рисунок справа)
+
{{Лемма
 +
|statement=
 +
Если для графа <tex> G </tex> выполнены условия из теоремы и в нем отсутствует цикл длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex>, то количество вершин в графе четное
 +
|proof= Доказательство будем вести методом от противного.
 +
*Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что <tex> deg(v_x) \leqslant \genfrac{}{}{}{0}{n-1}{2} </tex>.
 +
**Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(v_i) \geqslant \genfrac{}{}{}{0}{n-1}{2} + 1 = \genfrac{}{}{}{0}{n+1}{2} </tex>, значит <tex> \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{0}{n+1}{2} + \genfrac{}{}{}{0}{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}^{\genfrac{}{}{}{}{n - 1}{2}} (deg(v_{2i-1}) + deg(v_{2i})) + deg(v_n) \leqslant \genfrac{}{}{}{0}{n(n-1)}{2} + </tex> <tex> \genfrac{}{}{}{0}{n-1}{2} < \genfrac{}{}{}{0}{n^2}{2} </tex>, то есть <tex> |E| < \genfrac{}{}{}{0}{n^2}{4} </tex>, но по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>  {{---}} получили противоречие.  
 +
}}
  
При добавлении таких пар ребер в графе появляется цикл длины <tex> l </tex>, а значить в <tex> G </tex> может входить максимум одно ребро из таких пар. Тогда можно утверждать, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
+
По лемме <tex> n </tex> является четным, если в цикле отсутствует цикл длины <tex> l </tex>. Тогда верно, что <tex> 2|E| = \sum\limits_{i=1}^n deg(v_i) =  \sum\limits_{i=1}^{\genfrac{}{}{}{}{n}{2}} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{0}{n^2}{2} </tex>, а так как по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>, то <tex> |E| = \genfrac{}{}{}{0}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:
  
Докажем методом от противного, что <tex> n </tex> {{---}} четно. Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что  <tex> deg(v_x) \leqslant \genfrac{}{}{}{}{n-1}{2} </tex>.
+
[[Файл:Circle 3.jpg|800px|right|thumb|Слева направо изображены случаи 1-3. Красным выделены ребра, которые не могут быть в рассматриваемом графе, если в нем присутствуют ребра, выделенные зеленым]]
Пусть это не так, тогда <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}{4} </tex>, но по условию <tex> |E| \geqslant n^2/4 </tex>  {{---}} получили противоречие. Таким образом <tex> n </tex> является четным. Тогда верно, что <tex> 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} </tex>, а так как по условию <tex> |E| \geqslant n^2/4 </tex>, то <tex> |E| = \genfrac{}{}{}{}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:
 
  
[[Файл:Circle 3.jpg|800px|right]]
+
*<tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j - 1}) </tex>: <tex> (v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \notin E </tex> или <tex> (v_j, v_k) \notin E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \in E </tex>
*<tex> j + l - 1 \leqslant k \leqslant j + l - 2 </tex> : <tex> (v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \notin E </tex>
 
  
*<tex> j + 2 \leqslant k \leqslant j + l - 2 </tex> : <tex>(v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \notin E </tex>
+
*<tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex>: <tex>(v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \notin E </tex> или <tex>(v_j, v_k) \notin E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \in E </tex>
  
Пусть <tex> G </tex> не <tex> K_{n/2, n/2} </tex>, тогда существует такое четное число <tex> k </tex>, что в графе <tex> G </tex> существует ребро <tex> (v_j, v_{j+k}) </tex>. Докажем, что в таком случае существует ребро <tex> (v_j, v_{j+2}) \in E </tex>. Пусть это не так и минимальное четное <tex> k </tex>, что <tex> \exists (v_j, v_{j+k}) \in E </tex> больше двух, т.е. <tex> k \geqslant 4 </tex>. Тогда существует три случая:
+
Пусть <tex> G </tex> не <tex>K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}</tex>, тогда существует такое четное число <tex> k </tex>, что в графе <tex> G </tex> существует ребро <tex> (v_j, v_{j+k}) </tex>, то есть существует цикл нечетной длины. Докажем, что в таком случае существует ребро <tex> (v_j, v_{j+2}) \in E </tex>. Пусть это не так и минимальное четное <tex> k </tex>, что <tex> \exists (v_j, v_{j+k}) \in E </tex> больше двух, то есть <tex> k \geqslant 4 </tex>. Тогда существует три случая:
  
 
# <tex> 4 \leqslant k \leqslant n - l </tex> <br> <tex> (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 </tex> <br> <tex> \exists l = k-2 : (v_i, v_{i+l}) \in E </tex> {{---}} противоречие с минимальностью <tex> k </tex>
 
# <tex> 4 \leqslant k \leqslant n - l </tex> <br> <tex> (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 </tex> <br> <tex> \exists l = k-2 : (v_i, v_{i+l}) \in E </tex> {{---}} противоречие с минимальностью <tex> k </tex>
 
# <tex> n - l + 2 \leqslant k \leqslant 2n - 2l </tex> <br> <tex> (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 </tex> <br> однако <tex> 2n - k - 2l + 2 \leqslant k - 2 </tex> {{---}} противоречие  с минимальностью <tex> k </tex>
 
# <tex> n - l + 2 \leqslant k \leqslant 2n - 2l </tex> <br> <tex> (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 </tex> <br> однако <tex> 2n - k - 2l + 2 \leqslant k - 2 </tex> {{---}} противоречие  с минимальностью <tex> k </tex>
# <tex> 2n - 2l + 2 \leqslant k \leqslant n - 2 </tex> <br> <tex> (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 </tex> <br> однако <tex> k + 2l - 2n \leqslant k - 2 </tex> {{---}} снова проиворечие с минимальностью выбранного k  
+
# <tex> 2n - 2l + 2 \leqslant k \leqslant n - 2 </tex> <br> <tex> (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 </tex> <br> однако <tex> k + 2l - 2n \leqslant k - 2 </tex> {{---}} снова противоречие с минимальностью выбранного k  
  
 
Таким образом, в <tex> G </tex> существует ребро <tex> (v_j, v_{j+2}) </tex>, но тогда <tex> (v_j, v_{j+l}) \notin E </tex>, а следовательно <tex> (v_{j+1}, v_{j+3}) \in E </tex>. Если продолжить по всему графу, то получим, что <tex> \forall j : (v_j, v_{j+2}) \in E </tex> и, как следствие, <tex> G </tex> {{---}} панциклический.   
 
Таким образом, в <tex> G </tex> существует ребро <tex> (v_j, v_{j+2}) </tex>, но тогда <tex> (v_j, v_{j+l}) \notin E </tex>, а следовательно <tex> (v_{j+1}, v_{j+3}) \in E </tex>. Если продолжить по всему графу, то получим, что <tex> \forall j : (v_j, v_{j+2}) \in E </tex> и, как следствие, <tex> G </tex> {{---}} панциклический.   
Строка 45: Строка 60:
 
}}
 
}}
  
 +
=== Следствие ===
 
{{Утверждение
 
{{Утверждение
 
|id = statement
 
|id = statement
|statement = <tex>G(V, E), |V| = n , |E| = m,  \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>
+
|statement = Пусть <tex>G(V, E), |V| = n , |E| = m,  \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>
 
Тогда верно одно из двух утверждений:
 
Тогда верно одно из двух утверждений:
 
#<tex> G </tex> {{---}} панциклический граф
 
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex>  = <tex>K_{n / 2, n / 2}</tex>
+
#<tex> G </tex>  = <tex>K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}</tex>
|proof=По [[Теорема Оре|теореме Оре]] <tex> G </tex> {{---}} гамильтонов граф. Покажем, что <tex> m \geqslant n^2/4 </tex>. Пусть <tex> k </tex> {{---}} минимальная степень вершины в графе.  
+
|proof=По [[Теорема Оре|теореме Оре]] <tex> G </tex> {{---}} гамильтонов граф. Покажем, что <tex> m \geqslant \genfrac{}{}{}{0}{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 \geqslant \genfrac{}{}{}{}{n}{2} </tex>, тогда <tex> 2m = \sum\limits_{i=1}^n deg(v_i) >= \sum\limits_{i=1}^n k = k n \geqslant \genfrac{}{}{}{0}{n^2}{2} </tex>   
# <tex> k < n/2 </tex>. Пусть существует <tex> x </tex> вершин, так что их степени равны <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> n - k - 1 </tex> степени которых как минимум <tex> n - k </tex>. Тогда можно оценить количество ребер. <br> <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>
+
# <tex> k < \genfrac{}{}{}{}{n}{2} </tex>. Пусть существует <tex> x </tex> вершин, так что их степени равны <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> x </tex> вершин степени <tex> k </tex> провести оставшиеся ребра в одну вершину, у которой степень больше, то в графе остенется как минимум <tex> n - k - 1 </tex> вершин, степени которых как минимум <tex> n - k </tex>, поскольку должно выполняться неравенство из теоермы. Тогда можно оценить количество ребер. <br> <tex> m \geqslant \genfrac{}{}{}{0}{1}{2}((n-k-1)(n-k)+k^2+(k+1)) = \genfrac{}{}{}{0}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{0}{n^2+1}{4} </tex>
  
Итого граф подходит под условия теоремы.
+
Таким образом <tex> m \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex> и согласно теореме граф либо панциклический, либо <tex>K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}</tex>.
 
}}
 
}}
  
Строка 61: Строка 77:
 
* [[Теорема Оре|Теорема Оре]]
 
* [[Теорема Оре|Теорема Оре]]
 
* [[Гамильтоновы графы|Гамильтоновы графы]]
 
* [[Гамильтоновы графы|Гамильтоновы графы]]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Обходы графов]]
  
 
== Источники информации ==
 
== Источники информации ==
 
* [https://ac.els-cdn.com/0095895671900165/1-s2.0-0095895671900165-main.pdf?_tid=6388217a-d131-11e7-9e9c-00000aab0f02&acdnat=1511539751_317a50813ff61926478abcae5f032887 J.A. Bondy {{---}} Pancyclic Graphs I*]
 
* [https://ac.els-cdn.com/0095895671900165/1-s2.0-0095895671900165-main.pdf?_tid=6388217a-d131-11e7-9e9c-00000aab0f02&acdnat=1511539751_317a50813ff61926478abcae5f032887 J.A. Bondy {{---}} Pancyclic Graphs I*]
 
* [https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf Д.В. Карпов {{---}} Теория графов.]
 
* [https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf Д.В. Карпов {{---}} Теория графов.]
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Обходы графов]]
 

Версия 16:41, 26 декабря 2017

Основные определения

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


Определение:
[math] r [/math]-панциклический граф (англ. [math] r [/math]-pancyclic graph) — граф содержит все циклы от [math] r [/math] до [math] n [/math].


Основная теорема

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

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

  1. [math] G [/math] — панциклический граф
  2. [math] G [/math] = [math]K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}[/math]
Доказательство:
[math]\triangleright[/math]
[math] v_k [/math] на дуге [math] (v_{j + l - 1}, v_{j + l}, v_{j -1}) [/math] и ребра ([math]v_j, v_k[/math]) и ([math]v_{j+1}, v_{k-l+3}[/math]) выделены. Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l
[math] v_k [/math] на дуге [math] (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) [/math] и ребра ([math]v_j, v_k[/math]) и ([math]v_{j+1}, v_{k-l+1}[/math]) выделены. Дуги и ребра, окрашенные в зеленый цвет, образуют цикл длины l

Обозначим как [math] C=v_1 v_2 v_3 \ldots v_n [/math] гамильтонов цикл в графе [math] G [/math]. Для простоты расположим [math] C [/math] на окружности. Также подразумевается, что все индексы при вершинах берутся по модулю, то есть [math] v_j = v_{((j - 1)\bmod n) + 1} [/math].

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

Для [math]k[/math] таких, что [math] v_k [/math] лежит на дуге [math] (v_{j + l - 1}, v_{j + l}, v_{j -1}) [/math] рассмотрим пары ([math]v_j, v_k[/math]) и ([math]v_{j+1}, v_{k-l+3}[/math])

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

При добавлении таких пар ребер в графе появляется цикл длины [math] l [/math]. Действительно:

  • Рассмотрим первый случай, когда [math] v_k [/math] лежит на дуге [math] (v_{j + l - 1}, v_{j + l}, v_{j -1}) [/math] и существуют ребра ([math]v_j, v_k[/math]) и ([math]v_{j+1}, v_{k-l+3}[/math]). Длина цикла равна [math] len((v_{k - l + 3}, v_{k - l + 4}, v_{k})) + 3 = k - (k - l + 3) + 3 = l - 3 + 3 = l [/math].
  • Рассмотрим второй случай, когда [math] v_k [/math] лежит на дуге [math] (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) [/math] и существуют ребра ([math]v_j, v_k[/math]) и ([math]v_{j+1}, v_{k-l+1}[/math]). Тогда длина цикла равна [math] len((v_{k}, v_{k - 1}, v_{k - l + 1})) - 1 + 2 = k - (k - l + 1) - 1 + 2 = l - 1 - 1 + 2 = l [/math].

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

Лемма:
Если для графа [math] G [/math] выполнены условия из теоремы и в нем отсутствует цикл длины [math] l [/math], [math] 3 \leqslant l \leqslant n-1 [/math], то количество вершин в графе четное
Доказательство:
[math]\triangleright[/math]

Доказательство будем вести методом от противного.

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

По лемме [math] n [/math] является четным, если в цикле отсутствует цикл длины [math] l [/math]. Тогда верно, что [math] 2|E| = \sum\limits_{i=1}^n deg(v_i) = \sum\limits_{i=1}^{\genfrac{}{}{}{}{n}{2}} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{0}{n^2}{2} [/math], а так как по условию [math] |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} [/math], то [math] |E| = \genfrac{}{}{}{0}{n^2}{4} [/math]. Данное равенство достигается, если верно, что:

Слева направо изображены случаи 1-3. Красным выделены ребра, которые не могут быть в рассматриваемом графе, если в нем присутствуют ребра, выделенные зеленым
  • [math] v_k [/math] лежит на дуге [math] (v_{j + l - 1}, v_{j + l}, v_{j - 1}) [/math]: [math] (v_j, v_k) \in E [/math] и [math](v_{j+1}, v_{k-l+3}) \notin E [/math] или [math] (v_j, v_k) \notin E [/math] и [math](v_{j+1}, v_{k-l+3}) \in E [/math]
  • [math] v_k [/math] лежит на дуге [math] (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) [/math]: [math](v_j, v_k) \in E [/math] и [math](v_{j+1}, v_{k-l+1}) \notin E [/math] или [math](v_j, v_k) \notin E [/math] и [math](v_{j+1}, v_{k-l+1}) \in E [/math]

Пусть [math] G [/math] не [math]K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{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_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}[/math]
[math]\triangleright[/math]

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

  1. [math] k \geqslant \genfrac{}{}{}{}{n}{2} [/math], тогда [math] 2m = \sum\limits_{i=1}^n deg(v_i) \gt = \sum\limits_{i=1}^n k = k n \geqslant \genfrac{}{}{}{0}{n^2}{2} [/math]
  2. [math] k \lt \genfrac{}{}{}{}{n}{2} [/math]. Пусть существует [math] x [/math] вершин, так что их степени равны [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] x [/math] вершин степени [math] k [/math] провести оставшиеся ребра в одну вершину, у которой степень больше, то в графе остенется как минимум [math] n - k - 1 [/math] вершин, степени которых как минимум [math] n - k [/math], поскольку должно выполняться неравенство из теоермы. Тогда можно оценить количество ребер.
    [math] m \geqslant \genfrac{}{}{}{0}{1}{2}((n-k-1)(n-k)+k^2+(k+1)) = \genfrac{}{}{}{0}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{0}{n^2+1}{4} [/math]
Таким образом [math] m \geqslant \genfrac{}{}{}{0}{n^2}{4} [/math] и согласно теореме граф либо панциклический, либо [math]K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}[/math].
[math]\triangleleft[/math]

См. также

Источники информации