Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Циклы всех возможных длин на графике октаэдра , показывая, что он панциклический.

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

Определения [ править ]

П -vertex графа G есть pancyclic , если для каждого к в диапазоне 3 ≤ K ≤ N , G содержит цикл длины к . [1] Он является панциклическим узлом или панциклическим вершиной, если для каждой вершины v и каждого k в том же диапазоне он содержит цикл длины k , содержащий v . [2] Аналогично, он является панциклическим по ребрам, если для каждого ребра e и каждого kв том же диапазоне он содержит цикл длины k , содержащий e . [2]

Двудольный граф не может быть pancyclic, так как она не содержит каких - либо циклов нечетной длины, но это называется bipancyclic , если он содержит циклы всех четных длин от 4 до п . [3]

Планарные графики [ править ]

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

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

Почти панциклический граф Халина с циклами любой длины до n, кроме длины 8

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

Бонди (1971) заметил, что многие классические условия существования гамильтонова цикла также являются достаточными условиями для того, чтобы граф был панциклическим, и на этом основании предположил, что каждый четырехсвязный плоский граф является панциклическим. Однако Малькевич (1971) нашел ряд контрпримеров.

Турниры [ править ]

Турнир представляет собой ориентированный граф с одним ориентированным ребром между каждой парой вершин. Интуитивно турнир можно использовать для моделирования кругового спортивного соревнования , извлекая преимущество от победителя к проигравшему в каждой игре соревнования. Турнир называется сильно связным или сильным , если и только если она не может быть разделена на два непустых подмножества L и W проигравших и победителей, таких , что каждый конкурент в W бьется каждый конкурент в L . [9] Каждый сильный турнир бывает панциклическим [10] и узловым-панциклическим. [11] Если турнир регулярный(у каждого участника такое же количество побед и поражений, как и у другого участника), тогда это также является панциклическим краем; [12] однако сильный турнир с четырьмя вершинами не может быть реберно-панциклическим.

Графы с множеством ребер [ править ]

Теорема Mantel в гласит , что любая п -vertex неориентированный граф, по крайней мере , п 2 /4 ребер и не кратных ребер или само-петель, либо содержит треугольник , или это полный двудольный граф К п / 2, п / 2 . Эта теорема может быть усилена: любой неориентированный граф с гамильтонов по крайней мере , п 2 /4 ребер либо pancyclic или К п / 2, п / 2 . [1]

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

Возможности графа [ править ]

Для любого графа G его k- я степень G k определяется как граф на том же множестве вершин, у которого есть ребро между каждыми двумя вершинами, расстояние которых в G не превышает k . Если G является 2-вершинным соединен , то по Fleischner теорема его квадрат , G 2 гамильтонов; это можно усилить, чтобы показать, что он обязательно вершинно-панциклический. [14] Более того, если G 2 гамильтонова, она также панциклическая. [15]

Вычислительная сложность [ править ]

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

История [ править ]

Панцикличность была впервые исследована в контексте турниров Harary & Moser (1966) , Moon (1966) и Alspach (1967) . Понятие панцикличности было названо и распространено на неориентированные графы Бонди (1971) .

Заметки [ править ]

  1. ^ a b c Бонди (1971) .
  2. ^ а б Рандерат и др. (2002) .
  3. ^ Шмейхель & Митч (1982) .
  4. ^ Ли, Корнейл и Мендельсон (2000) , предложение 2.5.
  5. ^ Helden (2007) , следствие 3.78.
  6. ^ Бернхарт & Kainen (1979) .
  7. ^ Hakimi & Шмейхель (1979) .
  8. ^ Skowrońska (1985) .
  9. ^ Harary & Moser (1966) , следствие 5b.
  10. ^ Харари и Moser (1966) , теорема 7.
  11. ^ Мун (1966) , теорема 1.
  12. ^ Alspach (1967) .
  13. ^ Häggkvist & Thomassen (1976) .
  14. ^ Хоббс (1976) .
  15. ^ Флейшнер (1976) .
  16. ^ Ли, Корней и Мендельсон (2000) , теоремы 2.3 и 2.4.
  17. Перейти ↑ Underground (1978) .

Ссылки [ править ]

  • Alspach, Брайан (1967), "Циклы каждой длины в регулярных турнирах" , Канадский математический вестник , 10 (2): 283-286, DOI : 10,4153 / CMB-1967-028-6 CS1 maint: обескураженный параметр ( ссылка ).
  • Бернхарт, Франк; Кайнен, Пол К. (1979), "Толщина книги графа", Журнал комбинаторной теории , серия B , 27 (3): 320–331, DOI : 10.1016 / 0095-8956 (79) 90021-2.
  • Бонди, Дж. А. (1971), «Панциклические графы I», Журнал комбинаторной теории , серия B , 11 (1): 80–84, DOI : 10.1016 / 0095-8956 (71) 90016-5 CS1 maint: обескураженный параметр ( ссылка ).
  • Флейшнер, Х. (1976), «В квадрате графов гамильтоновость и панцикличность, гамильтонова связность и пансвязность являются эквивалентными понятиями», Monatshefte für Mathematik , 82 (2): 125–149, doi : 10.1007 / BF01305995 , MR  0427135.
  • Хэггквист, Роланд; Томассен, Карстен (1976), «О панциклических орграфах», Журнал комбинаторной теории , серия B , 20 (1): 20-40, DOI : 10.1016 / 0095-8956 (76) 90063-0.
  • Хакими, SL ; Шмейхель, Е. Ф. (1979), «О числе циклов длины к в максимальной плоский граф», Журнал теории графов , 3 : 69-86, DOI : 10.1002 / jgt.3190030108.
  • Харари, Фрэнк ; Moser, Лео (1966), "Теория круглых турниров по круговой системе ", American Mathematical Monthly , 73 (3): 231-246, DOI : 10,2307 / 2315334.
  • Helden, Guido (2007), Гамильтоничность максимальных плоских графов и планарных триангуляций (PDF) , Диссертация, Rheinisch-Westfälischen Technischen Hochschule Aachen, архивировано из оригинала (PDF) 18 июля 2011 г. CS1 maint: обескураженный параметр ( ссылка ).
  • Хоббс, Артур М. (1976), «Квадрат блока является панциклической вершиной», Журнал комбинаторной теории , серия B, 20 (1): 1–4, DOI : 10.1016 / 0095-8956 (76) 90061-7 , Руководство по ремонту  0416980 CS1 maint: обескураженный параметр ( ссылка ).
  • Ли, Мин-Чу; Корнейл, Дерек Г .; Мендельсон, Эрик (2000), "Pancyclicity и NP-полнота в плоских графах", Дискретная прикладная математика , 98 (3): 219-225, DOI : 10.1016 / S0166-218X (99) 00163-8.
  • Малькевич, Джозеф (1971), «О длинах циклов в плоских графах», Недавние тенденции в теории графов , Конспект лекций по математике, 186 , Springer-Verlag, стр. 191–195, doi : 10.1007 / BFb0059437.
  • Луна, JW (1966), "О subtournaments турнира , " , Канадский математический вестник , 9 (3): 297-301, DOI : 10,4153 / CMB-1966-038-7.
  • Рандерат, Берт; Ширмейер, Инго; Тьюз, Мейке; Фолькмана, Lutz (2002), "Vertex pancyclic графы", дискретная Прикладная математика , 120 (1-3): 219-237, DOI : 10.1016 / S0166-218X (01) 00292-X.
  • Шмейхель, Эдвард; Митч, Джон (1982), "двудольные графы с циклами всех четных длинами", Журнал теории графов , 6 (4): 429-439, DOI : 10.1002 / jgt.3190060407.
  • Сковроньска, Мирослава (1985), «Панцикличность графов Халина и их внешние сжатия», в Alspach, Брайан Р .; Годсил, Кристофер Д. (ред.), Циклы в графах , Анналы дискретной математики, 27 , Elsevier Science Publishers BV, стр. 179–194..
  • Метро, ​​Полли (1978), «О графах с гамильтоновыми квадратами», Дискретная математика , 21 (3): 323, DOI : 10.1016 / 0012-365X (78) 90164-4 , MR  0522906 CS1 maint: обескураженный параметр ( ссылка ).

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Панциклический граф» . MathWorld .