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

Поделись знанием:
Перейти к: навигация, поиск

Панциклический граф — ориентированный или неориентированный граф, который содержит циклы всех возможных длин от трёх до числа вершин графа[1]. Панциклические графы являются обобщением гамильтоновых графов, графов, которые имеют циклы максимальной возможной длины.

Определения

Граф <math>G</math> с <math>n</math> вершинами является панциклическим, если для любого <math>k</math> в пределах <math>3 \leqslant k \leqslant n</math> граф <math>G</math> содержит цикл длины <math>k</math>[1]. Граф является вершинно-панциклическим, если для любой вершины <math>v</math> и любого <math>k</math> в тех же пределах граф содержит цикл длины <math>k</math>, содержащий вершину <math>v</math>[2]. Похожим образом граф является рёберно-панциклическим, если для любого ребра <math>e</math> и для любого <math>k</math> в тех же пределах он содержит цикл длины <math>v</math>, содержащий ребро <math>e</math>[2].

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

Планарные графы

Максимальный внешнепланарный граф — это граф, образованный из простого многоугольника[en] на плоскости путём триагуляризации его внутренности. Любой максимальный внешнепланарный граф является панциклическим, что можно показать индукцией. Внешняя грань графа является циклом с n вершинами, а удаление любого треугольника, соединённого с остатком графа только одним ребром (лист дерева, которое образует двойственный граф триангуляризации), образует максимальный внешнепланарный граф с на единицу меньшим числом вершин, а по индукционному предположению этот граф имеет все циклы всех оставшихся длин. Если уделять больше внимания выбору треугольника для удаления, то те же аргументы показывают более строгий результат, что любой максимальный внешнепланарный граф является вершинно-панциклическим[4]. То же самое верно для графов, которые имеют максимальный внешнепланарный граф в качестве остовного подграфа, в частности, для колёс.

Максимальный планарный граф — это планарный граф, в котором все грани, включая внешнюю, являются треугольниками. Максимальный планарный граф является вершинно-панциклическим тогда и только тогда, когда он содержит гамильтонов цикл[5] — если он не гамильтонов, он определённо не панцикличен, а если он гамильтонов, то внутренность гамильтонова цикла образует максимальный внешнепланарный граф на тех же вершинах, к которой можно применить предыдущие аргумены для внешнепланарных графов[6]. Например, на рисунке[каком?] показана панцикличность графа октаэдра, гамильтонова максимального планарного графа с шестью вершинами. Более строго, по тем же самым причинам, если максимальный планарный граф имеет цикл длины <math>k</math>, он имеет циклы всех меньших длин[7].

Графы Халина являются планарными графами, образованными из планарного рисунка дерева, не имеющего вершин степени два, путём добавления цикла, соединяющего листья дерева. Графы Халина не обязательно панцикличны, но они почти панцикличны в том смысле, что отсутствует цикл максимум одной длины. Длина отсутствующего цикла обязательно чётна. Если ни одна из внутренних вершин графа Халина не имеет степень три, то граф обязательно панцикличен[8].

В 1971 году замечено[1], что много классических условий для существования гамильтонова цикла достаточны также для панцикличности, в связи с чем предположено, что любой 4-связный планарный граф панцикличен, но вскоре было найдено семейство контпримеров[9].

Турниры

Турнир — это направленный граф с одной направленной дугой между любой парой вершин. Интуитивно турнир может быть использован для моделирования круговой системы путём рисования дуги от победителя к побеждённому для каждой игры в соревновании. Турнир называется сильно связным или просто сильным тогда и только тогда, когда он не может быть разделён на два непустых подмножества <math>L</math> и <math>W</math> проигравших и выигравших, так что любой участник <math>W</math> побеждает любого участника в <math>L</math>[10]. Любой сильный турнир является панциклическим[11] и вершинно-панциклическим[12]. Если турнир регулярен (любой участник имеет то же число выигрышей и проигрышей, что и другие участники), то он является также рёберно-панцикличным[13], однако сильные турниры с четырьмя вершинами не могут быть рёберно-панциклическими.

Графы с большим числом рёбер

Теорема Мантеля[en] утверждает, что любой неориентированный граф с <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>[1].

Существуют гамильтоновы ориентированные графы с <math>n</math> вершинами и с <math>n(n + 1)/2 - 3</math> дугами, не являющиеся панциклическими, но любой гамильтонов ориентированный граф по меньшей мере с <math>n(n + 1)/2 - 1</math> дугами панцикличен. Кроме того, строго связный граф с <math>n</math> вершинами, в котором каждая вершина имеет степень, не меньшую <math>n</math> (входящие и исходящие дуги считаются вместе), либо панцикличен, либо является полным двудольным графом[14].

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

Для любого графа <math>G</math> его <math>k</math>-ая степень[en] графа <math>G^k</math> определяется как граф на том же множестве вершин, имеющий ребро между любыми двумя вершинами, расстояние между которыми в <math>G</math> не превосходит <math>k</math>. Если <math>G</math> вершинно 2-связен, то по теореме Фляйшнера <math>G^2</math> является гамильтоновым графом. Утверждение может быть усилено: граф обязательно будет вершинно-панциклическим[15]. Более строго, если <math>G^2</math> является гамильтоновым, он также и панцикличен[16].

Вычислительная сложность

Проверка, является ли граф панциклическим, является NP-полной задачей даже для специального случая 3-связных кубических графов. NP-полной задачей является также проверка, является ли граф вершинно-панциклическом даже для специального случая полиэдральных графов[17]. Также NP-полной задачей является проверка, является ли квадрат графа[en] гамильтоновым, а тем самым и проверка, является ли он панциклическим[18].

История

Панцикличность впервые исследовали Харари и Мозер в контексте турниров[19], а также Муун[20] и Алпач[13]. Понятие панцикличности получило название от Бонди, который расширил понятие для неориентированных графов[1].

Примечания

  1. ↑ 1 2 3 4 5 Bondy, 1971.
  2. ↑ 1 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. ↑ 1 2 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. — С. 283–286..
  • Frank Bernhart, Paul C. Kainen The book thickness of a graph // Journal of Combinatorial Theory, Series B. — 1979. — Т. 27, вып. 3. — С. 320–331. — DOI:10.1016/0095-8956(79)90021-2..
  • J. A. Bondy Pancyclic graphs I // Journal of Combinatorial Theory, Series B. — 1971. — Т. 11, вып. 1. — С. 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. — С. 125–149. — DOI:10.1007/BF01305995..
  • Roland Häggkvist, Carsten Thomassen On pancyclic digraphs // Journal of Combinatorial Theory, Series B. — 1976. — Т. 20, вып. 1. — 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. — С. 69–86. — DOI:10.1002/jgt.3190030108..
  • Frank Harary, Leo Moser The theory of round robin tournaments // American Mathematical Monthly. — 1966. — Т. 73, вып. 3. — С. 231–246. — DOI:10.2307/2315334..
  • Guido Helden. Hamiltonicity of maximal planar graphs and planar triangulations. — Rheinisch-Westfälischen Technischen Hochschule Aachen, 2007. — (Dissertation)..
  • Arthur M. Hobbs The square of a block is vertex pancyclic // Journal of Combinatorial Theory. — 1976. — Т. 20, вып. 1. — С. 1–4. — 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. — С. 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. — С. 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. — С. 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. — С. 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 // Discrete Mathematics. — 1978. — Т. 21, вып. 3. — С. 323. — DOI:10.1016/0012-365X(78)90164-4..

Ссылки

  • Weisstein, Eric W. [mathworld.wolfram.com/PancyclicGraph.html Pancyclic Graph] (англ.) на сайте Wolfram MathWorld.


<imagemap>: неверное или отсутствующее изображение

 Для улучшения этой статьи желательно?:


Источник — «http://wiki-org.ru/wiki/index.php?title=Панциклический_граф&oldid=80903267»