В математической области теории графов индуцированный путь в неориентированном графе G — это путь , который является индуцированным подграфом G. То есть это последовательность вершин в G такая, что каждые две соседние вершины в последовательности соединены ребром в G , а каждые две несмежные вершины в последовательности не соединены никаким ребром в G. Индуцированный путь иногда называют змеей , а проблема поиска длинных индуцированных путей в графах гиперкубов известна как проблема «змеи в ящике» .
Аналогично, индуцированный цикл — это цикл , который является индуцированным подграфом G ; индуцированные циклы также называются безхордовыми циклами или (когда длина цикла равна четырем и более) дырками . Антидырка — это дырка в дополнении к G , т. е. антидырка — это дополнение к дырке.
Длину самого длинного индуцированного пути в графе иногда называют числом обхода графа; [1] для разреженных графов ограниченное число обходов эквивалентно ограниченной глубине дерева . [2] Число индуцированных путей графа G — это наименьшее количество индуцированных путей, на которые могут быть разбиты вершины графа, [3] а тесно связанное число покрытий путей графа G — это наименьшее количество индуцированных путей, которые вместе включить все вершины G . [4] Обхват графа — это длина его кратчайшего цикла, но этот цикл должен быть индуцированным циклом, поскольку любая хорда может быть использована для создания более короткого цикла ; по тем же причинам нечетный обхват графа является также длиной его кратчайшего нечетного индуцированного цикла.
На иллюстрации изображен куб, граф с восемью вершинами и двенадцатью ребрами, а также индуцированный путь длиной четыре в этом графе. Простой анализ случая показывает, что в кубе больше не может быть индуцированного пути, хотя у него есть индуцированный цикл длиной шесть. Проблема поиска самого длинного индуцированного пути или цикла в гиперкубе, впервые поставленная Каутцем (1958), известна как проблема «змеи в ящике» и широко изучалась благодаря ее приложениям в теории кодирования и инженерии. .
Многие важные семейства графов можно охарактеризовать с точки зрения индуцированных путей или циклов графов в семействе.
Для графа G и параметра k NP-полно определить, имеет ли граф индуцированный путь длиной не менее k . Гари и Джонсон (1979) приписывают этот результат неопубликованному сообщению Михалиса Яннакакиса . Однако эта проблема может быть решена за полиномиальное время для некоторых семейств графов, таких как графы без тройных астероидов [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 — количество ребер в графе.