Минор графа

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

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

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

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

H.

G.

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

Можно легко проверить, что отношение миноров графов образует частичный порядок на классе изоморфизмов неориентированных графов — отношение транзитивно (минор минора графа G является сам минором G) и графы G и H могут быть минорами друг друга если они изоморфны, поскольку любая нетривиальная операция с минором удаляет рёбра или вершины. Глубокий результат Нейла Робертсона и Пола Сеймура утверждает, что этот частичный порядок является, на самом деле, вполне квазиупорядоченным — если задан бесконечный список G₁, G₂,… конечных графов, всегда существуют два индекса i < j, такие что G_i является минором графа G_j. Эквивалентная формулировка утверждения — любое множество графов может иметь лишь конечное число минимальных элементов по минорному отношению[8]. Этот результат доказывает гипотезу, до этого известную как гипотеза Вагнера. Вагнер высказал гипотезу много раньше, но опубликовал её лишь в 1970[9].

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

Для любого графа H простые свободные от миноров H графы должны быть редкими, что означает, что число рёбер меньше некоторой константы, умноженной на число вершин[12]. Конкретнее, если H имеет h вершин, то простой n-вершинный свободный от H-миноров граф может иметь не более ${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$ рёбер, а некоторые свободные от K_h миноров графы имеют по меньшей мере такое число рёбер[13]. Так, если H имеет h вершин, то свободные от H-миноров графы имеют среднюю степень ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ и, кроме того, вырожденность ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$. Вдобавок, свободные от H-миноров графы имеют теорему о разбиении, подобную теореме о разбиении в планарном графе — для любого фиксированного H, и любого n-вершинного свободного от H-миноров графа G можно найти подмножество вершин размером ${\displaystyle \scriptstyle O({\sqrt {n}})}$, удаление которого делит граф G на два (возможно несвязных) подграфа с максимум 2n/3 вершинами в каждом[14]. Даже более строго, для любого фиксированного H свободные от H-миноров графы имеют древесную ширину ${\displaystyle \scriptstyle O({\sqrt {n}})}$[15].

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

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

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

Хорошо известным примером характеризации такого типа является Теорема Вагнера, характеризующая планарные графы как графы, не имеющие ни K₅, ни K_3,3 в качестве миноров [1][2].

В некоторых случаях свойства графов в минорно замкнутом семействе может быть тесно связана со свойствами исключённых миноров. Например, минорно замкнутое семейство графов F имеет ограниченную путевую тогда и только тогда, когда запрещённые семейство семейства включает лес [22], F имеет ограниченную глубину дерева тогда и только тогда, когда запрещённые миноры включают разъединённое объединение путей, F имеет ограниченную древесную ширину тогда и только тогда, когда его запрещённые миноры включают планарный граф[23], и F имеет ограниченную локальную древесную ширину (функциональную связь между диаметром и древесной шириной) тогда и только тогда, когда его запрещённые миноры включают верхушечный граф (граф, который становится планарным при удалении одной вершины)[24][25]. Если H может быть нарисован на плоскости с единственным пересечением (то есть, число пересечений графа равно единице), то для свободных от H-миноров графов верна теорема об упрощённой структуре, по которой такие графы представляют собой кликовую сумму планарных графов и графов с ограниченной древесной шириной[26][27]. Например, как K₅, так и K_3,3 имеют число пересечений, равное единице, и как показал Вагнер, свободные от K₅ графы — это в точности 3-кликовые суммы планарных графов и восьмивершинного графа Вагнера, в то время как свободные от K_3,3 графы — это в точности 2-кликовые суммы планарных графов и K₅[28].

Задача разрешимости, содержится ли граф H в графе G в качестве минора является, в общем случае, NP-полной. Например, если H является циклом с тем же числом вершин, что и у G, то H является минором графа G тогда и только тогда, когда G содержит гамильтонов граф. Однако, если G является входным, а H фиксирован, задача может быть решена за полиномиальное время. Конкретнее, время работы проверки, является ли H минором графа G в этом случае равно O(n³), где n — число вершин в G, а O большое прячет константу, которая зависит суперэкспоненциально от H[5]. Вследствие результата о минорах графа этот алгоритм улучшается до O(n²)[35]. Таким образом, при применении алгоритма с полиномиальным временем работы для проверки, содержит ли заданный граф какой-либо из запрещённых миноров, можно распознать члены любого минорно замкнутого семейства за полиномиальное время. Однако, чтобы применять этот результат конструктивно, необходимо знать запрещённые миноры семейства графов[6].

• Weisstein, Eric W. Graph Minor (англ.) на сайте Wolfram MathWorld.