Индуцированный путь

В математической области теории графов индуцированный путь в неориентированном графе 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 ² ). ^[9]

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