Введение

Субграф с сокращенными ребрами

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

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

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

Просто проверить, что отношение миноров графов образует частичный порядок на классах изоморфизма конечных неориентированных графов: оно транзитивно (минор минора графа G является минором самого G), и G и H могут быть минорами друг другу только если они изоморфны, поскольку любая нетривиальная операция миноризации удаляет рёбра или вершины. Глубокий результат Нила Робертсона и Пола Сеймура утверждает, что этот частичный порядок является, фактически, квазипорядком: если задан бесконечный список конечных графов, то всегда существуют два индекса i < j такие, что является минором . Другой эквивалентный способ сформулировать это: любой набор графов может иметь лишь конечное число минимальных элементов относительно отношения миноризации. Этот результат доказал гипотезу, ранее известную как гипотеза Вагнера, названную в честь Клауса Вагнера; Вагнер выдвинул её значительно раньше, но опубликовал лишь в 1970 году. В ходе доказательства Сеймур и Робертсон также доказали теорему о структуре графов, в которой они определяют для любого фиксированного графа H грубую структуру любого графа, не имеющего H в качестве минора. Формулировка теоремы сама по себе длинная и сложная, но, вкратце, она устанавливает, что такой граф должен иметь структуру кликовой суммы меньших графов, модифицированных незначительными способами из графов, вложенных на поверхности ограниченного рода. Таким образом, их теория устанавливает фундаментальные связи между минорами графов и топологическими вложениями графов. Для любого графа H, простые H-минор-свободные графы должны быть разреженными, то есть число рёбер меньше некоторой постоянной доли числа вершин. Более конкретно, если H имеет h вершин, то простой n-вершинный простой H-минор-свободный граф может иметь не более рёбер, и некоторые H-минор-свободные графы имеют как минимум столько рёбер. Следовательно, если H имеет h вершин, то H-минор-свободные графы имеют среднюю степень и, кроме того, дегенерацию. Кроме того, H-минор-свободные графы обладают теоремой о сепараторах, аналогичной теореме о сепараторах для планарных графов: для любого фиксированного H и любого n-вершинного H-минор-свободного графа G можно найти подмножество вершин, удаление которого разбивает G на два (возможно, несвязных) подграфа с не более вершинами в каждом подграфе. Более того, для любого фиксированного H, H-минор-свободные графы имеют древесную ширину. Гипотеза Хадвигера в теории графов утверждает, что если граф G не содержит минор, изоморфный полному графу на k вершинах, то G допускает правильную раскраску в k – 1 цветов. Случай k = 5 является переформулировкой теоремы о четырёх цветах. Гипотеза Хадвигера доказана для k ≤ 6, но остаётся нерешённой в общем случае. Её называют "одной из самых глубоких нерешённых проблем в теории графов". Другим результатом, связывающим теорему о четырёх цветах с минорами графов, является теорема о снарках, объявленная Робертсоном, Сандерсом, Сеймуром и Томасом, которая является усилением теоремы о четырёх цветах, предложенной У. Т. Тютте, и утверждающая, что любой мостонеразложимый 3-регулярный граф, требующий четыре цвета при раскраске рёбер, должен иметь граф Петерсена в качестве минора.

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

Многие семейства графов обладают свойством, что каждый минор графа из F также принадлежит F; такой класс называется минорно-замкнутым. Например, в любом планарном графе или в любом вложении графа на фиксированной топологической поверхности ни удаление рёбер, ни стягивание рёбер не могут увеличить род вложения; следовательно, планарные графы и графы, вкладываемые на любую фиксированную поверхность, образуют минорно-замкнутые семейства. Если F – минорно-замкнутое семейство, то (в силу свойства хорошего квазипорядка миноров) среди графов, не принадлежащих F, существует конечное множество X минорно-минимальных графов. Эти графы являются запрещёнными минорами для F: граф принадлежит F тогда и только тогда, когда он не содержит в качестве минора ни одного графа из X. То есть, каждое минорно-замкнутое семейство F может быть охарактеризовано как семейство графов, свободных от миноров из X, для некоторого конечного множества X запрещённых миноров. F имеет ограниченную глубину дерева тогда и только тогда, когда его запрещённые миноры включают в себя дизъюнктное объединение путей, F имеет ограниченную ширину дерева тогда и только тогда, когда его запрещённые миноры включают в себя планарный граф, и F имеет ограниченную локальную ширину дерева (функциональную зависимость между диаметром и шириной дерева) тогда и только тогда, когда его запрещённые миноры включают в себя апексный граф (граф, который можно сделать планарным путём удаления одной вершины). Если H можно нарисовать на плоскости только с одним пересечением (то есть, он имеет число пересечений, равное одному), то графы, свободные от миноров H, имеют упрощённую теорему о структуре, согласно которой они формируются как суммы клик планарных графов и графов с ограниченной шириной дерева. Например, и K5, и K3,3 имеют число пересечений, равное одному, и, как показал Вагнер, графы, свободные от K5, являются точно 3-кликовыми суммами планарных графов и восьмивершинного графа Вагнера, в то время как графы, свободные от K3,3, являются точно 2-кликовыми суммами планарных графов и K5.

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

Граф H называется топологическим минором графа G, если существует подразделение H, изоморфное подграфу G. Любой топологический минор также является минором. Однако, обратное не всегда верно (например, полный граф K5 в графе Петерсена является минором, но не топологическим), но верно для графов с максимальной степенью, не превышающей трех. Отношение топологического минора не является квазиупорядочением на множестве конечных графов, и, следовательно, результат Робертсона и Сеймура не применим к топологическим минорам. Однако, можно непосредственно построить конечные запрещенные характеристики топологических миноров из конечных запрещенных характеристик миноров, заменяя каждый набор ветвей с 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 является планарным графом тогда и только тогда, когда он не содержит граф полезности K3,3 в качестве двухдольного минора.

Алгоритмы

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