Войти
В математике теорема о структуре графа является основным результатом в этой области теории графов. Результат устанавливает глубокую и фундаментальную связь между теорией миноров графов и топологических вложений. Эта теорема сформулирована в семнадцатой из 23 статей Нила Робертсона и Пола Сеймура. Его доказательство очень длинное и сложное. Каварабаяси и Мохар (2007) и Ловас (2006) - это доступные для неспециалистов обзоры, описывающие теорему и ее следствия.
A второстепенное Граф 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 не вкладываются в сферу. К сожалению, это понятие «веская причина» недостаточно сложно для теоремы о структуре графа. Требуются еще два понятия: клик-суммы и вихри.
A клика в графе 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. Во-вторых, мы должны позволить ограниченному числу новых вершин добавляться к каждому из вложенных графов с вихрями.
A грань вложенного графа - это открытая 2-ячейка на поверхности, которая не пересекается с графом, но граница которой является объединением некоторых ребер графа. встроенный граф. Пусть F - грань вложенного графа G, и пусть v 0, v 1,..., v n − 1,vn= 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-минорных элементов имеет разложение дерева ограниченной ширины; эквивалентно, это может быть представлено как клик-сумма графиков постоянного размера. Когда один из графиков в H может быть нарисован в плоскости только с одним , пересекающим, тогда H -безминорные графы допускают разложение как клик-сумму графов постоянного размера и графов ограниченного рода без вихрей. Другое усиление также известно, когда один из графов в H является вершинным графом.
