В теорії графів породженим шляхом в неорієнтованому графі G називається шлях, що є породженим підграфом G. Таким чином, це послідовність вершин в G, така, що будь-які дві суміжні вершини в послідовності з'єднані ребром в G і будь-які дві несуміжні вершини послідовності не з'єднані ребром G. Породжений шлях іноді називають змією і завдання пошуку найдовшого породженого шляху в графах гіперкубів відоме як задача про змію в коробці. Таким же чином, породженим циклом називається цикл, що є породженим підграфом G. Породжені цикли називаються також циклами без хорд або (якщо довжина циклу не менше чотирьох) дірками. Антидіра — це діра в доповненні графа G, тобто антидіра — це доповнення діри.
Довжину найбільшого породженого шляху в графі іноді називають числом обходу графа. Для розріджених графів існування обмеженого числа обходу еквівалентно існуванню обмеженої глибини дерева. Породженим числом обходу графа G називається найменше число підмножин вершин, на які можна розкласти вершини графа, щоб кожна підмножина утворювала породжений шлях,. і це поняття тісно пов'язане з числом покриття шляхами — мінімальне число незв'язних шляхів, що є породженими підграфами G, які покривають всі вершини G.. Обхват графа — це довжина його найкоротшого циклу, але цей цикл повинен бути породженим циклом, оскільки будь-яка хорда могла б утворити більш короткий цикл. З тих же причин непарним обхватом графа називається довжина його найкоротшого непарного породженого циклу.
Приклад На малюнку показаний куб, граф із вісьмома вершинами, дванадцятьма ребрами і породженим шляхом довжини чотири. Прямий аналіз показує, що не існує більш довгого породженого шляху в кубі, хоча існує породжений цикл довжини шість. Завдання пошуку найбільшого породженого шляху або циклу в гіперкубі, вперше поставлене Каутц , відоме як задача про змію в коробці та інтенсивно вивчалось через його використання в теорії кодування і конструюванні.
Опис сімейств графів Багато важливих сімейства графів можна описати в термінах породжених шляхів або циклів графів в сімействі.
Очевидно, що зв'язні графи, що не мають породжених шляхів довжини два — це повні графи, а зв'язні графи без породжених циклів — це дерева. Граф без трикутників — це граф без породжених циклів довжини три. Кографи — це в точності графи без породжених шляхів довжини три. Хордальні графи — це графи без породжених циклів довжини чотири й більше. Графи без дірок парної довжини — це графи, що не мають циклів, що містять парне число вершин. Тривіально досконалі графи — це графи, в яких немає ні породжених шляхів довжини три, ні породжених циклів довжини чотири. За строгою теоремою про досконалі графи, досконалі графи — це графи без непарних дірок і непарних антидір. Дистанційно-успадковувані графи — це графи, в яких будь-який породжений шлях є найкоротшим, і в цих графах будь-які два породжених шляхи між двома вершинами мають однакову довжину. Блокові графи — це графи, в яких існує максимум один породжений шлях між будь-якими двома вершинами, а зв'язні блокові графи — це графи, в яких існує в точності один породжений шлях між будь-якими двома вершинами.
Алгоритми і складність Завдання визначення, чи має граф G породжений шлях довжини не меншої k, є NP-повним. Гарей і Джонсон висловили цей результат в неопублікованому повідомленні Міхалісу Янакакісу. Однак це завдання можна вирішити за поліноміальний час для певних сімейств графів, таких як графи без астеро]дальних трійок . або графи без довгих дірок. .
Також є NP-повною задачею визначення, чи можна розкласти вершини графа на два породжених шляхи або два породжених цикли. . Як наслідок, визначення числа породжених шляхів графа є NP-складною задачею.
Складність задач апроксимації найбільшого породженого шляху або циклу можна пов'язати із завданням пошуку найбільших незалежних множин в графах..
Дірки (і антидіри в графах без циклів довжини 5 без хорд) у графі з n вершинами та m ребрами можуть бути знайдені за час (n + m2). .
Атомарні цикли Атомарні цикли — це узагальнення циклів без хорд. Якщо заданий цикл, n — хорда визначається як шлях довжини n, що містить дві точки циклу, де n менше довжини найкоротшого шляху в циклі, що з'єднує ці точки. Якщо цикл не має n — хорд, він називається атомарним циклом, оскільки його не можна розбити на менші цикли. . У найгіршому випадку атомарні цикли в графі можуть бути перераховані за час O (m2), де m — число ребер у графі.
Див. також Граф парності Задача про найдовший шлях
Примітки
Посилання
.