WikiSort.ru - Не сортированное

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

Теория миноров графов началась с теоремы Вагнера, гласящей, что граф планарен в том и только в том случае, когда в его миноры не входят ни в полный граф K₅, ни в полный двудольный граф K_3,3^[1][2]. Из теоремы Роберсона — Сеймура следует, что аналоги характеризации запрещёнными минорами существуют для любого свойства графов, которые сохраняются при удалениях и стягивании рёбер^[3][4].

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

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

Определения

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

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

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

Пример

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

H.

G.

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

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

Можно легко проверить, что отношение миноров графов образует частичный порядок на классе изоморфизмов неориентированных графов — отношение транзитивно (минор минора графа G является сам минором G) и графы G и H могут быть минорами друг друга если они изоморфны, поскольку любая нетривиальная операция с минором удаляет рёбра или вершины. Глубокий результат Нейла Робертсона^[en] и Пола Сеймура^[en] утверждает, что этот частичный порядок является, на самом деле, вполне квазиупорядоченным^[en] — если задан бесконечный список G₁, G₂,... конечных графов, всегда существуют два индекса i < j, такие что G_i является минором графа G_j. Эквивалентная формулировка утверждения — любое множество графов может иметь лишь конечное число минимальных элементов по минорному отношению^[8]. Этот результат доказывает гипотезу, до этого известную как гипотеза Вагнера. Вагнер^[en] высказал гипотезу много раньше, но опубликовал её лишь в 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}})}$ и, кроме того, вырождение^[en] ${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$ . Вдобавок, свободные от H-миноров графы имеют теорему о сепараторе, подобную теореме о сепараторе^[en] в планарном графе — для любого фиксированного 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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.