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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

Минор графа 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 = K4, то есть H равен полному графу из четырёх вершин, для которого k=3). Это одна из причин, по которой говорят, что структурная теорема описывает "грубую структуру " H-свободных графов.

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

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

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

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

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

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

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

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

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

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

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

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

Грань вложенного графа — это открытая 2-ячейка поверхности, не пересекающаяся с графом, но границы которой являются объединением некоторых рёбер вложенного графа. Пусть F — грань вложенного графа G и пусть v0, v1, ..., vn−1,vn = v0 — вершины, лежащие на границе F (в порядке цикла). Цикловой интервал для F — это набор вершин вида {va, va+1, ..., va+s}, где a и s — целые числа, и где индекс берётся по модулю n. Пусть Λ — это конечный список цикловых интервалов для F. Построим новый граф следующим образом. Для каждого циклового интервала L из Λ добавляем новую вершину vL, соединённую с некоторым числом (возможно, нулевым) вершин из L. Для каждой пары {L, M} интервалов в Λ мы можем добавить ребро, соединяющее vL с vM, если 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-свободный граф имеет древесную декомпозицию ограниченной ширины. Эквивалентно он может быть представлен как сумма по клике графов постоянного размера[4]. Если один из графов H может быть нарисован в плоскости с одним пересечением, то H-минорно-свободные графы допускают разложение на кликовую сумму графов с постоянным размером и графов с ограниченным родом (не используя вихри)[5][6]). Известны также различные усиления, если один из графов H является верхушечным графом[7].

См. также

Примечания

  1. ↑ Kawarabayashi, Mohar, 2007.
  2. ↑ Lovász, 2006.
  3. ↑ 3,0 3,1 Wagner, 1937.
  4. ↑ Robertson, Seymour, 1986 V.
  5. ↑ Robertson, Seymour, 1993.
  6. ↑ Demaine, Hajiaghayi, Thilikos, 2002.
  7. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2009.

Литература

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Структурная_теорема_графов&oldid=13354287