Вікіпедія

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

орієнтований або неорієнтований граф, який містить цикли всіх можливих довжин від трьох до числа вершин графа

Панциклі́чний граф — орієнтований або неорієнтований граф, який містить цикли всіх можливих довжин від трьох до числа вершин графа[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. ↑ Hobbs, (1976).
  16. ↑ Fleischner, 1976.
  17. ↑ Li, Corneil, Mendelsohn, 2000, Theorems 2.3 и 2.4.
  18. ↑ Underground, (1978).
  19. ↑ Harary, Moser, 1966.
  20. ↑ Moon, 1966.

Література ред.

Посилання ред.

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