Вікіпедія

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

Немає перевірених версій цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

В теорії графів породженим шляхом в неорієнтованому графі 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 — число ребер у графі.

Див. також

ред.

Примітки

ред.
  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). — ISBN 978-3-642-27874-7. — DOI:10.1007/978-3-642-27875-4.
  • Stavros D. Nikolopoulos, Leonidas Palios. Proc. 15th ACM-SIAM Symposium on Discrete Algorithms. — 2004. — С. 850–859..
Отримано з https://uk.wikipedia.org/wiki/Породжений_шлях