Минор графа

Минор в теории графов — граф для заданного графа , который может быть образован из удалением рёбер и вершин и стягиванием рёбер.

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

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

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

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

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

В других контекстах (как, например, при изучении псевдолесов) имеет смысл разрешить удаление разрезающих рёбер и позволить графам быть несвязными, но при этом имеет смысл запретить мультиграфы. В таком варианте теории миноров графов граф всегда упрощается после любого стягивания ребра для исключения петель и кратных рёберЛоваш () противоречит сам себе. На странице 76 он пишет, что «параллельные рёбра и петли разрешаются», но на странице 77 от утверждает, что «граф является лесом тогда и только тогда, когда он не содержит треугольника K3 в качестве минора», что верно только для простых графов.

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

H.

G.

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

Основные результаты и гипотезы Можно легко проверить, что отношение миноров графов образует частичный порядок на классе изоморфизмов неориентированных графов — отношение транзитивно (минор минора графа G является сам минором G) и графы G и H могут быть минорами друг друга если они изоморфны, поскольку любая нетривиальная операция с минором удаляет рёбра или вершины. Глубокий результат и Пола Сеймура утверждает, что этот частичный порядок является, на самом деле,  — если задан бесконечный список G1, G2,… конечных графов, всегда существуют два индекса i < j, такие что Gi является минором графа Gj. Эквивалентная формулировка утверждения — любое множество графов может иметь лишь конечное число минимальных элементов по минорному отношению, Chapter 12: Minors, Trees, and WQO; .. Этот результат доказывает гипотезу, до этого известную как гипотеза Вагнера. Вагнер высказал гипотезу много раньше, но опубликовал её лишь в 1970.

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

Для любого графа H простые свободные от миноров H графы должны быть редкими, что означает, что число рёбер меньше некоторой константы, умноженной на число вершин. Конкретнее, если H имеет h вершин, то простой n-вершинный свободный от H-миноров граф может иметь не более рёбер, а некоторые свободные от Kh миноров графы имеют по меньшей мере такое число рёбер; ; .. Так, если H имеет h вершин, то свободные от H-миноров графы имеют среднюю степень и, кроме того, вырожденность . Вдобавок, свободные от H-миноров графы имеют теорему о разбиении, подобную теореме о разбиении в планарном графе — для любого фиксированного H, и любого n-вершинного свободного от H-миноров графа G можно найти подмножество вершин размером , удаление которого делит граф G на два (возможно несвязных) подграфа с максимум 2n/3 вершинами в каждом; ; .. Даже более строго, для любого фиксированного H свободные от H-миноров графы имеют древовидную ширину .

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

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

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

Если F является минорно замкнутым семейством, то (ввиду свойства вполне квазиупорядоченности миноров) среди графов, не принадлежащих F, существует конечное множество X минорно минимальных графов. Эти графы являются запрещёнными минорами для F — граф принадлежит множеству F тогда и только тогда, когда он не содержит в качестве миноров любой граф из X. Таким образом, любое минорно замкнутое семейство F может быть охарактеризовано как семейство свободных от миноров из X графов для некоторого конечного множества X запрещённых миноров.

Хорошо известным примером характеризации такого типа является Теорема Вагнера, характеризующая планарные графы как графы, не имеющие ни K5, ни K3,3 в качестве миноров .

В некоторых случаях свойства графов в минорно замкнутом семействе могут быть тесно связаны со свойствами исключённых миноров. Например, минорно замкнутое семейство графов F имеет ограниченную путевую ширину тогда и только тогда, когда запрещённые семейства включают лес , F имеет ограниченную древовидную глубину тогда и только тогда, когда запрещённые миноры включают разъединённое объединение путей, F имеет ограниченную древовидную ширину тогда и только тогда, когда его запрещённые миноры включают планарный граф, Theorem 9, p. 81; ., и F имеет ограниченную локальную древовидную ширину (функциональную связь между диаметром и древовидной шириной) тогда и только тогда, когда его запрещённые миноры включают верхушечный граф (граф, который становится планарным при удалении одной вершины). Если H может быть нарисован на плоскости с единственным пересечением (то есть, число пересечений графа равно единице), то для свободных от H-миноров графов верна теорема об упрощённой структуре, по которой такие графы представляют собой кликовую сумму планарных графов и графов с ограниченной древовидной шириной. Например, как K5, так и K3,3 имеют число пересечений, равное единице, и как показал Вагнер, свободные от K5 графы — это в точности 3-кликовые суммы планарных графов и восьмивершинного графа Вагнера, в то время как свободные от K3,3 графы — это в точности 2-кликовые суммы планарных графов и K5; ..

Вариации

Топологические миноры Граф H называется топологическим минором графа G, если граф подразбиений графа H изоморфен подграфу графа G . Легко видеть, что любой топологический минор является минором (в обычном смысле). Обратное, однако, в общем случае неверно (например, полный граф K5 в графе Петерсена является минором, но не является топологическим минором), но выполняется для графа с максимальной степенью, не превосходящей трёх.

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

Погружённый минор Операция с графом, называемая подъёмом, является центральным понятием в концепции погружения. Подъём является операцией со смежными рёбрами. Если заданы три вершины 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-планарные графы, которые не замкнуты по взятию миноров.

Алгоритмы