Породжений шлях

В теорії графів породженим шляхом в неорієнтованому графі G називається шлях, що є породженим підграфом G. Таким чином, це послідовність вершин в G, така, що будь-які дві суміжні вершини в послідовності з'єднані ребром в G і будь-які дві несуміжні вершини послідовності не з'єднані ребром G. Породжений шлях іноді називають змією і завдання пошуку найдовшого породженого шляху в графах гіперкубів відоме як задача про змію в коробці. Таким же чином, породженим циклом називається цикл, що є породженим підграфом G. Породжені цикли називаються також циклами без хорд або (якщо довжина циклу не менше чотирьох) дірками. Антидіра — це діра в доповненні графа G, тобто антидіра — це доповнення діри.

Породжений шлях довжини чотири в кубі. Завдання пошуку найбільшого породженого шляху в гіперкубі відоме як задача про змію в коробці.

Довжину найбільшого породженого шляху в графі іноді називають числом обходу графа^[1]. Для розріджених графів існування обмеженого числа обходу еквівалентно існуванню обмеженої глибини дерева.^[2] Породженим числом обходу графа G називається найменше число підмножин вершин, на які можна розкласти вершини графа, щоб кожна підмножина утворювала породжений шлях,^[3] і це поняття тісно пов'язане з числом покриття шляхами — мінімальне число незв'язних шляхів, що є породженими підграфами G, які покривають всі вершини G.^[4] Обхват графа — це довжина його найкоротшого циклу, але цей цикл повинен бути породженим циклом, оскільки будь-яка хорда могла б утворити більш короткий цикл. З тих же причин непарним обхватом графа називається довжина його найкоротшого непарного породженого циклу.

Приклад

На малюнку показаний куб, граф із вісьмома вершинами, дванадцятьма ребрами і породженим шляхом довжини чотири. Прямий аналіз показує, що не існує більш довгого породженого шляху в кубі, хоча існує породжений цикл довжини шість. Завдання пошуку найбільшого породженого шляху або циклу в гіперкубі, вперше поставлене ​​Каутц (Kautz, 1958), відоме як задача про змію в коробці та інтенсивно вивчалось через його використання в теорії кодування і конструюванні.

Опис сімейств графів

Багато важливих сімейства графів можна описати в термінах породжених шляхів або циклів графів в сімействі.

• Очевидно, що зв'язні графи, що не мають породжених шляхів довжини два — це повні графи, а зв'язні графи без породжених циклів — це дерева.
• Граф без трикутників — це граф без породжених циклів довжини три.
• Кографи — це в точності графи без породжених шляхів довжини три.
• Хордальні графи — це графи без породжених циклів довжини чотири й більше.
• Графи без дірок парної довжини — це графи, що не мають циклів, що містять парне число вершин.
• Тривіально досконалі графи — це графи, в яких немає ні породжених шляхів довжини три, ні породжених циклів довжини чотири.
• За строгою теоремою про досконалі графи, досконалі графи — це графи без непарних дірок і непарних антидір.
• Дистанційно-успадковувані графи — це графи, в яких будь-який породжений шлях є найкоротшим, і в цих графах будь-які два породжених шляхи між двома вершинами мають однакову довжину.
• Блокові графи — це графи, в яких існує максимум один породжений шлях між будь-якими двома вершинами, а зв'язні блокові графи — це графи, в яких існує в точності один породжений шлях між будь-якими двома вершинами.

Алгоритми і складність

Завдання визначення, чи має граф G породжений шлях довжини не меншої k, є NP-повним. Гарей і Джонсон (Garey, Johnson, 1979) висловили цей результат в неопублікованому повідомленні Міхалісу Янакакісу. Однак це завдання можна вирішити за поліноміальний час для певних сімейств графів, таких як графи без астеро]дальних трійок^[5] або графи без довгих дірок.^[6]

Також є NP-повною задачею визначення, чи можна розкласти вершини графа на два породжених шляхи або два породжених цикли.^[7] Як наслідок, визначення числа породжених шляхів графа є NP-складною задачею.

Складність задач апроксимації найбільшого породженого шляху або циклу можна пов'язати із завданням пошуку найбільших незалежних множин в графах.^[8]

Дірки (і антидіри в графах без циклів довжини 5 без хорд) у графі з n вершинами та m ребрами можуть бути знайдені за час (n + m²).^[9]

Атомарні цикли

Атомарні цикли — це узагальнення циклів без хорд. Якщо заданий цикл, n — хорда визначається як шлях довжини n, що містить дві точки циклу, де n менше довжини найкоротшого шляху в циклі, що з'єднує ці точки. Якщо цикл не має n — хорд, він називається атомарним циклом, оскільки його не можна розбити на менші цикли.^[10] У найгіршому випадку атомарні цикли в графі можуть бути перераховані за час O (m²), де m — число ребер у графі.

Див. також

• Граф парності
• Задача про найдовший шлях