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

Индуцированный путь длины четыре в куб. Нахождение самого длинного индуцированного пути в гиперкубе известно как змея в коробке проблема.

в математический зона теория графов, индуцированный путь в неориентированном графе г это дорожка это индуцированный подграф из г. То есть это последовательность вершин в г такая, что каждые две соседние вершины в последовательности соединены ребром в г, и каждые две несмежные вершины в последовательности не соединены никаким ребром в г. Индуцированный путь иногда называют змея, и проблема поиска длинных индуцированных путей в графы гиперкуба известен как змея в коробке проблема.

Точно так же индуцированный цикл это цикл это индуцированный подграф в г; индуцированные циклы также называют бесхордовые циклы или (когда продолжительность цикла четыре и более) дыры. An антихол это дыра в дополнять из г, т.е. антидыр - это дополнение к дыре.

Длину самого длинного индуцированного пути в графе иногда называют длиной номер объезда графа;^[1] за разреженные графики, наличие ограниченного числа объездных путей эквивалентно ограниченному глубина дерева.^[2] В индуцированный номер пути графа г - наименьшее количество индуцированных путей, на которые можно разбить вершины графа,^[3] и тесно связанные номер покрытия пути из г - наименьшее количество индуцированных путей, которые вместе включают все вершины г.^[4] В обхват графа - это длина его кратчайшего цикла, но этот цикл должен быть индуцированным циклом, так как любой хорд может быть использован для создания более короткого цикла; по аналогичным причинам странный обхват графа - это также длина его кратчайшего нечетного индуцированного цикла.

пример

На иллюстрации показан куб, граф с восемью вершинами и двенадцатью ребрами и индуцированный путь длины четыре в этом графе. Простой анализ случая показывает, что в кубе больше не может быть индуцированного пути, хотя он имеет индуцированный цикл длиной шесть. Проблема поиска самого длинного индуцированного пути или цикла в гиперкубе, впервые поставленная Каутц (1958), известен как змея в коробке проблема, и она широко изучалась в связи с ее приложениями в теории кодирования и инженерии.

Характеристика семейств графов

Многие важные семейства графов можно охарактеризовать с помощью индуцированных путей или циклов графов в семействе.

• Тривиально связные графы без индуцированного пути длины два являются полные графики, а связные графы без индуцированного цикла - это деревья.
• А граф без треугольников - граф без индуцированного цикла длины три.
• В кографы - это в точности графы без индуцированного пути длины три.
• В хордовые графы - это графы без индуцированного цикла длины четыре и более.
• В графы без четных дырок - графы в, не содержащие индуцированных циклов с четным числом вершин.
• В тривиально совершенные графы - это графы, в которых нет ни индуцированного пути длины три, ни индуцированного цикла длины четыре.
• По сильной теореме о совершенном графе идеальные графики - это графики без нечетной дыры и нечетной антидыры.
• В дистанционно-наследственные графы - это графы, в которых каждый индуцированный путь является кратчайшим, и графы, в которых каждые два индуцированных пути между одними и теми же двумя вершинами имеют одинаковую длину.
• В блочные графики - это графы, в которых существует не более одного индуцированного пути между любыми двумя вершинами, а связные блочные графы - это графы, в которых существует ровно один индуцированный путь между каждыми двумя вершинами.

Алгоритмы и сложность

NP-полное определение для графа г и параметр k, имеет ли граф индуцированный путь длины не менее k. Гэри и Джонсон (1979) связывать этот результат с неопубликованным сообщением Михалис Яннакакис. Однако эта проблема может быть решена за полиномиальное время для некоторых семейств графов, таких как графы без астероидов и троек.^[5] или графики без длинных отверстий.^[6]

Также NP-полно, чтобы определить, можно ли разбить вершины графа на два индуцированных пути или два индуцированных цикла.^[7] Как следствие, определение числа индуцированных путей графа является NP-трудным.

Сложность аппроксимации самого длинного индуцированного пути или проблем цикла может быть связана со сложностью поиска больших независимые множества в графах следующей редукцией.^[8] Из любого графика г с п вершины, образуют другой граф ЧАС с вдвое большим количеством вершин, чем г, добавив к г п(п - 1) / 2 вершины, каждая из которых имеет по два соседа, по одному для каждой пары вершин в г. Тогда если г имеет независимый набор размеров k, ЧАС должен иметь индуцированный путь и индуцированный цикл длины 2k, образованный чередующимися вершинами независимого множества в г с вершинами я. Наоборот, если ЧАС имеет индуцированный путь или цикл длины k, любой максимальный набор несмежных вершин в г от этого пути или цикла образует независимый набор в г размером не менее k/ 3. Таким образом, размер максимального независимого множества в г находится в пределах постоянного множителя размера самого длинного индуцированного пути и самого длинного индуцированного цикла в ЧАС. Следовательно, по результатам Хастад (1996) о несовместимости независимых множеств, если NP = ZPP, не существует алгоритма полиномиального времени для аппроксимации самого длинного индуцированного пути или самого длинного индуцированного цикла с точностью до множителя O (п^1/2-ε) оптимального решения.

Дыры (и антидыры в графах без хордовых циклов длины 5) в графе с n вершинами и m ребрами могут быть обнаружены за время (n + m²).^[9]

Атомные циклы

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

Примечания

Рекомендации