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

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

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

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

Определения

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

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

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

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

Пример

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

ЧАС.

ГРАММ.

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

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

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

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

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

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

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

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

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

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

Вариации

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

Граф Н называется топологическим минор графа 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 теперь будут связаны более чем одним ребром, и, следовательно, эта операция по сути является операцией с несколькими графами.

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

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

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

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

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

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

Примечания

использованная литература

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

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