Миноры графов и Теорема Робертсона-Сеймура: Глобальный взгляд на топологию

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

Классическим примером здесь является Теорема Куратовского (и родственная ей Теорема Вагнера), которая гласит, что граф планарен (его можно нарисовать на плоскости без самопересечений) тогда и только тогда, когда он не содержит в качестве минора ни графа K5 (полного графа на 5 вершинах), ни графа K3,3 (домики и колодцы). K5 и K3,3 выступают здесь как "запрещенные миноры".

В период с 1983 по 2004 год Нил Робертсон и Пол Сеймур опубликовали серию из 20 научных статей общим объемом более 500 страниц, доказывая Теорему о минорах графов. Она утверждает невероятный факт: любое семейство графов, которое замкнуто относительно взятия миноров (то есть, если граф принадлежит семейству, то и все его миноры принадлежат семейству), может быть полностью охарактеризовано конечным набором запрещенных миноров!

Для планарных графов этот набор состоит из 2 элементов (K5 и K3,3). Для графов, которые можно нарисовать на поверхности тора (бублика), этот набор состоит из более чем 16 000 графов, но он все равно конечен.

Следствия этой теоремы для информатики ошеломляют. В рамках работы Робертсон и Сеймур доказали, что проверка того, содержит ли большой граф заданный фиксированный минор, решается за полиномиальное время O(N^3). Это означает, что для огромного количества NP-трудных задач математически гарантированно существуют быстрые полиномиальные алгоритмы. Загвоздка лишь в том, что доказательство неконструктивно: теорема говорит нам, что алгоритм существует и набор запрещенных миноров конечен, но не дает нам никакого способа найти эти миноры и написать сам код!