Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Пример [ править ]

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

Характеристика семейств графов [ править ]

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

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

Алгоритмы и сложность [ править ]

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

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

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

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

Атомные циклы [ править ]

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

Заметки [ править ]

  1. ^ Бакли и Харари (1988) .
  2. ^ Nešetřil & Ossona де Мендес (2012) , предложение 6.4, стр. 122.
  3. ^ Chartrand et al. (1994) .
  4. ^ Barioli, Fallat & Хогбен (2004) .
  5. ^ Kratsch, Müller & Todinca (2003) .
  6. Перейти ↑ Gavril (2002) .
  7. Перейти ↑ Le, Le & Müller (2003) .
  8. ^ Berman & Schnitger (1992) .
  9. ^ Николопулос и Палиос (2004) .
  10. ^ Gashler & Martinez (2012) .

Ссылки [ править ]

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