Панциклический граф — различия между версиями
Строка 56: | Строка 56: | ||
# <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> 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> 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> 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 n^2/4 </tex> и согласно теореме граф либо панциклический, либо <tex>K_{n / 2, n / 2}</tex>. | |
}} | }} | ||
Версия 20:23, 11 декабря 2017
Определение: |
Панциклический граф (англ. pancyclic graph) — граф, в котором есть циклы всех длин от | до . Если граф содержит все циклы от до , то такой граф называют -панциклическим.
Предпосылки к теореме. Теорема Мантела(частный случай теоремы Турана) утверждает, что для любого граф на вершинах, у которого количество ребер не меньше , либо содержит треугольник либо является .
Теорема (J. A. Bondy): |
Тогда верно одно из двух утверждений:
|
Доказательство: |
Обозначим как гамильтонов цикл в графе . Для простоты расположим на окружности.Также подразумевается, что все индексы при вершинах берутся по модулю, т.е. .Пусть в графе нет цикла длины , (по условию в графе существует гамильтонов цикл, длина которого равна ). Рассмотрим две соседние вершины и вместе с ними рассмотрим следующие пары:Для таких, что лежит на дуге рассмотрим пары ( ) и ( ) (см. рисунок слева)Для таких, что лежит на дуге рассмотрим пары ( ) и ( ) (см. рисунок справа)При добавлении таких пар ребер в графе появляется цикл длины , а значить в может входить максимум одно ребро из таких пар. Тогда можно утверждать, что .Докажем методом от противного, что — четно. Пусть является нечетным, тогда из рассуждений выше существует вершина , для которое верно, что . Пусть это не так, тогда , значит , то есть мы получили противоречие с тем, что . Без потери общности пусть . Рассмотрим , то есть , но по условию — получили противоречие. Таким образом является четным. Тогда верно, что , а так как по условию , то . Данное равенство достигается, если верно, что:
Пусть не , тогда существует такое четное число , что в графе существует ребро , т.е. существует цикл нечетной длины. Докажем, что в таком случае существует ребро . Пусть это не так и минимальное четное , что больше двух, т.е. . Тогда существует три случая:
|
Утверждение: |
Тогда верно одно из двух утверждений:
|
По теореме Оре — гамильтонов граф. Покажем, что . Пусть — минимальная степень вершины в графе.
|