Loading AI tools
З Вікіпедії, вільної енциклопедії
В теорії графів породженим шляхом в неорієнтованому графі 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 + m2).[9]
Атомарні цикли — це узагальнення циклів без хорд. Якщо заданий цикл, n — хорда визначається як шлях довжини n, що містить дві точки циклу, де n менше довжини найкоротшого шляху в циклі, що з'єднує ці точки. Якщо цикл не має n — хорд, він називається атомарним циклом, оскільки його не можна розбити на менші цикли.[10] У найгіршому випадку атомарні цикли в графі можуть бути перераховані за час O (m2), де m — число ребер у графі.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.