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