Войти
В теории графов неориентированный граф H называется второстепенным графа G, если H может быть образован из G путем удаления ребер и вершин и стягивания ребер.
Теория миноров графа началась с теоремы Вагнера о том, что граф плоский тогда и только тогда, когда его миноры не включают ни полный граф K5, ни полный двудольный граф K 3,3. Из теоремы Робертсона – Сеймура следует, что аналогичная запрещенная второстепенная характеризация существует для каждого свойства графов, которое сохраняется при удалении и сжатии ребер. Для каждого фиксированного графа H можно проверить, является ли H минором входного графа G за полиномиальное время ; вместе с запрещенной второстепенной характеристикой это означает, что каждое свойство графа, сохраняемое удалениями и сжатиями, может быть распознано за полиномиальное время.
Другие результаты и предположения, касающиеся миноров графа, включают теорему о структуре графа, согласно к которому графы, в которых H не является второстепенным, могут быть сформированы путем склеивания более простых частей, и гипотеза Хадвигера, связывающая невозможность раскрасить граф с существованием большого полный график как второстепенный. Важные варианты миноров графа включают топологические миноры и миноры погружения.
Сужение края это операция, которая удаляет ребро из графа, одновременно объединяя две вершины, которые он использовал для соединения. неориентированный граф H является второстепенным по отношению к другому неориентированному графу G, если граф, изоморфный H, может быть получен из G путем сжатия некоторых ребер, удаления некоторых ребер и удаления некоторых изолированных вершин. Порядок, в котором последовательность таких сокращений и удалений выполняется на G, не влияет на результирующий граф H.
Миноры графа часто изучаются в более общем контексте миноров матроидов. В этом контексте принято считать, что все графы связаны, с разрешенными петлями и несколькими ребрами (то есть они являются мультиграфами, а не простые графики); сокращение цикла и удаление отрезка среза - запрещенные операции. Эта точка зрения имеет то преимущество, что при удалении ребер ранг графа остается неизменным, а при сжатии ребер ранг всегда уменьшается на единицу.
В других контекстах (например, при изучении псевдолеса ) имеет смысл разрешить удаление края и разрешить несвязанные графы, но запретить мультиграфы. В этом варианте теории второстепенных графов граф всегда упрощается после любого сокращения ребер, чтобы исключить его петли и множественные ребра.
Функция f называется «минорно-монотонной», если, когда H равно минор группы G, то f (H) ≤ f (G).
В следующем примере граф H является второстепенным по отношению к графу G:
H. 
Г. 
Это показано на следующей диаграмме. Сначала постройте подграф графа G, удалив пунктирные ребра (и полученную изолированную вершину), а затем сожмите серое ребро (объединяя две вершины, которые он соединяет):
Это просто для проверки того, что второстепенное отношение графа образует частичный порядок на классах изоморфизма неориентированных графов: это транзитивный (второстепенный минор G является minor самой G), а G и H могут быть минорами друг друга, только если они изоморфны, потому что любая нетривиальная малая операция удаляет ребра или вершины. глубокий результат от Нила Робертсона и Пола Сеймура утверждает, что этот частичный порядок на самом деле является хорошо квазиупорядоченным : если бесконечное дан список G 1, G 2,... конечных графов, тогда всегда существуют два индекса i < j such that Gi является второстепенным для G j. Другой эквивалентный способ заявить об этом состоит в том, что любой набор графов может иметь только конечное число минимальных элементов при меньшем порядке. Этот результат доказал гипотезу, ранее известную как гипотеза Вагнера после Клауса Вагнера ; Вагнер предположил ее задолго до этого, но опубликовал ее только в 1970 году.
В ходе своего доказательства Сеймур и Робертсон также доказывают теорему о структуре графа, в которой они определяют, для любого фиксированного граф H, грубая структура любого графа, в котором H не является второстепенным. Формулировка теоремы сама по себе длинная и сложная, но вкратце она устанавливает, что такой граф должен иметь структуру клик-сумма меньших графов, которые незначительно изменены из графов встроенных на поверхностях ограниченного рода. Таким образом, их теория устанавливает фундаментальные связи между минорами графов и топологическими вложениями графов.
Для любого графа H простые H-минорные графы должны быть разреженными, что означает, что количество ребер меньше некоторого постоянного кратного количества вершин. Более конкретно, если H имеет h вершин, то простой граф с n вершинами, не содержащий H-минор, может иметь не более 
Гипотеза Хадвигера в теории графов предполагает, что если граф G не содержит минор, изоморфный полному графу на k вершинах, то G имеет правильную раскраску с k - 1 цвет. Случай k = 5 - это повторение теоремы о четырех цветах. Гипотеза Хадвигера доказана для k ≤ 6, но в общем случае неизвестна. Боллобас, Катлин и Эрдеш (1980) называют это «одной из самых глубоких нерешенных проблем в теории графов». Другой результат, связывающий теорему о четырех цветах с минорами графов, - это теорема Снарка, объявленная Робертсоном, Сандерсом, Сеймуром и Томасом, усиление теоремы о четырех цветах, выдвинутой У. T. Tutte и заявляет, что любой безмостовой 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 5 - это в точности 3-клика. -суммы планарных графов и восьмивершинный граф Вагнера, тогда как K 3,3 -свободные графы являются в точности 2-клик-суммами планарных графов и K 5.
Граф H называется топологическим минором графа G, если подраздел графа H изоморфен в подграф графа G. Легко видеть, что каждый топологический минор также является второстепенным. Обратное, однако, в целом неверно (например, полный граф K5в графе Петерсена является второстепенным, но не топологическим), но справедливо для графа с максимальной степенью не выше, чем 3.
Топологическое минорное отношение не является хорошо квазиупорядоченным на множестве конечных графов, и, следовательно, результат Робертсона и Сеймура не применим к топологическим минорам. Однако легко построить конечные запрещенные второстепенные топологические характеристики из конечных запрещенных второстепенных характеризаций, заменив каждое множество ветвей с 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 рёберно непересекающимися путями.
Отношение миноров погружения является хорошо квазиупорядоченным на множестве конечных графов, и, следовательно, результат Робертсона и Сеймура применим к минорам погружения. Кроме того, это означает, что каждое замкнутое семейство миноров погружения характеризуется конечным семейством запрещенных миноров погружения.
В чертеже графа второстепенные погружения возникают как планаризации неплоских графов : из чертежа графа на плоскости, с пересечениями можно сформировать минор погружения, заменяя каждую точку пересечения новой вершиной и в процессе также разделяя каждое пересеченное ребро на путь. Это позволяет распространить методы рисования для планарных графов на неплоские графы.
A мелкие миноры графа G являются второстепенными, в которых ребра G, сжатые для образования второстепенные образуют набор непересекающихся подграфов с малым диаметром диаметром. Мелкие миноры интерполируют между теориями миноров и подграфов графов, в которых мелкие миноры с большой глубиной совпадают с обычным типом миноров графов, в то время как мелкие миноры с нулевой глубиной являются в точности подграфами. Они также позволяют распространить теорию миноров графов на классы графов, такие как 1-планарные графы, которые не замкнуты при взятии миноров.
Альтернативным и эквивалентным определением минора графа является то, что H является минором графа G, если вершины H могут быть представлены набором вершинно-непересекающихся поддеревьев G, так что если две вершины смежны в H, существует ребро с его конечными точками в соответствующих двух деревьях в G. An ограничивает это определение, добавляя условия четности к этим поддеревьям. Если H представлен набором поддеревьев G, как указано выше, то H является нечетным минором G, когда можно назначить два цвета вершинам G таким образом, чтобы каждое ребро G в поддереве было правильно окрашено (его конечные точки имеют разные цвета), и каждое ребро G, которое представляет собой смежность между двумя поддеревьями, является монохроматическим (оба его конечных точки одного цвета). В отличие от обычного вида миноров графов, графы с запрещенными нечетными минорами не обязательно являются разреженными. Гипотеза Хадвигера о том, что k-хроматические графы обязательно содержат k-вершинные полные графы в качестве миноров, также изучалась с точки зрения нечетных миноров.
Другое основанное на четности расширение понятия миноров графа - это понятие a, которое дает двудольный граф всякий раз, когда начальный граф является двудольным. Граф H является двудольным минором другого графа G, если H может быть получен из G путем удаления вершин, удаления ребер и сворачивания пар вершин, находящихся на расстоянии два друг от друга вдоль периферийного цикла графа график. Форма теоремы Вагнера применяется для двудольных миноров: двудольный граф G является плоским графом тогда и только тогда, когда он не имеет графа полезности K 3,3 как двудольный минор.
Проблема принятия решения о том, содержит ли граф G в качестве минора H, является NP-полной в целом ; например, если H является циклическим графом с тем же числом вершин, что и G, то H является минором G тогда и только тогда, когда G содержит гамильтонов цикл. Однако, когда G является частью входных данных, но H фиксировано, ее можно решить за полиномиальное время. Более конкретно, время выполнения проверки того, является ли H второстепенным по отношению к G, в этом случае составляет O (n), где n - количество вершин в G, а запись big O скрывает константу, которая сверхэкспоненциально зависит на H; после первоначального результата Graph Minors, этот алгоритм был улучшен до O (n) раз. Таким образом, применяя алгоритм полиномиального времени для проверки того, содержит ли данный граф какой-либо из запрещенных миноров, теоретически возможно распознать членов любого минорно-замкнутого семейства за полиномиальное время. Этот результат не используется на практике, поскольку скрытая константа настолько велика (для выражения требуется три уровня нотации Кнута со стрелкой вверх ), что исключает любое приложение, что делает его галактическим алгоритмом. Кроме того, чтобы применить этот результат конструктивно, необходимо знать, что такое запрещенные миноры семейства графов. В некоторых случаях запрещенные миноры известны или могут быть вычислены.
В случае, когда H является фиксированным плоским графом, мы можем проверить за линейное время во входном графе G является ли H второстепенным по сравнению с G. В случаях, когда H не фиксировано, известны более быстрые алгоритмы в случае, когда G является плоским.
