Порождённый путь (Hkjk';~uudw hrm,)

Порождённый путь длины четыре в кубе. Задача поиска наибольшего порождённого пути в гиперкубе известна как задача о змее в коробке.

В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.

Также порождённым циклом называется цикл, являющийся порождённым подграфом G. Порождённые циклы называются также циклами без хорд или (если длина цикла не меньше четырёх) дырами. Антидыра — это дыра в дополнении графа G, то есть антидыра — это дополнение дыры.

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

Пример

На рисунке показан куб, граф с восемью вершинами, двенадцатью рёбрами и порождённым путём длины четыре. Прямой анализ показывает, что не существует более длинного порождённого пути в кубе, хотя существует порождённый цикл длины шесть. Задача поиска наибольшего порождённого пути или цикла в гиперкубе, впервые поставленная Каутцем, известна как задача о змее в коробке и изучалась интенсивно ввиду её использования в теории кодирования и конструировании.

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

Многие важные семейства графов можно описать в терминах порождённых путей или циклов графов в семействе.

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

Алгоритмы и сложность

Задача определения, имеет ли граф G порождённый путь длины не меньшей k, является NP-полной. Гарей и Джонсон высказали этот результат в неопубликованном сообщении Михалису Яннакакису. Однако эту задачу можно решить за полиномиальное время для определённых семейств графов, таких как графы без астероидальных троек или графы без длинных дыр.

Также является NP-полной задачей определение, можно ли разложить вершины графа на два порождённых пути или два порождённых цикла. Как следствие, определение числа порождённых путей графа является NP-трудной задачей.

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

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

Атомарные циклы

Атомарные циклы – это обобщение циклов без хорд. Если задан цикл, n-хорда определяется как путь длины n, содержащий две точки цикла, где n меньше длины кратчайшего пути в цикле, соединяющем эти точки. Если цикл не имеет n-хорд, он называется атомарным циклом, поскольку его нельзя разбить на меньшие циклы. В худшем случае атомарные циклы в графе могут быть перечислены за время O(m²), где m – число рёбер в графе.

Литература

• 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. — С. 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. — С. 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.