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

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

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

Определения

An п-вершинный граф грамм является панциклический если для каждого k В диапазоне 3 ≤ k ≤ п, грамм содержит цикл длины k.^[1] это узел-панциклический или же вершинно-панциклический если для каждой вершины v и каждый k в том же диапазоне он содержит цикл длины k который содержит v.^[2] Точно так же край-панциклический если для каждого края е и каждый k в том же диапазоне он содержит цикл длины k который содержит е.^[2]

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

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

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

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

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

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

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

Турниры

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

Графы с множеством ребер

Теорема Мантеля заявляет, что любой п-вершинный неориентированный граф с не менее п²/ 4 ребра, а не множественные ребра или петли, либо содержит треугольник, либо полный двудольный граф K_п/2,п/2. Эту теорему можно усилить: любой неориентированный гамильтонов граф с не менее п²/ 4 ребра либо панциклические, либо K_п/2,п/2.^[1]

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

График мощности

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

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

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

История

Впервые панцикличность в контексте турниров была исследована Харари и Мозер (1966), Луна (1966), и Альспах (1967). Концепция панцикличности была названа и распространена на неориентированные графы Бонди (1971).

Примечания

Рекомендации

внешняя ссылка

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