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

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

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

Определения

Граф $G$ с $n$ вершинами является панциклическим, если для любого $k$ в пределах $3⩽k⩽n$ граф $G$ содержит цикл длины $k$Шаблон:Sfn. Граф является вершинно панциклическим, если для любой вершины $v$ и любого $k$ в тех же пределах граф содержит цикл длины $k$, содержащий вершину $v$Шаблон:Sfn. Похожим образом граф является рёберно панциклическим, если для любого ребра $e$ и для любого $k$ в тех же пределах он содержит цикл длины $v$, содержащий ребро $e$Шаблон:Sfn.

Двудольный граф не может быть панциклическим, поскольку он не содержит циклы любой нечётной длины, но говорят, что граф является бипанциклическим, если он содержит циклы всех чётных длин от 4 до $n$Шаблон:Sfn.

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

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

Максимальный планарный граф — это планарный граф, в котором все грани, включая внешнюю, являются треугольниками. Максимальный планарный граф является вершинно панциклическим тогда и только тогда, когда он содержит гамильтонов циклШаблон:Sfn — если он не гамильтонов, он определённо не панцикличен, а если он гамильтонов, то внутренность гамильтонова цикла образует внешнюю грань максимального внешнепланарного графа на тех же вершинах и рёбрах, к которой можно применить предыдущие аргументы для внешнепланарных графовШаблон:Sfn. Например, на рисункеШаблон:Каком? показана панцикличность графа октаэдра, гамильтонова максимального планарного графа с шестью вершинами. Более строго, по тем же самым причинам, если максимальный планарный граф имеет цикл длины $k$, он имеет циклы всех меньших длинШаблон:Sfn.

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

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

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

Турниры

Турнир — это направленный граф с одной направленной дугой между любой парой вершин. Интуитивно турнир может быть использован для моделирования круговой системы путём рисования дуги от победителя к побеждённому для каждой игры в соревновании. Турнир называется сильно связным или просто сильным тогда и только тогда, когда он не может быть разделён на два непустых подмножества $L$ и $W$ проигравших и выигравших, так что любой участник $W$ побеждает любого участника в $L$Шаблон:Sfn. Любой сильный турнир является панциклическимШаблон:Sfn и вершинно панциклическимШаблон:Sfn. Если турнир регулярен (любой участник имеет то же число выигрышей и проигрышей, что и другие участники), то он является также рёберно панциклическимШаблон:Sfn, однако сильные турниры с четырьмя вершинами не могут быть рёберно панциклическими.

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

Шаблон:Не переведено 5 утверждает, что любой неориентированный граф с $n$ вершинами, имеющий по меньшей мере $n^2/4$ рёбер и не имеющий кратных рёбер и петель, либо содержит треугольник, либо он является полным двудольным графом $K_{n/2,n/2}$. Эту теорему можно усилить — любой неориентированный гамильтонов граф с не менее чем $n^2/4$ рёбрами либо панцикличен, либо это $K_{n/2,n/2}$Шаблон:Sfn.

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

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

Для любого графа $G$ его $k$-я степень графа $G^k$ определяется как граф на том же множестве вершин, имеющий ребро между любыми двумя вершинами, расстояние между которыми в $G$ не превосходит $k$. Если $G$ вершинно 2-связен, то по теореме Фляйшнера $G^2$ является гамильтоновым графом. Утверждение может быть усилено: граф обязательно будет вершинно панциклическимШаблон:Sfnp. Более строго, если $G^2$ является гамильтоновым, он также и панцикличенШаблон:Sfn.

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

Проверка графа на панцикличность является NP-полной задачей даже для специального случая 3-связных кубических графов. NP-полной задачей является также проверка графа на вершинную панцикличность даже для специального случая полиэдральных графовШаблон:Sfn. Также NP-полной задачей является проверка квадрата графа на гамильтоновость, а тем самым и проверка на панцикличностьШаблон:Sfnp.

История

Панцикличность впервые исследовали Харари и Мозер в контексте турнировШаблон:Sfn, а также МуунШаблон:Sfn и АлпачШаблон:Sfn. Понятие панцикличности получило название от Бонди, который расширил понятие для неориентированных графовШаблон:Sfn.

Литература

• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Книга.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Книга.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Статья.
• Шаблон:Книга.
• Шаблон:Статья.

Ссылки

• Шаблон:Mathworld