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

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

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

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

Значение ${\displaystyle k}$ в следствии 1, как правило, много больше древесной ширины ${\displaystyle H}$ (имеется замечательное исключение, когда ${\displaystyle H=K_{4}}$, то есть ${\displaystyle H}$ равен полному графу из четырёх вершин, для которого ${\displaystyle k=3}$). Это одна из причин, по которой говорят, что структурная теорема описывает «грубую структуру» ${\displaystyle H}$-свободных графов.

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

Если ${\displaystyle H}$ не планарен, структурная теорема графов может рассматриваться как сильное обобщение теоремы Понтрягина — Куратовского. Версия этой теоремы, доказанная Вагнером^[3], утверждает, что если граф ${\displaystyle G}$ является как ${\displaystyle K_{5}}$-свободным, так и ${\displaystyle K_{3,3}}$-свободным, то ${\displaystyle G}$ планарен. Эта теорема даёт "хорошую причину" для графа ${\displaystyle G}$ не содержать ${\displaystyle K_{5}}$ или ${\displaystyle K_{3,3}}$ в качестве миноров. Конкретнее, ${\displaystyle G}$ вкладывается в сферу, в то время как ни ${\displaystyle K_{5}}$, ни ${\displaystyle K_{3,3}}$ в сферу вложить нельзя. Понятия "хорошая причина" недостаточно для структурной теоремы графов. Требуются ещё два понятия — суммы по клике и вихри.

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

Если ${\displaystyle G_{1}}$, ${\displaystyle G_{2}}$, ..., ${\displaystyle G_{n}}$ — список графов, можно получить новый граф путём объединения графов из списка с помощью сумм по ${\displaystyle k}$-кликам. То есть создаём ${\displaystyle k}$-кликовую сумму графа ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$, затем создаём ${\displaystyle k}$-кликовую сумму графа ${\displaystyle G_{3}}$ с предыдущим результирующим графом, и т.д. Граф имеет древесную ширину, не превосходящую ${\displaystyle k}$, если он может быть получен как ${\displaystyle k}$-кликовая сумма некоторого списка графов, в котором каждый граф имеет максимум ${\displaystyle k+1}$ вершин.

Следствие 1 показывает нам, что ${\displaystyle k}$-кликовые суммы малых графов описывают грубую структуру ${\displaystyle H}$-свободных графов в случае планарности ${\displaystyle H}$. Если ${\displaystyle H}$ непланарен, мы вынуждены рассматривать также ${\displaystyle k}$-кликовые суммы графов, каждый из которых вложим в поверхность. Следующий пример с ${\displaystyle H=K_{5}}$ иллюстрирует этот момент. Граф ${\displaystyle K_{5}}$ можно вложить в любую поверхность, за исключением сферы. Однако существуют ${\displaystyle K_{5}}$-свободные графы, которые далеко не планарны. В частности, 3-кликовая сумма любого списка планарных графов даёт ${\displaystyle K_{5}}$-свободный граф. Вагнер^[3] определил точную структуру ${\displaystyle K_{5}}$-свободных графов как часть группы результатов, известных под названием теорема Вагнера:

Теорема 2. Если ${\displaystyle G}$ свободен от ${\displaystyle K_{5}}$, то ${\displaystyle G}$ можно получить как 3-кликовые суммы списка планарных графов и копий некоторого специфичного непланарного графа с 8 вершинами.

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

Стиль этого раздела неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии.

Имеется искушение предположить, что выполняется аналог теоремы 2 для графов ${\displaystyle H}$, отличных от ${\displaystyle K_{5}}$. Возможно, это звучало бы так: "Для любого непланарного графа ${\displaystyle H}$ существует положительное число ${\displaystyle k}$, такое, что каждый ${\displaystyle H}$-свободный граф может быть получен в виде ${\displaystyle k}$-кликовой суммы списка графов, каждый из которых либо имеет не более ${\displaystyle k}$ вершин, либо вкладываем в некоторую поверхность, в которую ${\displaystyle H}$ вложить нельзя". Данное утверждение слишком просто, чтобы быть правдой. Мы должны позволить каждому вложенному графу ${\displaystyle G_{i}}$ "мошенничать" двумя ограниченными способами. Во-первых, мы должны разрешить в ограниченном числе мест на поверхности добавление некоторых новых вершин и рёбер, которым разрешено пересекаться в некоторой ограниченной сложности. Такие места называются вихрями. "Сложность" вихря ограничена параметром, называемым его глубиной, которая тесно связана с путевой шириной графа. Читатель может пропустить чтение точного определения вихря глубины ${\displaystyle k}$ в следующем разделе. Во-вторых, мы должны позволить добавлять ограниченное число новых вершин для вложенных графов с вихрями.

Грань вложенного графа — это открытая 2-ячейка поверхности, не пересекающаяся с графом, но границы которой являются объединением некоторых рёбер вложенного графа. Пусть ${\displaystyle F}$ — грань вложенного графа ${\displaystyle G}$ и пусть ${\displaystyle v_{0},v_{1},...,v_{n-1},v_{n}=v_{0}}$ — вершины, лежащие на границе ${\displaystyle F}$ (в порядке цикла). Цикловой интервал для ${\displaystyle F}$ — это набор вершин вида ${\displaystyle \{v_{a},v_{a+1},...,v_{a+s}\}}$, где ${\displaystyle a}$ и ${\displaystyle s}$ — целые числа, и где индекс берётся по модулю ${\displaystyle n}$. Пусть ${\displaystyle \Lambda }$ — это конечный список цикловых интервалов для ${\displaystyle F}$. Построим новый граф следующим образом. Для каждого циклового интервала ${\displaystyle L}$ из ${\displaystyle \Lambda }$ добавляем новую вершину ${\displaystyle v_{L}}$, соединённую с некоторым числом (возможно, нулевым) вершин из ${\displaystyle L}$. Для каждой пары ${\displaystyle \{L,M\}}$ интервалов в ${\displaystyle \Lambda }$ мы можем добавить ребро, соединяющее ${\displaystyle v_{L}}$ с ${\displaystyle v_{M}}$, если ${\displaystyle L}$ и ${\displaystyle M}$ имеют непустое пересечение. Говорят, что образованный граф получен из графа ${\displaystyle G}$ добавлением вихря глубины, не превосходящей ${\displaystyle k}$ (к грани ${\displaystyle F}$), если никакая вершина на границе ${\displaystyle F}$ не появляется в более чем ${\displaystyle k}$ интервалах из ${\displaystyle \Lambda }$.

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

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

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

Усиленные версии структурной теоремы графов возможны в зависимости от множества ${\displaystyle H}$ запрещённых миноров. Например, если один из графов в ${\displaystyle H}$ планарен, то любой ${\displaystyle H}$-свободный граф имеет древесную декомпозицию ограниченной ширины. Эквивалентно он может быть представлен как сумма по клике графов постоянного размера^[4]. Если один из графов ${\displaystyle H}$ может быть нарисован в плоскости с одним пересечением, то ${\displaystyle H}$-минорно-свободные графы допускают разложение на кликовую сумму графов с постоянным размером и графов с ограниченным родом (не используя вихри)^[5][6]). Известны также различные усиления, если один из графов ${\displaystyle H}$ является верхушечным графом^[7].

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

• 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..

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