В математике теорема о структуре графа является основным результатом в области теории графов . Результат устанавливает глубокую и фундаментальную связь между теорией миноров графа и топологическими вложениями . Теорема сформулирована в семнадцатой из серии из 23 статей Нила Робертсона и Пола Сеймура . Ее доказательство очень длинное и запутанное. Kawarabayashi & Mohar (2007) и Lovász (2006) — обзоры, доступные неспециалистам, описывающие теорему и ее следствия.
Минор графа 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 4 , полный граф на четырех вершинах, для которого k = 3 ). Это одна из причин, по которой теорема о структуре графа, как говорят, описывает «грубую структуру» графов, свободных от H.
Грубо говоря, поверхность — это множество точек с локальной топологической структурой диска. Поверхности делятся на два бесконечных семейства: ориентируемые поверхности включают сферу , тор , двойной тор и так далее; неориентируемые поверхности включают действительную проективную плоскость , бутылку Клейна и так далее. Граф вкладывается в поверхность, если граф можно нарисовать на поверхности как множество точек (вершин) и дуг (ребер), которые не пересекаются и не касаются друг друга, за исключением случаев, когда ребра и вершины инцидентны или смежны. Граф является планарным, если он вкладывается в сферу. Если граф G вкладывается в определенную поверхность, то каждый минор G также вкладывается в эту же поверхность. Следовательно, «веская причина» того, что G не содержит H , заключается в том, что G вкладывается в поверхность, в которую H не вкладывается.
Если H не является планарным, теорему о структуре графа можно рассматривать как обширное обобщение теоремы Куратовского. Версия этой теоремы, доказанная Вагнером (1937), гласит, что если граф G является как K 5 -свободным, так и K 3,3 -свободным, то G является планарным. Эта теорема дает «веское основание» для того, чтобы граф G не имел K 5 или K 3,3 в качестве миноров; в частности, G вкладывается в сферу, тогда как ни K 5 , ни K 3,3 не вкладывают в сферу. К сожалению, это понятие «веского основания» недостаточно сложно для теоремы о структуре графа. Требуются еще два понятия: суммы клик и вихри .
Клика в графе G — это любой набор вершин, которые попарно смежны в G. Для неотрицательного целого числа k k - кликовая сумма двух графов G и K — это любой граф, полученный выбором неотрицательного целого числа m ≤ k , выбором клики размера m в каждой из G и K , объединением двух клик в одну клику размера m и последующим удалением нуля или более ребер, соединяющих вершины в новой клике.
Если G 1 , G 2 , …, G n — список графов, то мы можем создать новый граф, объединив список графов с помощью k -кликовых сумм . То есть, мы берем k -кликовую сумму G 1 и G 2 , затем берем k -кликовую сумму G 3 с полученным графом и т. д. Граф имеет ширину дерева не более k, если его можно получить с помощью k -кликовых сумм из списка графов, где каждый граф в списке имеет не более k + 1 вершины.
Следствие 1 указывает нам, что k -кликовые суммы небольших графов описывают грубую структуру H -свободных графов, когда H является планарным. Когда H не является планарным, нам также необходимо рассмотреть k -кликовые суммы списка графов, каждый из которых вложен в поверхность. Следующий пример с H = K 5 иллюстрирует этот момент. Граф K 5 вкладывается в каждую поверхность, кроме сферы. Однако существуют K 5 -свободные графы, которые далеки от планарных. В частности, 3-кликовая сумма любого списка планарных графов приводит к K 5 -свободному графу. Вагнер (1937) определил точную структуру K 5 -свободных графов как часть кластера результатов, известных как теорема Вагнера :
Теорема 2. Если G является K 5 -свободным, то G может быть получен с помощью 3-кликовых сумм из списка планарных графов и копий одного специального непланарного графа, имеющего 8 вершин.
Мы отмечаем, что теорема 2 является точной структурной теоремой, поскольку определена точная структура графов, свободных от K 5 . Такие результаты редки в теории графов. Теорема о структуре графа не является точной в этом смысле, поскольку для большинства графов H структурное описание графов, свободных от H , включает некоторые графы, которые не являются свободными от H .
Можно было бы предположить, что аналог теоремы 2 справедлив для графов H, отличных от K 5 . Возможно, верно, что: для любого непланарного графа H существует положительное целое число k такое, что каждый H -свободный граф может быть получен с помощью k -кликовых сумм из списка графов, каждый из которых либо имеет не более k вершин, либо встраивается в некоторую поверхность, в которую H не встраивается . К сожалению, это утверждение пока недостаточно сложно, чтобы быть верным. Мы должны позволить каждому вложенному графу G i «обманывать» двумя ограниченными способами. Во-первых, мы должны разрешить ограниченное количество мест на поверхности, в которых мы можем добавлять некоторые новые вершины и ребра, которым разрешено пересекаться друг с другом способом ограниченной сложности . Такие места называются вихрями . «Сложность» вихря ограничена параметром, называемым его глубиной , тесно связанным с шириной пути . Читатель может предпочесть отложить чтение следующего точного описания вихря глубиной k . Во-вторых, мы должны разрешить добавление ограниченного числа новых вершин к каждому из встроенных графов с вихрями.
Грань вложенного графа — это открытая 2-ячейка на поверхности, которая не пересекается с графом, но граница которой является объединением некоторых ребер вложенного графа. Пусть F — грань вложенного графа G , а v 0 , v 1 , ..., v n – 1 , v n = v 0 — вершины, лежащие на границе 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 и 2 приводят к пустому графу, если H является планарным, но ограниченное число вершин, добавленных на шаге 3, делает утверждение совместимым со следствием 1.
Усиленные версии теоремы о структуре графа возможны в зависимости от множества H запрещенных миноров. Например, когда один из графов в H является планарным , то каждый граф, свободный от H -миноров, имеет древесное разложение ограниченной ширины; эквивалентно, его можно представить как кликовую сумму графов постоянного размера. [1] Когда один из графов в H можно нарисовать на плоскости только с одним пересечением , то графы, свободные от H -миноров, допускают разложение как кликовую сумму графов постоянного размера и графов ограниченного рода без вихрей. [2] Известно также другое усиление, когда один из графов в H является графом вершины . [3]