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

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

Панциклі́чний граф — орієнтований або неорієнтований граф, який містить цикли всіх можливих довжин від трьох до числа вершин графа[1]. Панциклічні графи є узагальненням гамільтонових графів, графів, які мають цикли найбільшої можливої довжини.

Визначення[ред. | ред. код]

Граф з вершинами є панциклічним, якщо для будь-якого в межах граф містить цикл довжини [1]. Граф є вершинно панциклічним, якщо для будь-якої вершини і будь-якого в тих самих межах граф містить цикл довжини , що містить вершину [2]. Схожим чином граф є реберно панциклічним, якщо для будь-якого ребра і для будь-якого в тих самих межах він містить цикл довжини , що містить ребро [2].

Двочастинний граф не може бути панциклічним, оскільки він не містить циклів будь-якої непарної довжини, але кажуть, що граф є біпанциклічним, якщо він містить цикли всіх парних довжин від 4 до [3].

Планарні графи[ред. | ред. код]

Максимальний зовніпланарний граф — це граф, утворений із простого многокутника на площині шляхом тріангуляції його внутрішності. Будь-який максимальний зовніпланарний граф є панциклічним, що можна показати індукцією. Зовнішня грань графа є циклом з n вершинами, а видалення будь-якого трикутника, з'єднаного із рештою графа тільки одним ребром (листок дерева, яке утворює двоїстий граф тріангуляції), утворює максимальний зовніпланарний граф з на одиницю меншим числом вершин, а за індукційним припущенням цей граф має всі цикли всіх довжин, що залишилися. Якщо приділяти більше уваги вибору трикутника для видалення, то ті самі аргументи показують строгіший результат, що будь-який максимальний зовніпланарний граф є вершинно панциклічним[4]. Те ж саме істинне для графів, які мають максимальний зовніпланарний граф як кістяковий підграф, зокрема, для колеса.

Максимальний планарний граф — це планарний граф, у якому всі грані, включно із зовнішньою, є трикутниками. Максимальний планарний граф є вершинно панциклічним тоді й лише тоді, коли він містить гамільтонів цикл[5] — якщо він не гамільтонів, він безумовно не панциклічний, а якщо він гамільтонів, то внутрішність гамильтонового циклу утворює зовнішню межу максимального зовнішпланарного графа на тих самих вершинах і ребрах, до якої можна застосувати попередні аргументи для зовніпланарних графів[6]. Наприклад, на малюнку вгорі показано панциклічність графа октаедра, гамільтонового максимального планарного графа з шістьма вершинами. Строгіше, з тих самих причин, якщо максимальний планарний граф має цикл довжини , то він має цикли всіх менших довжин[7].

Майже панциклічний граф Халіна з циклами всіх довжин аж до n, за винятком довжини 8

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

1971 року помічено[1], що багато класичних умов для існування гамільтонового циклу достатні також для панциклічності, тому припущено, що будь-який 4-зв'язний планарний граф панциклічний, але незабаром знайдено сімейство контрприкладів[9].

Турніри[ред. | ред. код]

Турнір — це напрямлений граф з однією напрямленою дугою між будь-якою парою вершин. Інтуїтивно турнір можна використати для моделювання кругової системи малюванням дуги від переможця до переможеного для кожної гри в змаганні. Турнір називають сильно зв'язним або просто сильним тоді й лише тоді, коли його не можна розділити на дві непорожні підмножини і тих, хто програв і виграв, так, що будь-який учасник перемагає будь-якого учасника в [10]. Будь-який сильний турнір є панциклічним[11] і вершинно панциклічним[12]. Якщо турнір регулярний (будь-який учасник має таке ж число виграшів і програшів, що й інші учасники), то він є також реберно панциклічним[13], однак сильні турніри з чотирма вершинами не можуть бути реберно панциклічними.

Графи з великим числом ребер[ред. | ред. код]

Теорема Мантеля стверджує, що будь-який неорієнтований граф із вершинами, що має принаймні ребер і не має кратних ребер і петель, або містить трикутник, або він є повним двочастинним графом . Цю теорему можна посилити — будь-який неорієнтований гамільтонів граф з не менш ніж ребрами або панциклічний, або це [1].

Існують гамільтонові орієнтовані графи з вершинами і з дугами, які не є панциклічними, але будь-який гамільтонів орієнтований граф принаймні з дугами панциклічний. Крім того, строго зв'язний граф з вершинами, в якому кожна вершина має степінь, не менший від (вхідні та вихідні дуги рахуються разом), або панциклічний, або є повним двочастинним графом[14].

Степені графа[ред. | ред. код]

Для будь-якого графа його -й степінь графа визначається як граф на тій самій множині вершин, що має ребро між будь-якими двома вершинами, відстань між якими в не перевищує . Якщо вершинно 2-зв'язний, то за теоремою Фляйшнера є гамільтоновим графом. Твердження можна посилити: граф обов'язково буде вершинно панциклічним[15]. Строгіше, якщо є гамільтоновим, він також і панциклічний[16].

Обчислювальна складність[ред. | ред. код]

Перевірка графа на панциклічність є NP-повною задачею навіть для окремого випадку 3-зв'язних кубічних графів. NP-повною задачею є також перевірка графа на вершинну панциклічність навіть для окрмого випадку поліедральних графів[17]. Також NP-повною задачею є перевірка квадрата графа на гамільтоновість, а тим самим і перевірка на панциклічність[18].

Історія[ред. | ред. код]

Панциклічність уперше досліджували Харарі і Мозер у контексті турнірів[19], а також Муун[20] і Алпач[13]. Назву поняттю панциклічності дав Бонді, який розширив поняття для неорієнтованих графів[1].

Примітки[ред. | ред. код]

  1. ↑ а б в г д Bondy, 1971.
  2. ↑ а б Randerath, Schiermeyer, Tewes, Volkmann, 2002.
  3. ↑ Schmeichel, Mitchem, 1982.
  4. ↑ Li, Corneil, Mendelsohn, 2000, Proposition 2.5.
  5. ↑ Helden, 2007, Corollary 3.78.
  6. ↑ Bernhart, Kainen, 1979.
  7. ↑ Hakimi, Schmeichel, 1979.
  8. ↑ Skowrońska, 1985.
  9. ↑ Malkevitch, 1971.
  10. ↑ Harary, Moser, 1966, Corollary 5b.
  11. ↑ Harary, Moser, 1966, Theorem 7.
  12. ↑ Moon, 1966, Theorem 1.
  13. ↑ а б Alspach, 1967.
  14. ↑ Häggkvist, Thomassen, 1976, с. 20–40.
  15. ↑ Помилка скрипту: Функції «harvard_core» не існує.
  16. ↑ Fleischner, 1976.
  17. ↑ Li, Corneil, Mendelsohn, 2000, Theorems 2.3 и 2.4.
  18. ↑ Помилка скрипту: Функції «harvard_core» не існує.
  19. ↑ Harary, Moser, 1966.
  20. ↑ Moon, 1966.

Література[ред. | ред. код]

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Панциклічний_граф&oldid=37002129