В математической области теории графов индуцированный путь в неориентированном графе G — это путь , который является индуцированным подграфом графа G. То есть это последовательность вершин в G , такая что каждые две смежные вершины в последовательности соединены ребром в G , а каждые две несмежные вершины в последовательности не соединены никаким ребром в G. Индуцированный путь иногда называют змеей , а задача нахождения длинных индуцированных путей в графах гиперкуба известна как задача «змея в коробке» .
Аналогично, индуцированный цикл — это цикл , который является индуцированным подграфом графа G ; индуцированные циклы также называются циклами без хорд или (когда длина цикла равна четырем или более) дырами . Антидыра — это дыра в дополнении к графу G , т. е. антидыра — это дополнение дыры.
Длина самого длинного индуцированного пути в графе иногда называется числом обхода графа; [1] для разреженных графов наличие ограниченного числа обхода эквивалентно наличию ограниченной глубины дерева . [2] Число индуцированного пути графа G — это наименьшее число индуцированных путей, на которые могут быть разбиты вершины графа, [3] а тесно связанное с ним число покрытия путей графа G — это наименьшее число индуцированных путей, которые вместе включают все вершины G. [ 4] Обхват графа — это длина его кратчайшего цикла, но этот цикл должен быть индуцированным циклом, поскольку любая хорда может быть использована для создания более короткого цикла; по аналогичным причинам нечетный обхват графа также является длиной его кратчайшего нечетного индуцированного цикла.
На иллюстрации изображен куб, граф с восемью вершинами и двенадцатью ребрами, а также индуцированный путь длины четыре в этом графе. Прямой анализ случая показывает, что в кубе больше не может быть индуцированного пути, хотя он имеет индуцированный цикл длины шесть. Задача нахождения самого длинного индуцированного пути или цикла в гиперкубе, впервые поставленная Каутцем (1958), известна как задача о змее в коробке , и она широко изучалась из-за ее приложений в теории кодирования и инженерии.
Многие важные семейства графов можно охарактеризовать с точки зрения индуцированных путей или циклов графов в семействе.
Для графа G и параметра k NP-полной задачей является определение того, имеет ли граф индуцированный путь длины не менее k . Garey & Johnson (1979) приписывают этот результат неопубликованному сообщению Mihalis Yannakakis . Однако эта задача может быть решена за полиномиальное время для некоторых семейств графов, таких как графы без астероидных тройников [5] или графы без длинных дыр. [6]
Также NP-полной является задача определения того, можно ли разбить вершины графа на два индуцированных пути или два индуцированных цикла. [7] Как следствие, определение числа индуцированных путей графа является NP-трудной задачей.
Сложность аппроксимации задач на самый длинный индуцированный путь или цикл может быть связана со сложностью нахождения больших независимых множеств в графах с помощью следующего сокращения. [8] Из любого графа G с n вершинами сформируйте другой граф H с вдвое большим количеством вершин, чем G , добавив к G n ( n − 1)/2 вершин, имеющих по два соседа каждая, по одному для каждой пары вершин в G. Тогда, если G имеет независимое множество размера k , H должен иметь индуцированный путь и индуцированный цикл длины 2 k , образованные чередованием вершин независимого множества в G с вершинами I. Обратно, если H имеет индуцированный путь или цикл длины k , любой максимальный набор несмежных вершин в G из этого пути или цикла образует независимое множество в G размера не менее k /3. Таким образом, размер максимального независимого множества в G находится в пределах постоянного множителя размера самого длинного индуцированного пути и самого длинного индуцированного цикла в H. Следовательно, согласно результатам Хастада (1996) о неаппроксимируемости независимых множеств, если только NP=ZPP, не существует полиномиального алгоритма для аппроксимации самого длинного индуцированного пути или самого длинного индуцированного цикла с точностью до множителя O( n 1/2-ε ) оптимального решения.
Дыры (и антидыры в графах без хордовых циклов длины 5) в графе с n вершинами и m ребрами могут быть обнаружены за время (n+m 2 ). [9]
Атомарные циклы являются обобщением хордовых циклов, которые не содержат n -хорд. Для некоторого цикла n -хорда определяется как путь длины n, соединяющий две точки на цикле, где n меньше длины кратчайшего пути на цикле, соединяющего эти точки. Если цикл не имеет n -хорд, он называется атомарным циклом, потому что его нельзя разложить на меньшие циклы. [10] В худшем случае атомарные циклы в графе можно перечислить за время O( m 2 ), где m — количество ребер в графе.