Панциклічний граф

Панциклі́чний граф — орієнтований або неорієнтований граф, який містить цикли всіх можливих довжин від трьох до числа вершин графа. Панциклічні графи є узагальненням гамільтонових графів, графів, які мають цикли найбільшої можливої довжини.

Цикли всіх можливих довжин у графі октаедр показують, що граф панциклічний

Визначення

Граф ${\displaystyle G}$ з ${\displaystyle n}$ вершинами є панциклічним, якщо для будь-якого ${\displaystyle k}$ в межах ${\displaystyle 3\leqslant k\leqslant n}$ граф ${\displaystyle G}$ містить цикл довжини ${\displaystyle k}$. Граф є вершинно панциклічним, якщо для будь-якої вершини ${\displaystyle v}$ і будь-якого ${\displaystyle k}$ в тих самих межах граф містить цикл довжини ${\displaystyle k}$, що містить вершину ${\displaystyle v}$. Схожим чином граф є реберно панциклічним, якщо для будь-якого ребра ${\displaystyle e}$ і для будь-якого ${\displaystyle k}$ в тих самих межах він містить цикл довжини ${\displaystyle v}$, що містить ребро ${\displaystyle e}$.

Двочастинний граф не може бути панциклічним, оскільки він не містить циклів будь-якої непарної довжини, але кажуть, що граф є біпанциклічним, якщо він містить цикли всіх парних довжин від 4 до ${\displaystyle n}$.

Планарні графи

Максимальний зовніпланарний граф — це граф, утворений із простого многокутника на площині шляхом тріангуляції його внутрішності. Будь-який максимальний зовніпланарний граф є панциклічним, що можна показати індукцією. Зовнішня грань графа є циклом з n вершинами, а видалення будь-якого трикутника, з'єднаного із рештою графа тільки одним ребром (листок дерева, яке утворює двоїстий граф тріангуляції), утворює максимальний зовніпланарний граф з на одиницю меншим числом вершин, а за індукційним припущенням цей граф має всі цикли всіх довжин, що залишилися. Якщо приділяти більше уваги вибору трикутника для видалення, то ті самі аргументи показують строгіший результат, що будь-який максимальний зовніпланарний граф є вершинно панциклічним. Те ж саме істинне для графів, які мають максимальний зовніпланарний граф як кістяковий підграф, зокрема, для колеса.

Максимальний планарний граф — це планарний граф, у якому всі грані, включно із зовнішньою, є трикутниками. Максимальний планарний граф є вершинно панциклічним тоді й лише тоді, коли він містить гамільтонів цикл — якщо він не гамільтонів, він безумовно не панциклічний, а якщо він гамільтонів, то внутрішність гамильтонового циклу утворює зовнішню межу максимального зовнішпланарного графа на тих самих вершинах і ребрах, до якої можна застосувати попередні аргументи для зовніпланарних графів. Наприклад, на малюнку вгорі показано панциклічність графа октаедра, гамільтонового максимального планарного графа з шістьма вершинами. Строгіше, з тих самих причин, якщо максимальний планарний граф має цикл довжини ${\displaystyle k}$, то він має цикли всіх менших довжин.

Майже панциклічний граф Халіна з циклами всіх довжин аж до n, за винятком довжини 8

Графи Халіна є планарними графами, утвореними з планарного малюнка дерева, яке має вершин степеня два, доданням циклу, що з'єднує листки дерева. Графи Халіна не обов'язково панциклічні, але вони майже панциклічні в тому сенсі, що відсутній цикл максимум однієї довжини. Довжина відсутнього циклу обов'язково парна. Якщо жодна зі внутрішніх вершин графа Халіна не має степеня три, то граф обов'язково панциклічний.

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

Турніри

Турнір — це напрямлений граф з однією напрямленою дугою між будь-якою парою вершин. Інтуїтивно турнір можна використати для моделювання кругової системи малюванням дуги від переможця до переможеного для кожної гри в змаганні. Турнір називають сильно зв'язним або просто сильним тоді й лише тоді, коли його не можна розділити на дві непорожні підмножини ${\displaystyle L}$ і ${\displaystyle W}$ тих, хто програв і виграв, так, що будь-який учасник ${\displaystyle W}$ перемагає будь-якого учасника в ${\displaystyle L}$. Будь-який сильний турнір є панциклічним і вершинно панциклічним. Якщо турнір регулярний (будь-який учасник має таке ж число виграшів і програшів, що й інші учасники), то він є також реберно панциклічним, однак сильні турніри з чотирма вершинами не можуть бути реберно панциклічними.

Графи з великим числом ребер

Теорема Мантеля стверджує, що будь-який неорієнтований граф із ${\displaystyle n}$ вершинами, що має принаймні ${\displaystyle n^{2}/4}$ ребер і не має кратних ребер і петель, або містить трикутник, або він є повним двочастинним графом ${\displaystyle K_{n/2,n/2}}$. Цю теорему можна посилити — будь-який неорієнтований гамільтонів граф з не менш ніж ${\displaystyle n^{2}/4}$ ребрами або панциклічний, або це ${\displaystyle K_{n/2,n/2}}$.

Існують гамільтонові орієнтовані графи з ${\displaystyle n}$ вершинами і з ${\displaystyle n(n+1)/2-3}$ дугами, які не є панциклічними, але будь-який гамільтонів орієнтований граф принаймні з ${\displaystyle n(n+1)/2-1}$ дугами панциклічний. Крім того, строго зв'язний граф з ${\displaystyle n}$ вершинами, в якому кожна вершина має степінь, не менший від ${\displaystyle n}$ (вхідні та вихідні дуги рахуються разом), або панциклічний, або є повним двочастинним графом.

Степені графа

Для будь-якого графа ${\displaystyle G}$ його ${\displaystyle k}$-й степінь графа ${\displaystyle G^{k}}$ визначається як граф на тій самій множині вершин, що має ребро між будь-якими двома вершинами, відстань між якими в ${\displaystyle G}$ не перевищує ${\displaystyle k}$. Якщо ${\displaystyle G}$ вершинно 2-зв'язний, то за теоремою Фляйшнера ${\displaystyle G^{2}}$ є гамільтоновим графом. Твердження можна посилити: граф обов'язково буде вершинно панциклічним. Строгіше, якщо ${\displaystyle G^{2}}$ є гамільтоновим, він також і панциклічний.

Обчислювальна складність

Перевірка графа на панциклічність є NP-повною задачею навіть для окремого випадку 3-зв'язних кубічних графів. NP-повною задачею є також перевірка графа на вершинну панциклічність навіть для окрмого випадку поліедральних графів. Також NP-повною задачею є перевірка квадрата графа на гамільтоновість, а тим самим і перевірка на панциклічність.

Історія

Панциклічність уперше досліджували Харарі і Мозер у контексті турнірів, а також Муун і Алпач. Назву поняттю панциклічності дав Бонді, який розширив поняття для неорієнтованих графів.

Примітки

1. Bondy, 1971.
2. Randerath, Schiermeyer, Tewes, Volkmann, 2002.
3. Schmeichel, Mitchem, 1982.
4. Li, Corneil, Mendelsohn, 2000, Proposition 2.5.
5. Helden, 2007, Corollary 3.78.
6. Bernhart, Kainen, 1979.
7. Hakimi, Schmeichel, 1979.
8. Skowrońska, 1985.
9. Malkevitch, 1971.
10. Harary, Moser, 1966, Corollary 5b.
11. Harary, Moser, 1966, Theorem 7.
12. Moon, 1966, Theorem 1.
13. Alspach, 1967.
14. Häggkvist, Thomassen, 1976, с. 20–40.
15. Hobbs, (1976).
16. Fleischner, 1976.
17. Li, Corneil, Mendelsohn, 2000, Theorems 2.3 и 2.4.
18. Underground, (1978).
19. Harary, Moser, 1966.
20. Moon, 1966.

Література

• Brian Alspach. Cycles of each length in regular tournaments // Canadian Mathematical Bulletin. — 1967. — Т. 10, вип. 2 (16 червня). — С. 283—286..
• Frank Bernhart, Paul C. Kainen. The book thickness of a graph // , Series B. — 1979. — Т. 27, вип. 3 (16 червня). — С. 320—331. — DOI:10.1016/0095-8956(79)90021-2..
• J. A. Bondy. Pancyclic graphs I // , Series B. — 1971. — Т. 11, вип. 1 (16 червня). — С. 80—84. — DOI:10.1016/0095-8956(71)90016-5..
• H. Fleischner. In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts // Monatshefte für Mathematik. — 1976. — Т. 82, вип. 2 (16 червня). — С. 125—149. — DOI:10.1007/BF01305995..
• Roland Häggkvist, Carsten Thomassen. On pancyclic digraphs // , Series B. — 1976. — Т. 20, вип. 1 (16 червня). — DOI:10.1016/0095-8956(76)90063-0..
• S. L. Hakimi, E. F. Schmeichel. On the number of cycles of length k in a maximal planar graph // Journal of Graph Theory. — 1979. — Т. 3 (16 червня). — С. 69—86. — DOI:10.1002/jgt.3190030108..
• Frank Harary, Leo Moser. The theory of round robin tournaments // American Mathematical Monthly. — 1966. — Т. 73, вип. 3 (16 червня). — С. 231—246. — DOI:10.2307/2315334..
• Guido Helden. . — Rheinisch-Westfälischen Technischen Hochschule Aachen, 2007. — (Dissertation).
• Arthur M. Hobbs. The square of a block is vertex pancyclic // . — 1976. — Т. 20, вип. 1 (16 червня). — С. 1—4. — (Series B). — DOI:10.1016/0095-8956(76)90061-7..
• Ming-Chu Li, Derek G. Corneil, Eric Mendelsohn. Pancyclicity and NP-completeness in planar graphs // Discrete Applied Mathematics. — 2000. — Т. 98, вип. 3 (16 червня). — С. 219—225. — DOI:10.1016/S0166-218X(99)00163-8..
• Joseph Malkevitch. Recent Trends in Graph Theory. — Springer-Verlag, 1971. — Т. 186. — С. 191—195. — (Lecture Notes in Mathematics) — DOI:10.1007/BFb0059437..
• J. W. Moon. On subtournaments of a tournament // Canadian Mathematical Bulletin. — 1966. — Т. 9, вип. 3 (16 червня). — С. 297—301. — DOI:10.4153/CMB-1966-038-7..
• Bert Randerath, Ingo Schiermeyer, Meike Tewes, Lutz Volkmann. Vertex pancyclic graphs // Discrete Applied Mathematics. — 2002. — Т. 120, вип. 1—3 (16 червня). — С. 219—237. — DOI:10.1016/S0166-218X(01)00292-X..
• Edward Schmeichel, John Mitchem. Bipartite graphs with cycles of all even lengths // Journal of Graph Theory. — 1982. — Т. 6, вип. 4 (16 червня). — С. 429—439. — DOI:10.1002/jgt.3190060407..
• Mirosława Skowrońska. Cycles in Graphs / Brian R. Alspach, Christopher D. Godsil. — Elsevier Science Publishers B.V, 1985. — Т. 27. — С. 179—194. — (Annals of Discrete Mathematics).
• Paris Underground. On graphs with Hamiltonian squares // . — 1978. — Т. 21, вип. 3 (16 червня). — С. 323. — DOI:10.1016/0012-365X(78)90164-4..

Посилання

• Weisstein, Eric W. Панциклічний граф(англ.) на сайті Wolfram MathWorld.