Просмотр кода страницы Панциклический граф

[[Файл:Pancyclic octahedron.svg|thumb|Циклы всех возможных длин в графе [[октаэдр]]а показывают, что граф панцикличен.]]
'''Панциклический граф''' — [[Ориентированный граф|ориентированный]] или [[Граф (математика)|неориентированный граф]], который содержит [[Цикл (теория графов)|циклы]] всех возможных длин от трёх до числа [[Вершина (теория графов)|вершин]] графа{{sfn|Bondy|1971}}. Панциклические графы являются обобщением [[Гамильтонов граф|гамильтоновых графов]], графов, которые имеют циклы максимальной возможной длины.

== Определения ==
Граф <math>G</math> с <math>n</math> вершинами является панциклическим, если для любого <math>k</math> в пределах <math>3 \leqslant k \leqslant n</math> граф <math>G</math> содержит цикл длины <math>k</math>{{sfn|Bondy|1971}}. Граф является '''''вершинно панциклическим''''', если для любой вершины <math>v</math> и любого <math>k</math> в тех же пределах граф содержит цикл длины <math>k</math>, содержащий вершину <math>v</math>{{sfn|Randerath, Schiermeyer, Tewes, Volkmann|2002}}. Похожим образом граф является '''''рёберно панциклическим''''', если для любого ребра <math>e</math> и для любого <math>k</math> в тех же пределах он содержит цикл длины <math>v</math>, содержащий ребро <math>e</math>{{sfn|Randerath, Schiermeyer, Tewes, Volkmann|2002}}.

[[Двудольный граф]] не может быть панциклическим, поскольку он не содержит циклы любой нечётной длины, но говорят, что граф является '''''бипанциклическим''''', если он содержит циклы всех чётных длин от 4 до <math>n</math>{{sfn|Schmeichel, Mitchem|1982}}.

== Планарные графы ==
Максимальный [[внешнепланарный граф]] — это граф, образованный из [[Простой многоугольник|простого многоугольника]] на плоскости путём [[Задача о триангуляции многоугольника|триагуляризации]] его внутренности. Любой максимальный внешнепланарный граф является панциклическим, что можно показать индукцией. Внешняя грань графа является циклом с ''n'' вершинами, а удаление любого треугольника, соединённого с остатком графа только одним ребром (лист дерева, которое образует [[двойственный граф]] триангуляризации), образует максимальный внешнепланарный граф с на единицу меньшим числом вершин, а по индукционному предположению этот граф имеет все циклы всех оставшихся длин. Если уделять больше внимания выбору треугольника для удаления, то те же аргументы показывают более строгий результат, что любой максимальный внешнепланарный граф является вершинно панциклическим{{sfn|Li, Corneil, Mendelsohn|2000|loc= Proposition 2.5}}. То же самое верно для графов, которые имеют максимальный внешнепланарный граф в качестве [[Глоссарий теории графов|остовного подграфа]], в частности, для [[Колесо (теория графов)|колёс]].

Максимальный [[планарный граф]] — это планарный граф, в котором все грани, включая внешнюю, являются треугольниками. Максимальный планарный граф является вершинно панциклическим тогда и только тогда, когда он содержит гамильтонов цикл{{sfn|Helden|2007|loc=Corollary 3.78}} — если он не гамильтонов, он определённо не панцикличен, а если он гамильтонов, то внутренность гамильтонова цикла образует внешнюю грань максимального внешнепланарного графа на тех же вершинах и рёбрах, к которой можно применить предыдущие аргументы для внешнепланарных графов{{sfn|Bernhart, Kainen|1979}}. Например, на рисунке{{каком?}}<!--лучше это тогда внести в подпись к тому самому рисунку--> показана панцикличность графа [[октаэдр]]а, гамильтонова максимального планарного графа с шестью вершинами. Более строго, по тем же самым причинам, если максимальный планарный граф имеет цикл длины <math>k</math>, он имеет циклы всех меньших длин{{sfn|Hakimi, Schmeichel|1979}}.

[[Файл:Halin no 8-cycle.svg|thumb|Почти панциклический [[граф Халина]] с циклами всех длин вплоть до ''n'', за исключением длины 8]]
{{Якорь|Почти панциклический граф}}[[Граф Халина|Графы Халина]] являются планарными графами, образованными из планарного рисунка [[Дерево (теория графов)|дерева]], не имеющего вершин степени два, путём добавления цикла, соединяющего листья дерева. Графы Халина не обязательно панцикличны, но они '''''почти панцикличны''''' в том смысле, что отсутствует цикл максимум одной длины. Длина отсутствующего цикла обязательно чётна. Если ни одна из внутренних вершин графа Халина не имеет степень три, то граф обязательно панцикличен{{sfn|Skowrońska|1985}}.

В 1971 году замечено{{sfn|Bondy|1971}}, что много классических условий для существования гамильтонова цикла достаточны также для панцикличности, в связи с чем предположено, что любой 4-связный планарный граф панцикличен, но вскоре было найдено семейство контпримеров{{sfn|Malkevitch|1971}}.

== Турниры ==
[[Турнир (теория графов)|Турнир]] — это направленный граф с одной направленной дугой между любой парой вершин. Интуитивно турнир может быть использован для моделирования [[Круговая система|круговой системы]] путём рисования дуги от победителя к побеждённому для каждой игры в соревновании. Турнир называется [[Компонента сильной связности в орграфе|сильно связным]] или просто сильным тогда и только тогда, когда он не может быть разделён на два непустых подмножества <math>L</math> и <math>W</math> проигравших и выигравших, так что любой участник <math>W</math> побеждает любого участника в <math>L</math>{{sfn|Harary, Moser|1966|loc= Corollary 5b}}. Любой сильный турнир является панциклическим{{sfn|Harary, Moser|1966|loc=Theorem 7}} и вершинно панциклическим{{sfn|Moon|1966|loc=Theorem 1}}. Если турнир [[Регулярный граф|регулярен]] (любой участник имеет то же число выигрышей и проигрышей, что и другие участники), то он является также рёберно панциклическим{{sfn|Alspach|1967}}, однако сильные турниры с четырьмя вершинами не могут быть рёберно панциклическими.

== Графы с большим числом рёбер ==
{{не переведено 5|Теорема Мантеля|||Mantel's theorem}} утверждает, что любой неориентированный граф с <math>n</math> вершинами, имеющий по меньшей мере <math>n^2/4</math> рёбер и не имеющий кратных рёбер и петель, либо содержит треугольник, либо он является [[Полный двудольный граф|полным двудольным графом]] <math>K_{n/2, n/2}</math>. Эту теорему можно усилить — любой неориентированный гамильтонов граф с не менее чем <math>n^2/4</math> рёбрами либо панцикличен, либо это <math>K_{n/2, n/2}</math>{{sfn|Bondy|1971}}.

Существуют гамильтоновы ориентированные графы с <math>n</math> вершинами и с <math>n(n + 1)/2 - 3</math> дугами, не являющиеся панциклическими, но любой гамильтонов ориентированный граф по меньшей мере с <math>n(n + 1)/2 - 1</math> дугами панцикличен. Кроме того, строго связный граф с <math>n</math> вершинами, в котором каждая вершина имеет степень, не меньшую <math>n</math> (входящие и исходящие дуги считаются вместе), либо панцикличен, либо является полным двудольным графом{{sfn|Häggkvist, Thomassen|1976|с= 20–40}}.

== Степени графа ==
Для любого графа <math>G</math> его [[Степень графа|<math>k</math>-я степень]] графа <math>G^k</math> определяется как граф на том же множестве вершин, имеющий ребро между любыми двумя вершинами, расстояние между которыми в <math>G</math> не превосходит <math>k</math>. Если <math>G</math> [[Вершинно k-связный граф|вершинно 2-связен]], то по [[Теорема Фляйшнера|теореме Фляйшнера]] <math>G^2</math> является гамильтоновым графом. Утверждение может быть усилено: граф обязательно будет вершинно панциклическим{{sfnp|Hobbs|1976}}. Более строго, если <math>G^2</math> является гамильтоновым, он также и панцикличен{{sfn|Fleischner|1976}}.

== Вычислительная сложность ==
Проверка графа на панцикличность является [[NP-полная задача|NP-полной]] задачей даже для специального случая [[Вершинно k-связный граф|3-связных]] [[Кубический граф|кубических графов]]. NP-полной задачей является также проверка графа на вершинную панцикличность даже для специального случая [[Полиэдральный граф|полиэдральных графов]]{{sfn|Li, Corneil, Mendelsohn|2000|loc= Theorems 2.3 и 2.4}}. Также NP-полной задачей является проверка [[Степень графа|квадрата графа]] на гамильтоновость, а тем самым и проверка на панцикличность{{sfnp|Underground|1978}}.<!--Напрямую второе из первого не следует! -->

== История ==
Панцикличность впервые исследовали Харари и Мозер в контексте турниров{{sfn|Harary, Moser|1966}}, а также Муун{{sfn|Moon|1966}} и Алпач{{sfn|Alspach|1967}}. Понятие панцикличности получило название от Бонди, который расширил понятие для неориентированных графов{{sfn|Bondy|1971}}.

== Примечания ==
{{примечания|2}}

== Литература ==
{{refbegin|colwidth=30em}}
* {{статья
|автор=Brian Alspach
|ref=Alspach
|выпуск= 2
|издание= Canadian Mathematical Bulletin
|страницы= 283—286
|заглавие= Cycles of each length in regular tournaments
|url= http://cms.math.ca/cmb/v10/p283
|том= 10
|год= 1967
}}.
* {{статья
|автор=Frank Bernhart, Paul C. Kainen
|ref=Bernhart, Kainen
|doi= 10.1016/0095-8956(79)90021-2
|выпуск= 3
|издание= [[Journal of Combinatorial Theory]], Series B
|страницы= 320—331
|заглавие= The book thickness of a graph
|том= 27
|год= 1979
}}.
* {{статья
|автор=J. A. Bondy
|ref=Bondy
|doi= 10.1016/0095-8956(71)90016-5
|выпуск= 1
|издание= [[Journal of Combinatorial Theory]], Series B
|страницы= 80—84
|заглавие= Pancyclic graphs I
|том= 11
|год= 1971
}}.
* {{статья
|автор=H. Fleischner
|ref=Fleischner
|doi= 10.1007/BF01305995
|выпуск= 2
|издание= Monatshefte für Mathematik
|mr= 0427135
|страницы= 125—149
|заглавие= In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts
|том= 82
|год= 1976
}}.
* {{статья
|автор=Roland Häggkvist, Carsten Thomassen
|ref=Häggkvist, Thomassen
|doi= 10.1016/0095-8956(76)90063-0
|выпуск= 1
|издание= [[Journal of Combinatorial Theory]], Series B
|заглавие= On pancyclic digraphs
|том= 20
|год= 1976
}}.
* {{статья
|автор=S. L. Hakimi, E. F. Schmeichel
|ref=Hakimi, Schmeichel
|doi= 10.1002/jgt.3190030108
|издание= Journal of Graph Theory
|страницы= 69—86
|заглавие= On the number of cycles of length ''k'' in a maximal planar graph
|ссылка=https://archive.org/details/sim_journal-of-graph-theory_spring-1979_3_1/page/69
|том= 3
|год= 1979
}}.
* {{статья
|автор=Frank Harary, Leo Moser
|ref=Harary, Moser
|doi= 10.2307/2315334
|выпуск= 3
|издание= [[American Mathematical Monthly]]
|страницы= 231—246
|заглавие= The theory of round robin tournaments
|ссылка=https://archive.org/details/sim_american-mathematical-monthly_1966-03_73_3/page/231
|том= 73
|год= 1966
}}.
* {{книга
 |автор               = Guido Helden
|ref                      = Helden
|издательство = Rheinisch-Westfälischen Technischen Hochschule Aachen
|заглавие         = Hamiltonicity of maximal planar graphs and planar triangulations
|url                      = http://darwin.bth.rwth-aachen.de/opus3/volltexte/2007/1949/pdf/Helden_Guido.pdf
|серия               = Dissertation
|год                   = 2007
|ссылка= https://web.archive.org/web/20110718172008/http://darwin.bth.rwth-aachen.de/opus3/volltexte/2007/1949/pdf/Helden_Guido.pdf
}}.
* {{статья
|автор=Arthur M. Hobbs
|ref=Hobbs
|doi= 10.1016/0095-8956(76)90061-7
|выпуск= 1
|издание= [[Journal of Combinatorial Theory]]
|mr= 0416980
|страницы= 1—4
|серия= Series B
|заглавие= The square of a block is vertex pancyclic
|том= 20
|год= 1976
}}.
* {{статья
|автор=Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn
|ref=Li, Corneil, Mendelsohn
|doi= 10.1016/S0166-218X(99)00163-8
|выпуск= 3
|издание= Discrete Applied Mathematics
|страницы= 219—225
|заглавие= Pancyclicity and NP-completeness in planar graphs
|том= 98
|год= 2000
}}.
* {{книга
|автор=Joseph Malkevitch
|ref=Malkevitch
|вклад= On the lengths of cycles in planar graphs
|doi= 10.1007/BFb0059437
|страницы= 191—195
|издательство= Springer-Verlag
|серия= Lecture Notes in Mathematics
|заглавие= Recent Trends in Graph Theory
|том= 186
|год= 1971
}}.
* {{статья
|автор=J. W. Moon
|ref=Moon
|выпуск= 3
|издание= Canadian Mathematical Bulletin
|страницы= 297—301
|заглавие= On subtournaments of a tournament
|url= http://cms.math.ca/cmb/v9/p297
|doi= 10.4153/CMB-1966-038-7
|том= 9
|год= 1966
}}.
* {{статья
|автор=Bert Randerath, Ingo Schiermeyer, Meike Tewes, Lutz Volkmann
|ref=Randerath, Schiermeyer, Tewes, Volkmann
|doi= 10.1016/S0166-218X(01)00292-X
|выпуск= 1—3
|издание= Discrete Applied Mathematics
|страницы= 219—237
|заглавие= Vertex pancyclic graphs
|том= 120
|год= 2002
}}.
* {{статья
|автор=Edward Schmeichel, John Mitchem
|ref=Schmeichel, Mitchem
|doi= 10.1002/jgt.3190060407
|выпуск= 4
|издание= Journal of Graph Theory
|страницы= 429—439
|заглавие= Bipartite graphs with cycles of all even lengths
|ссылка=https://archive.org/details/sim_journal-of-graph-theory_winter-1982_6_4/page/429
|том= 6
|год= 1982
}}.
* {{книга
|автор=Mirosława Skowrońska
|ref=Skowrońska
|вклад= The pancyclicity of Halin graphs and their exterior contractions
|ответственный=Brian R. Alspach, Christopher D. Godsil
|страницы= 179—194
|издательство= Elsevier Science Publishers B.V.
|серия= Annals of Discrete Mathematics
|заглавие= Cycles in Graphs
|том= 27
|год= 1985
}}.
* {{статья
|автор=Paris Underground
|doi= 10.1016/0012-365X(78)90164-4
|выпуск= 3
|издание= [[Discrete Mathematics]]
|mr= 522906
|страницы= 323
|заглавие= On graphs with Hamiltonian squares
|том= 21
|год= 1978
|ref=Underground
}}.
{{refend}}

== Ссылки ==
* {{mathworld|title=Pancyclic Graph|urlname=PancyclicGraph}}

{{rq|checktranslate|style}}

[[Категория:Семейства графов]]
[[Категория:Гамильтоновы пути и циклы]]