112
правок
Изменения
добавлена лемма о четности n
== Основные определения ==
{{Определение
|definition='''Панциклический граф''' (англ. ''pancyclic graph'') {{---}} граф, в котором есть циклы всех длин от <tex> 3 </tex> до <tex> n </tex> . Если граф содержит все циклы от <tex> r </tex> до <tex> n </tex>, то такой граф называют <tex> r </tex>-панциклическим.
}}
{{Определение
|definition='''<tex> r </tex>-панциклический граф''' (англ. ''<tex> r </tex>-pancyclic graph'') {{---}} граф содержит все циклы от <tex> r </tex> до <tex> n </tex>.
}}
== Основная теорема ==
{{Теорема
|about=J. A. Bondy
|statement=
Пусть <tex>G(V, E) </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex>.
Тогда верно одно из двух утверждений:
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex> = <tex>K_{\genfrac{}{}{}{}{n / }{2}, \genfrac{}{}{}{}{n / }{2}}</tex>
|proof=
[[Файл: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> v_k </tex> лежит на дуге <tex> (v_{j + 2 \leqslant k \leqslant }, 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_{\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> 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> 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> {{---}} панциклический.
}}
=== Следствие ==={{ТеоремаУтверждение|aboutid =Schmeichel & Hakimistatement|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>K_{\genfrac{}{}{}{}{n}{2}, \genfrac{}{}{}{}{n}{2}}</tex>|Vproof=По [[Теорема Оре| = nтеореме Оре]] <tex> G </tex> {{---}} гамильтонов граф. Покажем, v_1 v_2 v_3 что <tex> m \ldots v_n v_1 geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>. Пусть <tex> k </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 < \genfrac{}{}{}{}{n}{2} </tex>. Пусть существует <tex> x </tex> вершин, так что их степени равны <tex> k </tex>, тогда они все должны быть связаны, для которого выполняется неравенство так как иначе мы получим противоречие с утверждением теоремы <tex> \forall (u, v) \notin E : deg(v_1u) + deg(v_nv) \geqslant n </tex>. Понятно, что <tex> x \leqslant k + 1 </tex>, но так как граф является гамильтоновым, то он связен, а значит <tex> x < k + 1 </tex>. Несложно заметить, что если из всех <tex> x </tex> вершин степени <tex> k </tex> провести оставшиеся ребра в одну вершину, у которой степень больше, то в графе остенется как минимум <tex> n - k - 1 <br/tex>Тогда вершин, степени которых как минимум <tex> G n - k </tex> , поскольку должно выполняться неравенство из теоермы. Тогда можно оценить количество ребер. <br> <tex> m \geqslant \genfrac{}{}{}{0}{1}{2}((n-k-1)(n-k)+k^2+(k+1)) = \genfrac{}{}{}{0}{1}{2} панциклический граф, двудольный граф или граф, в котором нет только цикла длины <tex>(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>.
}}
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Обходы графов]]
== Ссылки Источники информации ==* [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* J]* [https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf Д.В.AКарпов {{---}} Теория графов. Bondy]