Граф минор

В теории графов неориентированный граф H называется минором графа G, если H можно образовать из G путем удаления ребер, вершин и стягивания ребер .

Теория миноров графа началась с теоремы Вагнера о том, что граф планарен тогда и только тогда, когда его миноры не включают ни полный граф K ₅ , ни полный двудольный граф K _3,3 . Теорема Робертсона-Сеймура подразумевает, что аналогичная запрещенная второстепенная характеристика существует для каждого свойства графов, которое сохраняется за счет удаления и сжатия ребер. Для каждого фиксированного графа H можно проверить, является ли H минором входного графа G за полиномиальное время ; вместе с запрещенной второстепенной характеристикой это означает, что каждое свойство графа, сохраненное за счет удалений и сокращений, может быть распознано за полиномиальное время.

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

Определения

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

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

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

Функция f называется «минорно-монотонной», если всякий раз, когда H является минором G , выполняется f ( H ) ≤ f ( G ) .

Пример

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

ЧАС.

Г.

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

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

Непосредственно проверяется, что минорное отношение графа образует частичный порядок на классах изоморфизма конечных неориентированных графов: оно транзитивно (минор минора G является минором самого G ), а G и H могут быть только минорами. друг друга, если они изоморфны, поскольку любая нетривиальная второстепенная операция удаляет ребра или вершины. Глубокий результат Нила Робертсона и Пола Сеймура что этот частичный порядок на самом деле является квазиупорядочением : если бесконечный список ( G1 _{гласит ,} , G2 _{хорошим} ,...) задан конечных графов, то всегда существуют два индекса i < j такой, что G _i является минором G _j . Другой эквивалентный способ выразить это состоит в том, что любой набор графов может иметь только конечное число минимальных элементов при минорном порядке. Этот результат доказал гипотезу, ранее известную как гипотеза Вагнера в честь Клауса Вагнера ; Вагнер выдвинул эту гипотезу гораздо раньше, но опубликовал ее только в 1970 году.

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

Для любого графа H простые графы без H -миноров должны быть разреженными , что означает, что количество ребер меньше некоторого постоянного кратного числа вершин. Точнее, если H имеет h вершин, то простой граф с n -вершинами и простой H -минорный граф может иметь не более $\scriptstyle O(nh{\sqrt {\log h}})$ ребер, а некоторые K _{h имеют по крайней мере такое же количество ребер.} графы без миноров Таким образом, если H имеет h вершин, то H -безминорные графы имеют среднюю степень $\scriptstyle O(h{\sqrt {\log h}})$ и еще вырождение $\scriptstyle O(h{\sqrt {\log h}})$. Кроме того, графы без H -миноров имеют теорему о сепараторе, аналогичную теореме о плоском сепараторе для плоских графов: для любого фиксированного H и любого n -вершинного H -минорного графа G можно найти подмножество $\scriptstyle O({\sqrt {n}})$ вершины, удаление которых разбивает G на два (возможно, несвязных) подграфа с не более чем 2 n ⁄ 3 вершины на подграф. Более того, для любого фиксированного H графы H без миноров имеют древовидную ширину. $\scriptstyle O({\sqrt {n}})$.

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

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

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

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

Если F — минорно-замкнутое семейство, то (в силу свойства хорошей квазиупорядоченности миноров) среди графов, не принадлежащих F, существует конечное множество X минорно-минимальных графов. Эти графы являются запрещенными минорами для F : граф принадлежит F когда он не содержит в качестве минора ни одного графа из X. тогда и только тогда , То есть каждое минорно-замкнутое семейство F можно охарактеризовать как семейство X -безминорных графов для некоторого конечного множества X запрещенных миноров. Самый известный пример характеристики этого типа — теорема Вагнера, характеризующая плоские графы как графы, не имеющие ни K ₅ , ни K _3,3 в качестве миноров.

В некоторых случаях свойства графов в минорно-замкнутом семействе могут быть тесно связаны со свойствами их исключенных миноров. Например, семейство F с замкнутыми минорными графами имеет ограниченную ширину пути тогда и только тогда, когда его запрещенные миноры включают в себя лес . F имеет ограниченную глубину дерева тогда и только тогда, когда его запрещенные миноры включают в себя несвязное объединение графов путей . F имеет ограниченную ширину дерева тогда и только тогда, когда его запрещенные миноры включают в себя планарный граф . и F имеет ограниченную локальную ширину дерева (функциональную связь между диаметром и шириной дерева) тогда и только тогда, когда его запрещенные миноры включают вершинный граф (граф, который можно сделать плоским, удалив одну вершину). Если H можно нарисовать на плоскости только с одним пересечением (то есть, у него есть пересечение номер один), то графы без H -миноров имеют упрощенную структурную теорему, в которой они формируются как клик-суммы планарных графов и графов. ограниченной ширины дерева. Например, и K _5, и K _3,3 имеют пересечение номер один, и, как показал Вагнер, графы, свободные от K _5, представляют собой в точности 3-кликовые суммы планарных графов и восьмивершинного графа Вагнера , в то время как K _{3, 3-} свободные графы — это в точности 2-кликовые суммы планарных графов и K ₅ .

Вариации

Топологические миноры

Граф H называется минором графа G если подразделение H , изоморфно ​ подграфу ​ G топологическим . Каждый топологический минор также является минором. Обратное, однако, неверно в общем случае (например, полный граф K ₅ в графе Петерсена является минорным, но не топологическим), но справедливо для графа с максимальной степенью не выше трех.

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

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

Граф H называется индуцированным минором графа G , если его можно получить из индуцированного подграфа G стягиванием ребер. В противном случае G называется H -индуцированной минорной свободной группой.

Погружение незначительное

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

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

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

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

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

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

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

Альтернативное и эквивалентное определение минора графа состоит в том, что H является минором графа G всякий раз, когда вершины H могут быть представлены набором непересекающихся по вершинам поддеревьев G , так что если две вершины смежны в H , существует ребро с его концами в соответствующих двух деревьях в G .Нечетный минор ограничивает это определение, добавляя к этим поддеревьям условия четности. Если H представлено набором поддеревьев G, как указано выше, то H является нечетным минором G , если возможно присвоить два цвета вершинам G таким образом, чтобы каждое ребро G внутри поддерева было правильно раскрашено. (его конечные точки имеют разные цвета), и каждое ребро G , представляющее смежность между двумя поддеревьями, является одноцветным (обе его конечные точки имеют один и тот же цвет). В отличие от обычных миноров графа, графы с запрещенными нечетными минорами не обязательно являются разреженными. о Гипотеза Хадвигера том, что k -хроматические графы обязательно содержат k -вершинные полные графы в качестве миноров, также изучалась с точки зрения нечетных миноров.

Другим расширением понятия миноров графа, основанным на четности, является концепция двудольного минора , которая создает двудольный граф всякий раз, когда начальный граф является двудольным. Граф H является двудольным минором другого графа G, если H можно получить из G удалением вершин, удалением ребер и схлопыванием пар вершин, находящихся на расстоянии двух друг от друга вдоль периферийного цикла графа. Форма теоремы Вагнера применима к двудольным минорам: Двудольный граф G является планарным графом тогда и только тогда, когда он не имеет графа полезности K _3,3 в качестве двудольного минора.

Алгоритмы

Проблема определения ли граф G того, содержит H в качестве минора, в общем случае является NP-полной; например, если H — граф циклов с тем же количеством вершин, что и G , то H — минор графа G тогда и только тогда, когда G содержит гамильтонов цикл . Однако, когда G является частью входных данных, но H фиксировано, ее можно решить за полиномиальное время. Более конкретно, время выполнения проверки того, является ли H минорным по отношению к G, в этом случае равно O ( n ³ ), где n — количество вершин в G , а за большим обозначением O скрывается константа, которая суперэкспоненциально зависит от H ; с момента исходного результата Graph Minors этот алгоритм был улучшен до O ( n ² ) время. Таким образом, применяя алгоритм полиномиального времени для проверки того, содержит ли данный граф какой-либо из запрещенных миноров, теоретически возможно распознавать членов любого минорно-замкнутого семейства за полиномиальное время . Этот результат не используется на практике, поскольку скрытая константа настолько велика (для выражения требуется три слоя нотации Кнута со стрелкой вверх ), что исключает любое применение, что делает его галактическим алгоритмом . Более того, чтобы конструктивно применить этот результат, необходимо знать, что такое запрещенные миноры семейства графов. В некоторых случаях запрещенные несовершеннолетние известны или могут быть вычислены.

В случае, когда H — фиксированный планарный граф , мы можем за линейное время проверить во входном графе G, ли H минором G. является В случаях, когда H не фиксировано, известны более быстрые алгоритмы в случае, когда G планарна.

Ссылки

• Алон, Нога ; Сеймур, Пол ; Томас, Робин (1990), «Теорема о разделителе для неплоских графов», Журнал Американского математического общества , 3 (4): 801–808, doi : 10.2307/1990903 , JSTOR   1990903 , MR   1065053 .
• Бласёк, Ярослав; Каминский, Марцин; Раймон, Жан-Флоран; Транк, Теофиль (2015), Индуцированные миноры и хороший квазиупорядочение , arXiv : 1510.07135 , Бибкод : 2015arXiv151007135B .
• Боллобас, Б. ; Кэтлин, Пенсильвания; Эрдеш, Пол (1980), «Гипотеза Хадвигера верна почти для каждого графа», European Journal of Combinatorics , 1 (3): 195–199, doi : 10.1016/s0195-6698(80)80001-1 .
• Буххайм, Кристоф; Чимани, Маркус; Гутвенгер, Карстен; Юнгер, Майкл; Мутцель, Петра (2014), «Пересечения и планаризация», Тамассия, Роберто (ред.), Справочник по рисованию и визуализации графиков , Дискретная математика и ее приложения (Бока-Ратон), CRC Press, Бока-Ратон, Флорида .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги (2004), «Диаметр и ширина дерева в семействах второстепенных замкнутых графов, пересмотренный вариант» , Algorithmica , 40 (3): 211–215, doi : 10.1007/s00453-004-1106-1 , S2CID   390856 .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2002), «1,5-аппроксимация древовидной ширины графов, исключая граф с одним второстепенным пересечением», Proc. 5-й международный семинар по аппроксимационным алгоритмам для комбинаторной оптимизации (APPROX 2002) , Конспекты лекций по информатике, том. 2462, Springer-Verlag, стр. 67–80, номер документа : 10.1007/3-540-45753-4_8.
• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-3-540-26183-4 .
• Дин, Гуоли (1996), «Исключая длинный двойной путь», Журнал комбинаторной теории , серия B, 66 (1): 11–23, doi : 10.1006/jctb.1996.0002 , MR   1368512 .
• Эппштейн, Дэвид (2000), «Диаметр и ширина дерева в семействах младших замкнутых графов», Algorithmica , 27 (3): 275–291, arXiv : math.CO/9907126 , doi : 10.1007/s004530010020 , MR   1759751 , S2CID   3172160 .
• Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1988), «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время», Journal of the ACM , 35 (3): 727–739, doi : 10.1145/44483.44491 , S2CID   16587284 .
• Гроэ, Мартин (2003), «Локальная ширина дерева, исключенные миноры и алгоритмы аппроксимации», Combinatorica , 23 (4): 613–632, arXiv : math/0001128 , doi : 10.1007/s00493-003-0037-9 , S2CID   11751235 .
• Хадвигер, Хьюго (1943), «О классификации комплексов маршрутов», Quarterjschr. Натуралист Гес Цюрих , 88 : 133–143 .
• Холл, Дик Вик (1943), «Заметки о примитивных кривых перекоса», Бюллетень Американского математического общества , 49 (12): 935–936, doi : 10.1090/S0002-9904-1943-08065-2 .
• Каварабаяси, Кеничи ; Кобаяши, Юсуке; Рид, Брюс (март 2012 г.), «Проблема непересекающихся путей в квадратичном времени», Журнал комбинаторной теории, серия B , 102 (2): 424–435, doi : 10.1016/j.jctb.2011.07.004
• Косточка, Александр В. (1982), "Минимальное число Хадвигера для графов с заданной средней степенью вершин", Методы Дискрет. Анализ. (на русском языке), 38 : 37–58 .
• Косточка, Александр В. (1984), «Нижняя граница числа графов Хадвигера по их средней степени», Combinatorica , 4 (4): 307–316, doi : 10.1007/BF02579141 , S2CID   15736799 .
• Ловас, Ласло (2006), «Теория графовых миноров», Бюллетень Американского математического общества , 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8 .
• Мадер, Вольфганг (1967), «Свойства гомоморфизма и средняя плотность ребер графов», Mathematical Annals , 174 (4): 265–268, doi : 10.1007/BF01364272 , S2CID   120261785 .
• Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Springer, стр. 62–65, номер документа : 10.1007/978-3-642-27875-4 , ISBN.  978-3-642-27874-7 , МР   2920058 .
• Пегг, Эд-младший (2002), «Рецензия на книгу: Колоссальная книга по математике» (PDF) , Уведомления Американского математического общества , 49 (9): 1084–1086, Бибкод : 2002ITED...49.1084A , doi : 10.1109/ТЭД.2002.1003756 .
• Плоткин, Серж; Рао, Сатиш; Смит, Уоррен Д. (1994), «Неглубоко исключенные несовершеннолетние и улучшенное разложение графов», Proc. 5-й симпозиум ACM – SIAM. по дискретным алгоритмам (SODA 1994) , стр. 462–470 .
• Рид, Брюс ; Вуд, Дэвид Р. (2009), «Алгоритм с линейным временем для поиска разделителя в графе, исключающий минор», Транзакции ACM в алгоритмах , 5 (4): Статья 39, doi : 10.1145/1597036.1597043 , S2CID   760001 .
• Робертсон, Нил ; Сеймур, Пол (1983), «Минорные графы. I. Исключение леса», Журнал комбинаторной теории, серия B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5 .
• Робертсон, Нил ; Сеймур, Пол Д. (1986), «Минорные графы. V. Исключение плоского графа», Journal of Combinatorial Theory, Series B , 41 (1): 92–114, doi : 10.1016/0095-8956(86)90030- 4
• Робертсон, Нил ; Сеймур, Пол Д. (1993), «Исключая граф с одним пересечением», Робертсон, Нил; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорным графам , Современная математика, том. 147, Американское математическое общество , стр. 669–675 .
• Робертсон, Нил ; Сеймур, Пол Д. (1995), «Незначительные графы. XIII. Проблема непересекающихся путей», Журнал комбинаторной теории, серия B , 63 (1): 65–110, doi : 10.1006/jctb.1995.1006 .
• Робертсон, Нил ; Сеймур, Пол Д. (2003), «Незначительные графы. XVI. Исключение неплоского графа», Журнал комбинаторной теории, серия B , 89 (1): 43–76, doi : 10.1016/S0095-8956(03) 00042-Х .
• Робертсон, Нил ; Сеймур, Пол Д. (2004), «Незначительные графы. XX. Гипотеза Вагнера», Журнал комбинаторной теории, серия B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001 .
• Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (1993), «Гипотеза Хадвигера для K ₆ графов, свободных от » (PDF) , Combinatorica , 13 (3): 279–361, doi : 10.1007/BF01202354 , S2CID   9608738 .
• Томас, Робин (1999), «Недавние исключенные второстепенные теоремы для графов», Обзоры по комбинаторике, 1999 (Кентербери) (PDF) , London Math. Соц. Лекционная конспект. Сер., т. 1, с. 267, Кембридж: Кембриджский университет. Пресс, стр. 201–222, МР   1725004 .
• Томасон, Эндрю (1984), «Экстремальная функция для сжатия графов», Mathematical Proceedings of the Cambridge Philosophical Society , 95 (2): 261–265, Бибкод : 1983MPCPS..95..261T , doi : 10.1017/S0305004100061521 , S2CID   124801301 .
• Томасон, Эндрю (2001), «Экстремальная функция для полных миноров», Журнал комбинаторной теории, серия B , 81 (2): 318–338, doi : 10.1006/jctb.2000.2013 .
• Вагнер, Клаус (1937а), «О свойстве плоских комплексов», Ann. , 114 : 570–590, doi : 10.1007/BF01594196 , S2CID   123534907 .
• Вагнер, Клаус (1937b), «О расширении теоремы Куратовского», German Mathematics , 2 : 280–285 .

Внешние ссылки

• Вайсштейн, Эрик В. «Граф Минор» . Математический мир .