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

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

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

Точно так же индуцированный цикл это цикл это индуцированный подграф в г; индуцированные циклы также называют бесхордовые циклы или (когда продолжительность цикла четыре и более) дыры. 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 (м²) время, где м количество ребер в графе.

Примечания

1. Бакли и Харари (1988).
2. Нешетржил и Оссона де Мендес (2012), Предложение 6.4, с. 122.
3. Chartrand et al. (1994).
4. Бариоли, Фаллат и Хогбен (2004).
5. Крач, Мюллер и Тодинка (2003).
6. Гаврил (2002).
7. Ле, Ле и Мюллер (2003).
8. Берман и Шнитгер (1992).
9. Николопулос и Палиос (2004).
10. Гашлер и Мартинес (2012).

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

• Бариоли, Франческо; Фаллат, Шон; Хогбен, Лесли (2004). «Вычисление минимального ранга и числа путей для некоторых графов» (PDF). Линейная алгебра и ее приложения. 392: 289–303. Дои:10.1016 / j.laa.2004.06.019.
• Берман, Петр; Шнитгер, Георг (1992). «О сложности аппроксимации задачи независимого множества». Информация и вычисления. 96 (1): 77–94. Дои:10.1016 / 0890-5401 (92) 90056-Л.
• Бакли, Фред; Харари, Фрэнк (1988). «О наиболее длинных индуцированных путях в графах». Китайский ежеквартальный математический журнал. 3 (3): 61–65.
• Чартран, Гэри; Макканна, Джозеф; Шервани, Навид; Хоссейн, Моаззем; Хашми, Джахангир (1994). «Индуцированное число путей двудольных графов». Ars Combinatoria. 37: 191–208.
• Гарей, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и непреодолимость: руководство по теории NP-полноты. В. Х. Фриман. п.196.
• Гашлер, Майкл; Мартинес, Тони (2012). «Надежное обучение коллектора с CycleCut» (PDF). Связь Наука. 24 (1): 57–69. Дои:10.1080/09540091.2012.664122.
• Гаврил, Фэника (2002). «Алгоритмы для индуцированных путей максимального веса». Письма об обработке информации. 81 (4): 203–208. Дои:10.1016 / S0020-0190 (01) 00222-8.
• Хостад, Йохан (1996). "Клику трудно приблизить к п^{1 − ε}". Материалы 37-го ежегодного симпозиума IEEE по основам компьютерных наук. С. 627–636. Дои:10.1109 / SFCS.1996.548522.
• Каутц, Уильям Х. (Июнь 1958 г.). «Коды проверки ошибок единичного расстояния». Операции IRE на электронных компьютерах. ИС-7 (2): 179–180. Дои:10.1109 / TEC.1958.5222529. S2CID  26649532.
• Крач, Дитер; Мюллер, Хайко; Тодинка, Иоан (2003). «Набор вершин обратной связи и самый длинный индуцированный путь на графах без AT». Теоретико-графические концепции в информатике. Берлин: конспект лекций по информатике, Vol. 2880, Springer-Verlag. С. 309–321. Дои:10.1007 / b93953. Архивировано из оригинал 25 ноября 2006 г.
• Ле, Хоанг-Оан; Ле, Ван Банг; Мюллер, Хайко (2003). «Разбиение графа на непересекающиеся индуцированные пути или циклы» (PDF). Дискретная прикладная математика. Второй международный коллоквиум "Journées de l'Informatique Messine", Мец, 2000 г. 131 (1): 199–212. Дои:10.1016 / S0166-218X (02) 00425-0. Архивировано из оригинал (PDF) на 03.03.2016.
• Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012). «Глава 6. Деревья с ограниченной высотой и глубиной дерева». Разреженность: графики, структуры и алгоритмы. Алгоритмы и комбинаторика. 28. Гейдельберг: Springer. С. 115–144. Дои:10.1007/978-3-642-27875-4. ISBN  978-3-642-27874-7. Г-Н  2920058.
• Николопулос, Ставрос Д .; Палиос, Леонид (2004). «Обнаружение дырок и дырок на графиках». Материалы 15-го симпозиума ACM-SIAM по дискретным алгоритмам. С. 850–859.