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

Поделись знанием:
(перенаправлено с «Рёберно-панциклический граф»)
Перейти к: навигация, поиск

Панциклический граф — ориентированный или неориентированный граф, который содержит циклы всех возможных длин от трёх до числа вершин графа[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].

Напишите отзыв о статье "Панциклический граф"

Примечания

Литература

  • 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.


Отрывок, характеризующий Панциклический граф

– Нет, нет, говорите, – сказала Наташа. – Он где же?
– Его убили почти при мне. – И Пьер стал рассказывать последнее время их отступления, болезнь Каратаева (голос его дрожал беспрестанно) и его смерть.
Пьер рассказывал свои похождения так, как он никогда их еще не рассказывал никому, как он сам с собою никогда еще не вспоминал их. Он видел теперь как будто новое значение во всем том, что он пережил. Теперь, когда он рассказывал все это Наташе, он испытывал то редкое наслаждение, которое дают женщины, слушая мужчину, – не умные женщины, которые, слушая, стараются или запомнить, что им говорят, для того чтобы обогатить свой ум и при случае пересказать то же или приладить рассказываемое к своему и сообщить поскорее свои умные речи, выработанные в своем маленьком умственном хозяйстве; а то наслажденье, которое дают настоящие женщины, одаренные способностью выбирания и всасыванья в себя всего лучшего, что только есть в проявлениях мужчины. Наташа, сама не зная этого, была вся внимание: она не упускала ни слова, ни колебания голоса, ни взгляда, ни вздрагиванья мускула лица, ни жеста Пьера. Она на лету ловила еще не высказанное слово и прямо вносила в свое раскрытое сердце, угадывая тайный смысл всей душевной работы Пьера.
Княжна Марья понимала рассказ, сочувствовала ему, но она теперь видела другое, что поглощало все ее внимание; она видела возможность любви и счастия между Наташей и Пьером. И в первый раз пришедшая ей эта мысль наполняла ее душу радостию.
Было три часа ночи. Официанты с грустными и строгими лицами приходили переменять свечи, но никто не замечал их.
Пьер кончил свой рассказ. Наташа блестящими, оживленными глазами продолжала упорно и внимательно глядеть на Пьера, как будто желая понять еще то остальное, что он не высказал, может быть. Пьер в стыдливом и счастливом смущении изредка взглядывал на нее и придумывал, что бы сказать теперь, чтобы перевести разговор на другой предмет. Княжна Марья молчала. Никому в голову не приходило, что три часа ночи и что пора спать.
– Говорят: несчастия, страдания, – сказал Пьер. – Да ежели бы сейчас, сию минуту мне сказали: хочешь оставаться, чем ты был до плена, или сначала пережить все это? Ради бога, еще раз плен и лошадиное мясо. Мы думаем, как нас выкинет из привычной дорожки, что все пропало; а тут только начинается новое, хорошее. Пока есть жизнь, есть и счастье. Впереди много, много. Это я вам говорю, – сказал он, обращаясь к Наташе.
– Да, да, – сказала она, отвечая на совсем другое, – и я ничего бы не желала, как только пережить все сначала.
Пьер внимательно посмотрел на нее.
– Да, и больше ничего, – подтвердила Наташа.
– Неправда, неправда, – закричал Пьер. – Я не виноват, что я жив и хочу жить; и вы тоже.
Вдруг Наташа опустила голову на руки и заплакала.
– Что ты, Наташа? – сказала княжна Марья.
– Ничего, ничего. – Она улыбнулась сквозь слезы Пьеру. – Прощайте, пора спать.
Пьер встал и простился.

Княжна Марья и Наташа, как и всегда, сошлись в спальне. Они поговорили о том, что рассказывал Пьер. Княжна Марья не говорила своего мнения о Пьере. Наташа тоже не говорила о нем.
– Ну, прощай, Мари, – сказала Наташа. – Знаешь, я часто боюсь, что мы не говорим о нем (князе Андрее), как будто мы боимся унизить наше чувство, и забываем.
Княжна Марья тяжело вздохнула и этим вздохом признала справедливость слов Наташи; но словами она не согласилась с ней.
– Разве можно забыть? – сказала она.
– Мне так хорошо было нынче рассказать все; и тяжело, и больно, и хорошо. Очень хорошо, – сказала Наташа, – я уверена, что он точно любил его. От этого я рассказала ему… ничего, что я рассказала ему? – вдруг покраснев, спросила она.
– Пьеру? О нет! Какой он прекрасный, – сказала княжна Марья.
– Знаешь, Мари, – вдруг сказала Наташа с шаловливой улыбкой, которой давно не видала княжна Марья на ее лице. – Он сделался какой то чистый, гладкий, свежий; точно из бани, ты понимаешь? – морально из бани. Правда?
– Да, – сказала княжна Марья, – он много выиграл.
– И сюртучок коротенький, и стриженые волосы; точно, ну точно из бани… папа, бывало…
– Я понимаю, что он (князь Андрей) никого так не любил, как его, – сказала княжна Марья.
– Да, и он особенный от него. Говорят, что дружны мужчины, когда совсем особенные. Должно быть, это правда. Правда, он совсем на него не похож ничем?
– Да, и чудесный.
– Ну, прощай, – отвечала Наташа. И та же шаловливая улыбка, как бы забывшись, долго оставалась на ее лице.


Пьер долго не мог заснуть в этот день; он взад и вперед ходил по комнате, то нахмурившись, вдумываясь во что то трудное, вдруг пожимая плечами и вздрагивая, то счастливо улыбаясь.
Он думал о князе Андрее, о Наташе, об их любви, и то ревновал ее к прошедшему, то упрекал, то прощал себя за это. Было уже шесть часов утра, а он все ходил по комнате.
«Ну что ж делать. Уж если нельзя без этого! Что ж делать! Значит, так надо», – сказал он себе и, поспешно раздевшись, лег в постель, счастливый и взволнованный, но без сомнений и нерешительностей.
«Надо, как ни странно, как ни невозможно это счастье, – надо сделать все для того, чтобы быть с ней мужем и женой», – сказал он себе.
Пьер еще за несколько дней перед этим назначил в пятницу день своего отъезда в Петербург. Когда он проснулся, в четверг, Савельич пришел к нему за приказаниями об укладке вещей в дорогу.
«Как в Петербург? Что такое Петербург? Кто в Петербурге? – невольно, хотя и про себя, спросил он. – Да, что то такое давно, давно, еще прежде, чем это случилось, я зачем то собирался ехать в Петербург, – вспомнил он. – Отчего же? я и поеду, может быть. Какой он добрый, внимательный, как все помнит! – подумал он, глядя на старое лицо Савельича. – И какая улыбка приятная!» – подумал он.
– Что ж, все не хочешь на волю, Савельич? – спросил Пьер.
– Зачем мне, ваше сиятельство, воля? При покойном графе, царство небесное, жили и при вас обиды не видим.
– Ну, а дети?
– И дети проживут, ваше сиятельство: за такими господами жить можно.
– Ну, а наследники мои? – сказал Пьер. – Вдруг я женюсь… Ведь может случиться, – прибавил он с невольной улыбкой.
– И осмеливаюсь доложить: хорошее дело, ваше сиятельство.
«Как он думает это легко, – подумал Пьер. – Он не знает, как это страшно, как опасно. Слишком рано или слишком поздно… Страшно!»
– Как же изволите приказать? Завтра изволите ехать? – спросил Савельич.
– Нет; я немножко отложу. Я тогда скажу. Ты меня извини за хлопоты, – сказал Пьер и, глядя на улыбку Савельича, подумал: «Как странно, однако, что он не знает, что теперь нет никакого Петербурга и что прежде всего надо, чтоб решилось то. Впрочем, он, верно, знает, но только притворяется. Поговорить с ним? Как он думает? – подумал Пьер. – Нет, после когда нибудь».
За завтраком Пьер сообщил княжне, что он был вчера у княжны Марьи и застал там, – можете себе представить кого? – Натали Ростову.
Княжна сделала вид, что она в этом известии не видит ничего более необыкновенного, как в том, что Пьер видел Анну Семеновну.
– Вы ее знаете? – спросил Пьер.
– Я видела княжну, – отвечала она. – Я слышала, что ее сватали за молодого Ростова. Это было бы очень хорошо для Ростовых; говорят, они совсем разорились.
– Нет, Ростову вы знаете?
– Слышала тогда только про эту историю. Очень жалко.
«Нет, она не понимает или притворяется, – подумал Пьер. – Лучше тоже не говорить ей».
Княжна также приготавливала провизию на дорогу Пьеру.
«Как они добры все, – думал Пьер, – что они теперь, когда уж наверное им это не может быть более интересно, занимаются всем этим. И все для меня; вот что удивительно».
В этот же день к Пьеру приехал полицеймейстер с предложением прислать доверенного в Грановитую палату для приема вещей, раздаваемых нынче владельцам.
«Вот и этот тоже, – думал Пьер, глядя в лицо полицеймейстера, – какой славный, красивый офицер и как добр! Теперь занимается такими пустяками. А еще говорят, что он не честен и пользуется. Какой вздор! А впрочем, отчего же ему и не пользоваться? Он так и воспитан. И все так делают. А такое приятное, доброе лицо, и улыбается, глядя на меня».
Пьер поехал обедать к княжне Марье.
Проезжая по улицам между пожарищами домов, он удивлялся красоте этих развалин. Печные трубы домов, отвалившиеся стены, живописно напоминая Рейн и Колизей, тянулись, скрывая друг друга, по обгорелым кварталам. Встречавшиеся извозчики и ездоки, плотники, рубившие срубы, торговки и лавочники, все с веселыми, сияющими лицами, взглядывали на Пьера и говорили как будто: «А, вот он! Посмотрим, что выйдет из этого».
При входе в дом княжны Марьи на Пьера нашло сомнение в справедливости того, что он был здесь вчера, виделся с Наташей и говорил с ней. «Может быть, это я выдумал. Может быть, я войду и никого не увижу». Но не успел он вступить в комнату, как уже во всем существе своем, по мгновенному лишению своей свободы, он почувствовал ее присутствие. Она была в том же черном платье с мягкими складками и так же причесана, как и вчера, но она была совсем другая. Если б она была такою вчера, когда он вошел в комнату, он бы не мог ни на мгновение не узнать ее.
Она была такою же, какою он знал ее почти ребенком и потом невестой князя Андрея. Веселый вопросительный блеск светился в ее глазах; на лице было ласковое и странно шаловливое выражение.
Пьер обедал и просидел бы весь вечер; но княжна Марья ехала ко всенощной, и Пьер уехал с ними вместе.
На другой день Пьер приехал рано, обедал и просидел весь вечер. Несмотря на то, что княжна Марья и Наташа были очевидно рады гостю; несмотря на то, что весь интерес жизни Пьера сосредоточивался теперь в этом доме, к вечеру они всё переговорили, и разговор переходил беспрестанно с одного ничтожного предмета на другой и часто прерывался. Пьер засиделся в этот вечер так поздно, что княжна Марья и Наташа переглядывались между собою, очевидно ожидая, скоро ли он уйдет. Пьер видел это и не мог уйти. Ему становилось тяжело, неловко, но он все сидел, потому что не мог подняться и уйти.