Перегляд вихідного коду сторінки Панциклічний граф

[[Файл:Pancyclic_octahedron.svg|міні|Цикли всіх можливих довжин у графі [[октаедр]] показують, що граф панциклічний]]
'''Панциклі́чний граф'''&nbsp;— [[Орієнтований граф|орієнтований]] або [[Граф (математика)|неорієнтований граф]], який містить [[Цикл (теорія графів)|цикли]] всіх можливих довжин від трьох до числа [[Вершина (теорія графів)|вершин]] графа{{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}}.

== Планарні графи ==
Максимальний [[зовніпланарний граф]]&nbsp;— це граф, утворений із [[Простий многокутник|простого многокутника]] на площині шляхом [[Тріангуляція многокутника|тріангуляції]] його внутрішності. Будь-який максимальний зовніпланарний граф є панциклічним, що можна показати індукцією. Зовнішня грань графа є циклом з ''n'' вершинами, а видалення будь-якого трикутника, з'єднаного із рештою графа тільки одним ребром (листок дерева, яке утворює [[двоїстий граф]] тріангуляції), утворює максимальний зовніпланарний граф з на одиницю меншим числом вершин, а за індукційним припущенням цей граф має всі цикли всіх довжин, що залишилися. Якщо приділяти більше уваги вибору трикутника для видалення, то ті самі аргументи показують строгіший результат, що будь-який максимальний зовніпланарний граф є вершинно панциклічним{{Sfn|Li, Corneil, Mendelsohn|2000|місце=Proposition 2.5}}. Те ж саме істинне для графів, які мають максимальний зовніпланарний граф як [[Словник термінів теорії графів|кістяковий підграф]], зокрема, для [[Колесо (теорія графів)|колеса]].

Максимальний [[планарний граф]]&nbsp;— це планарний граф, у якому всі грані, включно із зовнішньою, є трикутниками. Максимальний планарний граф є вершинно панциклічним [[тоді й лише тоді]], коли він містить гамільтонів цикл{{Sfn|Helden|2007|місце=Corollary 3.78}}&nbsp;— якщо він не гамільтонів, він безумовно не панциклічний, а якщо він гамільтонів, то внутрішність гамильтонового циклу утворює зовнішню межу максимального зовнішпланарного графа на тих самих вершинах і ребрах, до якої можна застосувати попередні аргументи для зовніпланарних графів{{Sfn|Bernhart, Kainen|1979}}. Наприклад, на малюнку вгорі показано панциклічність графа [[октаедр]]а, гамільтонового максимального планарного графа з шістьма вершинами. Строгіше, з тих самих причин, якщо максимальний планарний граф має цикл довжини <math>k</math>, то він має цикли всіх менших довжин{{Sfn|Hakimi, Schmeichel|1979}}.
[[Файл:Halin_no_8-cycle.svg|міні|Майже панциклічний [[граф Халіна]] з циклами всіх довжин аж до ''n'', за винятком довжини 8]]
{{Якір|Майже панциклічний граф}}[[Граф Халіна|Графи Халіна]] є планарними графами, утвореними з планарного малюнка [[Дерево (теорія графів)|дерева]], яке має вершин степеня два, доданням циклу, що з'єднує листки дерева. Графи Халіна не обов'язково панциклічні, але вони '''''майже панциклічні''''' в тому сенсі, що відсутній цикл максимум однієї довжини. Довжина відсутнього циклу обов'язково парна. Якщо жодна зі внутрішніх вершин графа Халіна не має степеня три, то граф обов'язково панциклічний{{Sfn|Skowrońska|1985}}.

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

== Турніри ==
[[Турнір (теорія графів)|Турнір]]&nbsp;— це напрямлений граф з однією напрямленою дугою між будь-якою парою вершин. Інтуїтивно турнір можна використати для моделювання [[Кругова система|кругової системи]] малюванням дуги від переможця до переможеного для кожної гри в змаганні. Турнір називають [[Компонента сильної зв'язності графа|сильно зв'язним]] або просто сильним [[тоді й лише тоді]], коли його не можна розділити на дві непорожні підмножини <math>L</math> і <math>W</math> тих, хто програв і виграв, так, що будь-який учасник <math>W</math> перемагає будь-якого учасника в <math>L</math>{{Sfn|Harary, Moser|1966|місце=Corollary 5b}}. Будь-який сильний турнір є панциклічним{{Sfn|Harary, Moser|1966|місце=Theorem 7}} і вершинно панциклічним{{Sfn|Moon|1966|місце=Theorem 1}}. Якщо турнір [[Регулярний граф|регулярний]] (будь-який учасник має таке ж число виграшів і програшів, що й інші учасники), то він є також реберно панциклічним{{Sfn|Alspach|1967}}, однак сильні турніри з чотирма вершинами не можуть бути реберно панциклічними.

== Графи з великим числом ребер ==
[[Теорема Мантеля]] стверджує, що будь-який неорієнтований граф із <math>n</math> вершинами, що має принаймні <math>n^2/4</math> ребер і не має кратних ребер і петель, або містить трикутник, або він є [[Повний дводольний граф|повним двочастинним графом]] <math>K_{n/2, n/2}</math>. Цю теорему можна посилити&nbsp;— будь-який неорієнтований гамільтонів граф з не менш ніж <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|місце=Theorems 2.3 и 2.4}}. Також NP-повною задачею є перевірка [[Степінь графа|квадрата графа]] на гамільтоновість, а тим самим і перевірка на панциклічність{{Sfnp|Underground|1978}}.

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

== Примітки ==
{{Reflist|2}}

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

== Посилання ==
* {{MathWorld|title=Панциклічний граф|urlname=PancyclicGraph}}
{{Бібліоінформація}}
[[Категорія:Гамільтонові шляхи та цикли]]
[[Категорія:Види графів]]