График минор - Graph minor

В теория графов, неориентированный граф ЧАС называется незначительный графика грамм если ЧАС может быть сформирован из грамм удалив ребра и вершины и сужающиеся края.

Теория миноров графов началась с Теорема Вагнера что график планарный тогда и только тогда, когда его несовершеннолетние не включают ни полный график K5 ни полный двудольный граф K3,3.[1] В Теорема Робертсона – Сеймура означает, что аналогичный запрещенная второстепенная характеристика существует для каждого свойства графов, которое сохраняется при удалении и сжатии ребер.[2]Для каждого фиксированного графика ЧАС, можно проверить, ЧАС является минором входного графа грамм в полиномиальное время;[3] вместе с запрещенным второстепенным описанием это означает, что каждое свойство графа, сохраняемое удалениями и сжатиями, может быть распознано за полиномиальное время.[4]

Другие результаты и гипотезы, касающиеся миноров графов, включают теорема о структуре графа, согласно которому графики, не имеющие ЧАС как минор может быть сформирован путем склеивания более простых частей, и Гипотеза Хадвигера относительно неспособности раскрасить график к существованию большого полный график как второстепенный. Важные варианты миноров графа включают топологические миноры и миноры погружения.

Определения

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

Миноры графов часто изучаются в более общем контексте несовершеннолетние матроиды. В этом контексте принято считать, что все графы связаны с петли и несколько краев разрешены (то есть они мультиграфы а не простые графики); сокращение петли и удаление передовой запрещенные операции. Эта точка зрения имеет то преимущество, что при удалении краев классифицировать графа без изменений, а стягивания ребер всегда уменьшают ранг на единицу.

В других контекстах (например, при изучении псевдолеса ) имеет больше смысла разрешить удаление среза и разрешить несвязные графы, но запретить мультиграфы. В этом варианте теории второстепенных графов граф всегда упрощается после любого сокращения ребер, чтобы исключить его петли и множественные ребра.[5]

Функция ж называется "минорно-монотонным", если, когда ЧАС является несовершеннолетним из грамм, то f (H) ≤ f (G).

Пример

В следующем примере граф H является второстепенным графа G:

ЧАС. график H

ГРАММ. граф G

Следующая диаграмма иллюстрирует это. Сначала создайте подграф графа G, удалив пунктирные ребра (и полученную изолированную вершину), а затем сожмите серое ребро (объединяя две вершины, которые он соединяет):

преобразование из G в H

Основные результаты и предположения

Несложно проверить, что второстепенный граф связь образует частичный заказ на классах изоморфизма неориентированных графов: это переходный (несовершеннолетний или несовершеннолетний грамм является несовершеннолетним из грамм сам), и грамм и ЧАС могут быть минорами друг друга, только если они изоморфны, потому что любая нетривиальная второстепенная операция удаляет ребра или вершины. А глубокий результат к Нил Робертсон и Пол Сеймур заявляет, что этот частичный порядок на самом деле хорошо квазиупорядоченный: если бесконечный список грамм1, грамм2, ... конечных графов, то всегда существуют два индекса я < j такой, что граммя является несовершеннолетним из граммj. Другой эквивалентный способ заявить об этом состоит в том, что любой набор графов может иметь только конечное число минимальные элементы по второстепенному заказу.[6] Этот результат доказал гипотезу, ранее известную как гипотеза Вагнера, после Клаус Вагнер; Вагнер догадался об этом задолго до этого, но опубликовал его только в 1970 году.[7]

В ходе доказательства Сеймур и Робертсон также доказывают, что теорема о структуре графа в котором они определяют, для любого фиксированного графа ЧАС, грубая структура любого графа, не имеющего ЧАС как несовершеннолетний. Формулировка теоремы сама по себе длинна и сложна, но вкратце устанавливает, что такой граф должен иметь структуру кликовая сумма меньших графов, которые незначительно изменены из графов встроенный на поверхностях ограниченного род Таким образом, их теория устанавливает фундаментальные связи между минорами графов и топологические вложения графиков.[8]

Для любого графика ЧАС, простой ЧАС-безминорные графы должны быть редкий, что означает, что количество ребер меньше некоторого постоянного кратного количества вершин.[9] В частности, если ЧАС имеет час вершины, то простой п-vertex простой ЧАС-безминорный граф может иметь не более края, а некоторые Kчас-безминорные графы имеют по крайней мере такое же количество ребер.[10] Таким образом, если ЧАС имеет час вершины, то ЧАС-без минорные графики имеют среднюю степень и, кроме того вырождение . Кроме того, ЧАС-безминорные графы имеют теорему о разделителе, аналогичную теореме теорема о плоском сепараторе для плоских графов: для любых фиксированных ЧАС, и любые п-вертекс ЧАС-без минорный график грамм, можно найти подмножество вершины, удаление которых разбивает грамм на два (возможно, несвязных) подграфа с не более чем 2п/ 3 вершины на подграф.[11] Еще сильнее, для любых фиксированных ЧАС, ЧАС-безминорные графы имеют ширина дерева .[12]

В Гипотеза Хадвигера в теории графов предполагает, что если граф грамм не содержит минор, изоморфный полный график на k вершины, то грамм имеет правильная окраска с k - 1 цвет.[13] Дело k = 5 - это повторное утверждение теорема четырех цветов. Гипотеза Хадвигера была доказана для k ≤ 6,[14] но в общем случае неизвестно. Боллобас, Катлин и Эрдеш (1980) назовем это «одной из самых глубоких нерешенных проблем теории графов». Еще один результат, связывающий теорему о четырех цветах с минорами графов, - это теорема Снарка объявленное Робертсоном, Сандерсом, Сеймуром и Томасом усиление теоремы о четырех цветах, предположенной В. Т. Тутте и заявляя, что любой без моста 3-регулярный граф это требует четырех цветов в окраска края должен иметь Граф Петерсена как несовершеннолетний.[15]

Семейства минор-замкнутых графов

Дополнительная информация о семействах минорных замкнутых графов, включая список некоторых из них: Теорема Робертсона – Сеймура

Многие семейства графов обладают тем свойством, что каждый минор графа в F также в F; такой класс называется минор-закрыто. Например, в любом планарный граф, или любой встраивание графа на фиксированной топологическая поверхность, ни удаление краев, ни сжатие краев не могут увеличить род вложения; поэтому плоские графы и графы, вложимые на любую фиксированную поверхность, образуют минно-замкнутые семейства.

Если F является минорно-замкнутым семейством, то (из-за свойства квазиупорядоченности миноров) среди графов, не принадлежащих F есть конечное множество Икс минорно-минимальных графов. Эти графики запрещенные несовершеннолетние за F: граф принадлежит F тогда и только тогда, когда он не содержит как второстепенный какой-либо граф в Икс. То есть каждая несовершеннолетняя замкнутая семья F можно охарактеризовать как семью Икс-безминорные графы для некоторого конечного множества Икс запрещенных несовершеннолетних.[2]Самый известный пример характеристики этого типа - Теорема Вагнера характеризуя планарные графы как графы, не имеющие K5 ни K3,3 как несовершеннолетние.[1]

В некоторых случаях свойства графов в минорно-замкнутом семействе могут быть тесно связаны со свойствами их исключенных миноров. Например, семейство минорно-замкнутых графов F ограничил ширина пути тогда и только тогда, когда запрещенные несовершеннолетние включают лес,[16] F ограничил глубина дерева тогда и только тогда, когда его запрещенные младшие включают несвязный союз графы путей, F ограничил ширина дерева тогда и только тогда, когда запрещенные несовершеннолетние включают планарный граф,[17] и F имеет ограниченную локальную ширину дерева (функциональная связь между диаметр и treewidth) тогда и только тогда, когда его запрещенные младшие элементы включают вершина графика (граф, который можно сделать планарным, удалив одну вершину).[18] Если ЧАС может быть нарисован в плоскости только с одним пересечением (то есть имеет номер перехода один) затем ЧАС-Графы без минорной структуры имеют упрощенную структурную теорему, в которой они формируются как суммы клик планарных графов и графов ограниченной древовидной ширины.[19] Например, оба K5 и K3,3 пересечения номер один, и, как показал Вагнер, K5-свободные графы - это в точности 3-кликовые суммы плоских графов и восьмивершинные График Вагнера, в то время как K3,3-свободные графы - это в точности 2-клик-суммы плоских графов иK5.[20]

Вариации

Топологические несовершеннолетние

График ЧАС называется топологический минор графа грамм если подразделение из ЧАС является изоморфный к подграф из грамм.[21] Легко видеть, что каждый топологический минор также является минором. Обратное, однако, в целом неверно (например, полный график K5 в Граф Петерсена является второстепенным, но не топологическим), но справедливо для графа с максимальной степенью не выше трех.[22]

Топологическое минорное отношение не является квазиупорядоченным на множестве конечных графов.[23] и, следовательно, результат Робертсона и Сеймура неприменим к топологическим минорам. Однако легко построить конечные запрещенные второстепенные топологические характеристики из конечных запрещенных второстепенных характеристик, заменив каждое множество ветвей на k исходящие ребра каждым деревом на k листья со степенью опускания не менее двух.

Индуцированные несовершеннолетние

График ЧАС называется индуцированный несовершеннолетний графа грамм если его можно получить из индуцированного подграфа грамм сокращая края. Иначе, грамм как говорят ЧАС-индуцированный несовершеннолетний-свободный.[24]

Погружение минор

Операция с графом называется подъем занимает центральное место в концепции, называемой погружения. В подъем - операция на смежных ребрах. Учитывая три вершины v, ты, и ш, куда (v, u) и (u, w) ребра в графе, поднятие vuw, или эквивалент (v, u), (u, w) это операция, которая удаляет два ребра (v, u) и (u, w) и добавляет край (v, w). В случае, когда (v, w) уже присутствовал, v и ш теперь будет соединяться более чем одним ребром, и, следовательно, эта операция по сути является операцией с несколькими графами.

В случае, если граф ЧАС можно получить из графика грамм последовательностью подъемных операций (на грамм), а затем, найдя изоморфный подграф, скажем, что ЧАС это минор погружения грамм.Есть еще один способ определения миноров погружения, который эквивалентен операции подъема. Мы говорим что ЧАС это минор погружения грамм если существует инъективное отображение из вершин в ЧАС к вершинам в грамм где изображения смежных элементов ЧАС связаны в грамм рёберно непересекающимися путями.

Отношение миноров погружения - это хорошо квазиупорядочение на множестве конечных графов, и, следовательно, результат Робертсона и Сеймура применим к минорам погружения. Кроме того, это означает, что каждое замкнутое семейство миноров погружения характеризуется конечным семейством запрещенных миноров погружения.

В рисунок графика, несовершеннолетние погружения возникают как планаризации из неплоские графы: из чертежа графа на плоскости с пересечениями можно сформировать минор погружения, заменив каждую точку пересечения на новую вершину и в процессе также разделив каждое пересеченное ребро на путь. Это позволяет распространить методы рисования для плоских графов на неплоские графы.[25]

Мелкие несовершеннолетние

А мелкий минор графа грамм минор, в котором края грамм которые были сжаты, чтобы сформировать второстепенную форму набора непересекающихся подграфов с низкими диаметр. Мелкие миноры интерполируют между теориями миноров и подграфов графов, в которых мелкие миноры с большой глубиной совпадают с обычным типом миноров графов, в то время как мелкие миноры с нулевой глубиной являются в точности подграфами.[26] Они также позволяют распространить теорию миноров графов на классы графов, такие как 1-планарные графы которые не закрываются на прием несовершеннолетних.[27]

Условия паритета

Альтернативное и эквивалентное определение минора графа: ЧАС является несовершеннолетним из грамм всякий раз, когда вершины ЧАС может быть представлен набором вершинно-непересекающихся поддеревьев грамм, такое, что если две вершины смежны в ЧАС, существует ребро с концами в соответствующих двух деревьях в грамм.An странный минор ограничивает это определение, добавляя к этим поддеревьям условия четности. Если ЧАС представлен набором поддеревьев грамм как указано выше, то ЧАС это странный несовершеннолетний из грамм если возможно назначить два цвета вершинам грамм таким образом, чтобы каждый край грамм внутри поддерева правильно окрашены (его конечные точки имеют разные цвета), и каждый край грамм который представляет собой смежность между двумя поддеревьями, является монохроматическим (обе его конечные точки одного цвета). В отличие от обычного вида миноров графов, графы с запрещенными нечетными минорами не обязательно являются разреженными.[28] В Гипотеза Хадвигера, который k-хроматические графы обязательно содержат k-вертекс полные графики как несовершеннолетние, также изучалась с точки зрения нечетных несовершеннолетних.[29]

Другое основанное на четности расширение понятия миноров графов - это концепция двудольный минор, что дает двудольный граф если исходный граф двудольный. График ЧАС является двудольным минором другого графа грамм в любое время ЧАС можно получить из грамм путем удаления вершин, ребер и сворачивания пар вершин, находящихся на расстоянии два друг от друга вдоль периферический цикл графа. Форма Теорема Вагнера применяется для двудольных миноров: двудольный граф грамм это планарный граф тогда и только тогда, когда у него нет график полезности K3,3 как двудольный несовершеннолетний.[30]

Алгоритмы

Проблема решение ли график грамм содержит ЧАС как несовершеннолетний является NP-полным в целом; например, если ЧАС это график цикла с тем же количеством вершин, что и грамм, тогда ЧАС является несовершеннолетним из грамм если и только если грамм содержит Гамильтонов цикл. Однако когда грамм является частью ввода, но ЧАС фиксировано, ее можно решить за полиномиальное время. В частности, время работы для проверки того, ЧАС является несовершеннолетним из грамм в этом случае О(п3), куда п это количество вершин в грамм и нотация большой O скрывает константу, сверхэкспоненциально зависящую от ЧАС;[3] после получения исходного результата Graph Minors, этот алгоритм был улучшен до О(п2) время.[31] Таким образом, применяя алгоритм полиномиального времени для проверки того, содержит ли данный граф какой-либо из запрещенных миноров, теоретически возможно распознать членов любого минорно-замкнутого семейства в полиномиальное время. Этот результат не используется на практике, поскольку скрытая константа очень велика (требуются три уровня Обозначение Кнута со стрелкой вверх выразить), чтобы исключить любое приложение, делая его галактический алгоритм.[32] Кроме того, чтобы применить этот результат конструктивно, необходимо знать, что такое запрещенные миноры семейства графов.[4] В некоторых случаях запрещенные несовершеннолетние известны или могут быть вычислены.[33]

В случае, когда ЧАС фиксированный планарный граф, то мы можем протестировать за линейное время во входном графе грамм ли ЧАС является несовершеннолетним из грамм.[34] В случаях, когда ЧАС не фиксируется, известны более быстрые алгоритмы в случае, когда грамм плоский.[35]

Примечания

  1. ^ а б Ловас (2006), п. 77; Вагнер (1937a).
  2. ^ а б Ловас (2006), теорема 4, с. 78; Робертсон и Сеймур (2004).
  3. ^ а б Робертсон и Сеймур (1995).
  4. ^ а б Товарищи и Лэнгстон (1988).
  5. ^ Ловас (2006) не согласен с тем, разрешать ли петли и множественные смежности: он пишет на стр. 76, что «разрешены параллельные края и петли», но на стр. 77 он утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольника. K3 как минор », справедливо только для простых графиков.
  6. ^ Дистель (2005), Глава 12: Несовершеннолетние, деревья и WQO; Робертсон и Сеймур (2004).
  7. ^ Ловас (2006), п. 76.
  8. ^ Ловас (2006), стр. 80–82; Робертсон и Сеймур (2003).
  9. ^ Мадер (1967).
  10. ^ Косточка (1982); Косточка (1984); Томасон (1984); Томасон (2001).
  11. ^ Алон, Сеймур и Томас (1990); Плоткин, Рао и Смит (1994); Рид и Вуд (2009).
  12. ^ Grohe (2003)
  13. ^ Хадвигер (1943).
  14. ^ Робертсон, Сеймур и Томас (1993).
  15. ^ Томас (1999); Пегг (2002).
  16. ^ Робертсон и Сеймур (1983).
  17. ^ Ловас (2006), Теорема 9, с. 81; Робертсон и Сеймур (1986).
  18. ^ Эппштейн (2000); Демейн и Хаджиагайи (2004).
  19. ^ Робертсон и Сеймур (1993); Демейн, Хаджиагайи и Тиликос (2002).
  20. ^ Вагнер (1937a); Вагнер (1937b); Холл (1943).
  21. ^ Diestel 2005, п. 20
  22. ^ Diestel 2005, п. 22
  23. ^ Дин (1996).
  24. ^ Błasiok et al.
  25. ^ Buchheim et al. (2014).
  26. ^ Нешетржил и Оссона де Мендес (2012).
  27. ^ Нешетржил и Оссона де Мендес (2012) С. 319–321.
  28. ^ Каварабаяси, Кен-ичи; Рид, Брюс; Воллан, Пол (2011), "Малый алгоритм графа с условиями четности", 52-й ежегодный симпозиум IEEE по основам компьютерных наук, Институт инженеров по электротехнике и радиоэлектронике, стр. 27–36, Дои:10.1109 / focs.2011.52, S2CID  17385711.
  29. ^ Гилен, Джим; Джерардс, Берт; Рид, Брюс; Сеймур, Пол; Ветта, Адриан (2009), "О нечетно-минорном варианте гипотезы Хадвигера", Журнал комбинаторной теории, Серия B, 99 (1): 20–29, Дои:10.1016 / j.jctb.2008.03.006, МИСТЕР  2467815.
  30. ^ Чудновский, Мария; Калаи, Гил; Нево, Эран; Новик, Изабелла; Сеймур, Пол (2016), «Двусторонние несовершеннолетние», Журнал комбинаторной теории, Серия B, 116: 219–228, arXiv:1312.0210, Дои:10.1016 / j.jctb.2015.08.001, МИСТЕР  3425242, S2CID  14571660.
  31. ^ Каварабаяши, Кобаяши и Рид (2012).
  32. ^ Джонсон, Дэвид С. (1987). «Колонка NP-полноты: Постоянное руководство (выпуск 19)». Журнал алгоритмов. 8 (2): 285–303. CiteSeerX  10.1.1.114.3864. Дои:10.1016/0196-6774(87)90043-5.
  33. ^ Бодлендер, Ханс Л. (1993). «Путеводитель по Treewidth» (PDF). Acta Cybernetica. 11: 1–21. См. Конец раздела 5.
  34. ^ Бодлендер, Ханс Л. (1993). «Путеводитель по Treewidth» (PDF). Acta Cybernetica. 11: 1–21. Первый абзац после теоремы 5.3.
  35. ^ Адлер, Изольда; Дорн, Фредерик; Фомин, Федор В .; Сау, Игнаси; Тиликос, Димитриос М. (01.09.2012). «Быстрое второстепенное тестирование в плоских графах» (PDF). Алгоритмика. 64 (1): 69–84. Дои:10.1007 / s00453-011-9563-9. ISSN  0178-4617. S2CID  6204674.

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

внешняя ссылка