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

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

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

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

Приклад

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Примітки

1. Buckley, Harary, 1988
2. Nešetřil, Ossona de Mendez, 2012
3. Chartrand, McCanna, Sherwani, Hossain, 1994.
4. Barioli, Fallat, Hogben, 2004.
5. Kratsch, Müller, Todinca, 2003.
6. Gavril, 2002.
7. Le, Le, Müller, 2003.
8. Berman, Schnitger, 1992.
9. Nikolopoulos, Palios, 2004.
10. Gashler, Martinez, 2012.

Посилання

• Francesco Barioli, Shaun Fallat, Leslie Hogben. Computation of minimal rank and path cover number for certain graphs // Linear Algebra Appl.. — 2004. — Т. 392. — С. 289–303. — DOI:10.1016/j.laa.2004.06.019.
• Piotr Berman, Georg Schnitger. On the complexity of approximating the independent set problem // Information and Computation. — 1992. — Т. 96. — No. 1. — С. 77–94. — DOI:10.1016/0890-5401(92)90056-L.
• Fred Buckley, Frank Harary. On longest induced paths in graphs // Chinese Quart. J. Math.. — 1988. — Т. 3. — No. 3. — С. 61–65.
• Gary Chartrand, Joseph McCanna, Naveed Sherwani, Moazzem Hossain, Jahangir Hashmi. The induced path number of bipartite graphs // Ars Combin.. — 1994. — Т. 37. — С. 191–208.
• Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — С. 196.
• Michael Gashler, Tony Martinez. Robust manifold learning with CycleCut // Connection Science. — 2012. — Т. 24, вип. 1. — С. 57–69. — DOI:10.1080/09540091.2012.664122.
• Fănică Gavril. Algorithms for maximum weight induced paths // Information Processing Letters. — 2002. — Т. 81, вип. 4. — С. 203–208. — DOI:10.1016/S0020-0190(01)00222-8.
• Johan Håstad. Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. — 1996. — С. 627–636. — DOI:10.1109/SFCS.1996.548522.
• W. H. Kautz. Unit-distance error-checking codes // IRE Trans. Elect. Comput.. — 1958. — Т. 7. — С. 177–180.
• Dieter Kratsch, Haiko Müller, Ioan Todinca. Graph-theoretic concepts in computer science. — Berlin : Lecture Notes in Computer Science, Vol. 2880, Springer-Verlag, 2003. — С. 309–321. — DOI:10.1007/b93953.
• Hoàng-Oanh Le, Van Bang Le, Haiko Müller. Splitting a graph into disjoint induced paths or cycles // Discrete Appl. Math.. — 2003. — Т. 131, вип. 1. — С. 199–212. — DOI:10.1016/S0166-218X(02)00425-0.
• Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Heidelberg : Springer, 2012. — Т. 28. — С. 115–144. — (Algorithms and Combinatorics). — . — DOI:10.1007/978-3-642-27875-4.
• Stavros D. Nikolopoulos, Leonidas Palios. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms. — 2004. — С. 850–859..