Вікіпедія

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

В теорії графів породженим шляхом в неорієнтованому графі 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/w/index.php?title=Породжений_шлях&oldid=41236214