Порождённый путь
Из Википедии, свободной энциклопедии
Из Википедии, свободной энциклопедии
В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.
Также порождённым циклом называется цикл, являющийся порождённым подграфом G. Порождённые циклы называются также циклами без хорд или (если длина цикла не меньше четырёх) дырами. Антидыра — это дыра в дополнении графа G, то есть антидыра — это дополнение дыры.
Длину наибольшего порождённого пути в графе иногда называют числом обхода графа[1]. Для разреженных графов существование ограниченного числа обхода эквивалентно существованию ограниченной глубины дерева[2]. Порождённым числом обхода графа G называется наименьшее число подмножеств вершин, на которые можно разложить вершины графа, чтобы каждое подмножество образовывало порождённый путь[3], и это понятие тесно связано с числом покрытия путями — минимальное число несвязных путей, являющихся порождёнными подграфами G, покрывающих все вершины G[4]. Обхват графа — это длина его кратчайшего цикла, но этот цикл должен быть порождённым циклом, так как любая хорда могла бы образовать более короткий цикл. По тем же причинам нечётным обхватом графа называется длина его кратчайшего нечётного порождённого цикла.
На рисунке показан куб, граф с восемью вершинами, двенадцатью рёбрами и порождённым путём длины четыре. Прямой анализ показывает, что не существует более длинного порождённого пути в кубе, хотя существует порождённый цикл длины шесть. Задача поиска наибольшего порождённого пути или цикла в гиперкубе, впервые поставленная Каутцем[5], известна как задача о змее в коробке и изучалась интенсивно ввиду её использования в теории кодирования и конструировании.
Многие важные семейства графов можно описать в терминах порождённых путей или циклов графов в семействе.
Задача определения, имеет ли граф G порождённый путь длины не меньшей k, является NP-полной. Гарей и Джонсон[6] высказали этот результат в неопубликованном сообщении Михалису Яннакакису. Однако эту задачу можно решить за полиномиальное время для определённых семейств графов, таких как графы без астероидальных троек[7] или графы без длинных дыр[8].
Также является NP-полной задачей определение, можно ли разложить вершины графа на два порождённых пути или два порождённых цикла[9]. Как следствие, определение числа порождённых путей графа является NP-трудной задачей.
Сложность задач аппроксимации наибольшего порождённого пути или цикла можно связать с задачей поиска наибольших независимых множеств в графах[10].
Дыры (и антидыры в графах без циклов длины 5 без хорд) в графе с n вершинами и m рёбрами могут быть найдены за время (n+m2)[11].
Атомарные циклы – это обобщение циклов без хорд. Если задан цикл, n-хорда определяется как путь длины n, содержащий две точки цикла, где n меньше длины кратчайшего пути в цикле, соединяющем эти точки. Если цикл не имеет n-хорд, он называется атомарным циклом, поскольку его нельзя разбить на меньшие циклы[12]. В худшем случае атомарные циклы в графе могут быть перечислены за время O(m2), где m – число рёбер в графе.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
