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