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

Цикли всіх можливих довжин у графі октаедр показують, що граф панциклічний

Панциклі́чний граф — орієнтований або неорієнтований граф, який містить цикли всіх можливих довжин від трьох до числа вершин графаШаблон: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, однак сильні турніри з чотирма вершинами не можуть бути реберно панциклічними.

Графи з великим числом ребер

Теорема Мантеля стверджує, що будь-який неорієнтований граф із $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