Структурная теорема графов

Структурная теорема графов — фундаментальный результат в теории графов. Результат устанавливает глубокую связь между теорией миноров графов и топологическими вложениями. Теорема была сформулирована в 17 статьях из серии 23 статей Нейла Робертсона и Пола Сеймура. Каварабайаши и Мохар и Ловаш провели обзор теоремы в доступном для неспециалистов виде, описав теорему и её следствия.

Начала и мотивация теоремы

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

Древесная ширина

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

Следствие 1. Для любого планарного графа H существует положительное целое k, такое, что любой H-свободный граф имеет древесную ширину, меньшую k.

Значение k в следствии 1, как правило, много больше древесной ширины H (имеется замечательное исключение, когда H = K₄, то есть H равен полному графу из четырёх вершин, для которого k=3). Это одна из причин, по которой говорят, что структурная теорема описывает "грубую структуру " H-свободных графов.

Вложение в поверхности

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

Если H не планарен, структурная теорема графов может рассматриваться как сильное обобщение теоремы Понтрягина — Куратовского. Версия этой теоремы, доказанная Вагнером, утверждает, что если граф G является как K₅-свободным, так и K_3,3-свободным, то G планарен. Эта теорема даёт "хорошую причину" для графа G не содержать K₅ или K_3,3 в качестве миноров. Конкретнее, G вкладывается в сферу, в то время как ни K₅, ни K_3,3 в сферу вложить нельзя. Понятия "хорошая причина" недостаточно для структурной теоремы графов. Требуются ещё два понятия — суммы по клике и вихри.

Суммы по клике

Клика в графе G — это любое множество вершин, которые попарно смежны друг другу в G. Для неотрицательного целого k k-кликовая сумма двух графов G и K — это любой граф, полученный выбором в графах G и K клик размером m ≤ k для некоторого неотрицательного m, отождествлением этих двух клик в одну клику (размером m) и удалением некоторого (возможно, нулевого) числа рёбер в этой новой клике.

Если G₁, G₂, ..., G_n — список графов, можно получить новый граф путём объединения графов из списка с помощью сумм по k-кликам. То есть создаём k-кликовую сумму графа G₁ и G₂, затем создаём k-кликовую сумму графа G₃ с предыдущим результирующим графом, и т.д. Граф имеет древесную ширину, не превосходящую k , если он может быть получен как k-кликовая сумма некоторого списка графов, в котором каждый граф имеет максимум k + 1 вершин.

Следствие 1 показывает нам, что k-кликовые суммы малых графов описывают грубую структуру H-свободных графов в случае планарности H. Если H непланарен, мы вынуждены рассматривать также k-кликовые суммы графов, каждый из которых вложим в поверхность. Следующий пример с H = K₅ иллюстрирует этот момент. Граф K₅ можно вложить в любую поверхность, за исключением сферы. Однако существуют K₅-свободные графы, которые далеко не планарны. В частности, 3-кликовая сумма любого списка планарных графов даёт K₅-свободный граф. Вагнер определил точную структур K₅-свободных графов как часть группы результатов, известных под названием теорема Вагнера:

Теорема 2. Если G свободен от K₅, то G можно получить как 3-кликовые суммы списка планарных графов и копий некоторого специфичного непланарного графа с 8 вершинами.

Заметим, что Теорема 2 является точной структурной теоремой, поскольку в точности определяет структуру K₅-свободных графов. Такие результаты редки в теории графов. Структурная теорема графов не является точной в том смысле, что для большинства графов H структурное описание H-свободных графов включает некоторые графы, не являющиеся H-свободными.

Вихри (грубое описание)

Имеется искушение предположить, что выполняется аналог теоремы 2 для графов H, отличных от K₅. Возможно, это звучало бы так: Для любого непланарного графа H существует положительное число k, такое, что каждый H-свободный граф может быть получен в виде k-кликовой суммы списка графов, каждый из которых либо имеет не более k вершин, либо вкладываем в некоторую поверхность, в которую H вложить нельзя. Данное утверждение слишком просто, чтобы быть правдой. Мы должны позволить каждому вложенному графу G_i "мошенничать" двумя ограниченными способами. Во-первых, мы должны разрешить в ограниченном числе мест на поверхности добавление некоторых новых вершин и рёбер, которым разрешено пересекаться в некоторой ограниченной сложности. Такие места называются вихрями. "Сложность" вихря ограничена параметром, называемым его глубиной, которая тесно связана с путевой шириной графа. Читатель может пропустить чтение точного определения вихря глубины k в следующем разделе. Во-вторых, мы должны позволить добавлять ограниченное число новых вершин для вложенных графов с вихрями.

Вихри (точное определение)

Грань вложенного графа — это открытая 2-ячейка поверхности, не пересекающаяся с графом, но границы которой являются объединением некоторых рёбер вложенного графа. Пусть F — грань вложенного графа G и пусть v₀, v₁, ..., v_n−1,v_n = v₀ — вершины, лежащие на границе F (в порядке цикла). Цикловой интервал для F — это набор вершин вида {v_a, v_a+1, ..., v_a+s}, где a и s — целые числа, и где индекс берётся по модулю n. Пусть Λ — это конечный список цикловых интервалов для F. Построим новый граф следующим образом. Для каждого циклового интервала L из Λ добавляем новую вершину v_L, соединённую с некоторым числом (возможно, нулевым) вершин из L. Для каждой пары {L, M} интервалов в Λ мы можем добавить ребро, соединяющее v_L с v_M, если L и M имеют непустое пересечение. Говорят, что образованный граф получен из графа G добавлением вихря глубины, не превосходящей k (к грани F), если никакая вершина на границе F не появляется в более чем k интервалах из Λ.

Утверждение структурной теоремы графов

Структурная теорема графов. Для любого графа H существует положительное целое k, такое, что любой H-свободный граф может быть получен следующим образом:

1. Начинаем со списка графов, где каждый граф из списка вложен в поверхность, в которую H вложить нельзя
2. к каждому вложенному графу из списка добавляем не более k вихрей и каждый вихрь имеет глубину, не превосходящую k
3. к каждому полученному графу добавляем не более k новых вершин (называемых верхушками и добавляем некоторое число рёбер, которые имеют, по крайней мере, один конец в верхушке.
4. наконец, соединяем с помощью k-кликовых сумм получившийся список графов.

Заметим, что шаги 1 и 2 дают пустые графы, если граф H планарен, но ограниченное число вершин, добавляемых на шаге 3, делает утверждение совместимым со Следствием 1.

Уточнения

Усиленные версии структурной теоремы графов возможны в зависимости от множества H запрещённых миноров. Например, если один из графов в H планарен, то любой H-свободный граф имеет древесную декомпозицию ограниченной ширины. Эквивалентно он может быть представлен как сумма по клике графов постоянного размера. Если один из графов H может быть нарисован в плоскости с одним пересечением, то H-минорно-свободные графы допускают разложение на кликовую сумму графов с постоянным размером и графов с ограниченным родом (не используя вихри)). Известны также различные усиления, если один из графов H является верхушечным графом.

См. также

• Теорема Робертсона – Сеймура

Литература

• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi. Proc. 36th International Colloquium Automata, Languages and Programming (ICALP '09). — Springer-Verlag, 2009. — Т. 5555. — С. 316–327. — (Lecture Notes in Computer Science). — doi:10.1007/978-3-642-02927-1_27..
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos. Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002). — Springer-Verlag, 2002. — Т. 2462. — С. 67–80. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-45753-4_8..
• Ken-ichi Kawarabayashi, Bojan Mohar. Some recent progress and applications in graph minor theory // Graphs and Combinatorics. — 2007. — Т. 23, вып. 1. — С. 1–46. — doi:10.1007/s00373-006-0684-x..
• Lovász. Graph minor theory // Bulletin of the American Mathematical Society. — 2006. — Т. 43, вып. 1. — С. 75–86. — doi:10.1090/S0273-0979-05-01088-8..
• Neil Robertson, P. D. Seymour. Graph minors. I. Excluding a forest // Journal of Combinatorial Theory. — 1983 I. — Т. 35, вып. 1. — С. 39–61. — doi:10.1016/0095-8956(83)90079-5..
• Neil Robertson, P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width // Journal of Algorithms. — 1986 II. — Т. 7, вып. 3. — С. 309–322. — doi:10.1016/0196-6774(86)90023-4..
• Neil Robertson, P. D. Seymour. Graph minors. III. Planar tree-width // Journal of Combinatorial Theory. — 1984 III. — Т. 36, вып. 1. — С. 49–64. — doi:10.1016/0095-8956(84)90013-3..
• Neil Robertson, P. D. Seymour. Graph minors. IV. Tree-width and well-quasi-ordering // Journal of Combinatorial Theory. — 1990 IV. — Т. 48, вып. 2. — С. 227–254. — doi:10.1016/0095-8956(90)90120-O..
• Neil Robertson, P. D. Seymour. Graph minors. V. Excluding a planar graph // Journal of Combinatorial Theory. — 1986 V. — Т. 41, вып. 1. — С. 92–114. — doi:10.1016/0095-8956(86)90030-4..
• Neil Robertson, P. D. Seymour. Graph minors. VI. Disjoint paths across a disc // Journal of Combinatorial Theory. — 1986 VI. — Т. 41, вып. 1. — С. 115–138. — doi:10.1016/0095-8956(86)90031-6..
• Neil Robertson, P. D. Seymour. Graph minors. VII. Disjoint paths on a surface // Journal of Combinatorial Theory. — 1988 VII. — Т. 45, вып. 2. — С. 212–254. — doi:10.1016/0095-8956(88)90070-6..
• Neil Robertson, P. D. Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces // Journal of Combinatorial Theory. — 1990 VIII. — Т. 48, вып. 2. — С. 255–288. — doi:10.1016/0095-8956(90)90121-F..
• Neil Robertson, P. D. Seymour. Graph minors. IX. Disjoint crossed paths // Journal of Combinatorial Theory. — 1990 IX. — Т. 49, вып. 1. — С. 40–77. — doi:10.1016/0095-8956(90)90063-6..
• Neil Robertson, P. D. Seymour. Graph minors. X. Obstructions to tree-decomposition // Journal of Combinatorial Theory. — 1991 X. — Т. 52, вып. 2. — С. 153–190. — doi:10.1016/0095-8956(91)90061-N..
• Neil Robertson, P. D. Seymour. Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors / Neil Robertson, Paul Seymour. — American Mathematical Society, 1993. — Т. 147. — С. 669–675. — (Contemporary Mathematics). — doi:10.1090/conm/147/01206..
• Neil Robertson, P. D. Seymour. Graph minors. XI. Circuits on a surface // Journal of Combinatorial Theory. — 1994 XI. — Т. 60, вып. 1. — С. 72–106. — doi:10.1006/jctb.1994.1007..
• Neil Robertson, P. D. Seymour. Graph minors. XII. Distance on a surface // Journal of Combinatorial Theory. — 1995 XII. — Т. 64, вып. 2. — С. 240–272. — doi:10.1006/jctb.1995.1034..
• Neil Robertson, P. D. Seymour. Graph minors. XIII. The disjoint paths problem // Journal of Combinatorial Theory. — 1995 XIII. — Т. 63, вып. 1. — С. 65–110. — doi:10.1006/jctb.1995.1006..
• Neil Robertson, P. D. Seymour. Graph minors. XIV. Extending an embedding // Journal of Combinatorial Theory. — 1995 XIV. — Т. 65, вып. 1. — С. 23–50. — doi:10.1006/jctb.1995.1042..
• Neil Robertson, P. D. Seymour. Graph minors. XV. Giant steps // Journal of Combinatorial Theory. — 1996 XV. — Т. 68, вып. 1. — С. 112–148. — doi:10.1006/jctb.1996.0059.
• Neil Robertson, P. D. Seymour. Graph minors. XVI. Excluding a non-planar graph // Journal of Combinatorial Theory. — 2003 XVI. — Т. 89, вып. 1. — С. 43–76. — doi:10.1016/S0095-8956(03)00042-X..
• Neil Robertson, P. D. Seymour. Graph minors. XVII. Taming a vortex // Journal of Combinatorial Theory. — 1999 XVII. — Т. 77, вып. 1. — С. 162–210. — doi:10.1006/jctb.1999.1919..
• Neil Robertson, Paul Seymour. Graph minors. XVIII. Tree-decompositions and well-quasi-ordering // Journal of Combinatorial Theory. — 2003 XVII. — Т. 89, вып. 1. — С. 77–108. — doi:10.1016/S0095-8956(03)00067-4..
• Neil Robertson, P. D. Seymour. Graph minors. XIX. Well-quasi-ordering on a surface // Journal of Combinatorial Theory. — 2004 XIX. — Т. 90, вып. 2. — С. 325–385. — doi:10.1016/j.jctb.2003.08.005..
• Neil Robertson, P. D. Seymour. Graph minors. XX. Wagner's conjecture // Journal of Combinatorial Theory. — 2004 XX. — Т. 92, вып. 2. — С. 325–357. — doi:10.1016/j.jctb.2004.08.001..
• Neil Robertson, Paul Seymour. Graph minors. XXI. Graphs with unique linkages // Journal of Combinatorial Theory. — 2009 XXI. — Т. 99, вып. 3. — С. 583–616. — doi:10.1016/j.jctb.2008.08.003..
• Neil Robertson, Paul Seymour. Graph minors. XXII. Irrelevant vertices in linkage problems // Journal of Combinatorial Theory. — 2012 XXII. — Т. 102, вып. 2. — С. 530–563. — doi:10.1016/j.jctb.2007.12.007..
• Neil Robertson, Paul Seymour. Graph minors XXIII. Nash-Williams' immersion conjecture // Journal of Combinatorial Theory. — 2010 XXIII. — Т. 100, вып. 2. — С. 181–205. — doi:10.1016/j.jctb.2009.07.003..
• Klaus Wagner. Über eine Erweiterung des Satzes von Kuratowski // Deutsche Mathematik. — 1937. — Т. 2. — С. 280–285..