Изменения

|definition='''Панциклический граф''' (англ. ''pancyclic graph'') {{---}} граф, в котором есть циклы всех длин от <tex> 3 </tex> до <tex> n </tex> . Если граф содержит все циклы от <tex> r </tex> до <tex> n </tex>, то такой граф называют <tex> r </tex>-панциклическим.

{{Определение|definition='''Предпосылки к теореме<tex> r </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 r </tex> вершинах, у которого количество ребер не меньше -pancyclic graph'') {{---}} граф содержит все циклы от <tex> n^2 / 4 r </tex>, либо содержит треуголник либо является до <tex>K_{n / 2, n / 2}</tex>.}}

Пусть <tex>G(V, E) </tex> {{---}} гамильтонов граф, <tex>|V| = n, |E| \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex>.

#<tex> G </tex> = <tex>K_{\genfrac{}{}{}{}{n / }{2}, \genfrac{}{}{}{}{n / }{2}}</tex>

[[Файл: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> C=v_1 v_2 v_3 3 \leqslant l \ldots v_n leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл в графе , длина которого равна <tex> G n </tex>). Для простоты расположим Рассмотрим две соседние вершины <tex> C v_j v_{j+1} </tex> на окружности.и вместе с ними рассмотрим следующие пары:

Пусть в графе нет цикла длины Для <tex> l k</tex>таких, что <tex> v_k </tex> лежит на дуге <tex> 3 \leqslant (v_{j + l \leqslant n-1 }, v_{j + l}, v_{j -1}) </tex> рассмотрим пары (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n v_j, v_k</tex>). Рассмотрим две соседние вершины и (<tex> v_i v_{ij+1}, v_{k-l+3} </tex> и вместе с ними рассмотрим следующие пары: )

Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1 \leqslant k \leqslant 2}, v_{j + 3}, v_{j + l - 2 }) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+31}</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 \leqslant k \leqslant }, 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>.

При добавлении таких пар ребер {{Лемма|statement=Если для графа <tex> G </tex> выполнены условия из теоремы и в графе появляется нем отсутствует цикл длины <tex> l </tex>, а значить <tex> 3 \leqslant l \leqslant n-1 </tex>, то количество вершин в графе четное|proof= Доказательство будем вести методом от противного.*Пусть <tex> G 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> n </tex> {{---}} четно. Пусть По лемме <tex> n </tex> является нечетнымчетным, тогда из рассуждений выше существует вершина если в цикле отсутствует цикл длины <tex> v_x l </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> является четным. Тогда верно, что <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{}{}{}{0}{n^2}{2} </tex>, а так как по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2/}{4 } </tex>, то <tex> |E| = \genfrac{}{}{}{0}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:

[[Файл:Circle 3.jpg|800px|right]]*<tex> j + l - |thumb|Слева направо изображены случаи 1 \leqslant k \leqslant j + l - 2 </tex> : <tex> (v_j3. Красным выделены ребра, которые не могут быть в рассматриваемом графе, v_k) \in E </tex> и <tex>(v_{j+1}если в нем присутствуют ребра, v_{k-l+3}) \notin E </tex>выделенные зеленым]]

*<tex> v_k </tex> лежит на дуге <tex> (v_{j + 2 \leqslant k \leqslant l - 1}, v_{j + l }, v_{j - 2 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}) \notin in E </tex>

Пусть *<tex> G v_k </tex> не лежит на дуге <tex> K_(v_{n/j + 2}, v_{j + 3}, n/v_{j + l - 2} ) </tex>, тогда существует такое четное число : <tex> k </tex>(v_j, что в графе <tex> G v_k) \in E </tex> существует ребро и <tex> (v_j, v_{j+1}, v_{k-l+1}) \notin E </tex>. Докажем, что в таком случае существует ребро или <tex> (v_j, v_{j+2}v_k) \in notin E </tex>. Пусть это не так и минимальное четное <tex> k </tex>, что <tex> \exists (v_j, v_{j+1}, v_{k-l+1}) \in E </tex> больше двух, т.е. <tex> k \geqslant 4 </tex>. Тогда существует три случая:

# Пусть <tex> 4 \leqslant k \leqslant n - l G </tex> <br> не <tex> (v_j, v_K_{\genfrac{}{}{j+k}) \in E \Rightarrow (v_{j+1}, v_{j+k+l-3n}) \notin E \Rightarrow (v_{j+2}, v_\genfrac{}{}{}{}{j+kn}) \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 G </tex> <br> существует ребро <tex> (v_j, v_{j+k}) \in E \Rightarrow </tex>, то есть существует цикл нечетной длины. Докажем, что в таком случае существует ребро <tex> (v_{j-1}v_j, 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> exists (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 geqslant 4 </tex> - снова проиворечие с минимальностью выбранного k . Тогда существует три случая:

# <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> {{- --}} панциклический.

|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>K_{\genfrac{}{}{}{}{n / }{2}, \genfrac{}{}{}{}{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 \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(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}{1n^2}{24}((n-k-1)(n-k)+k^2+k+1) = </tex> и согласно теореме граф либо панциклический, либо <tex>K_{\genfrac{}{}{}{}{1n}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant , \genfrac{}{}{}{}{n^}{2+1}{4} </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]