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

Древесная ширина графа 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 не планарен, структурная теорема графов может рассматриваться как сильное обобщение теоремы Понтрягина — Куратовского. Версия этой теоремы, доказанная Вагнером[3], утверждает, что если граф 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₅-свободный граф. Вагнер[3] определил точную структур 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 интервалах из Λ.