Теорема о структуре графа

В математике теорема о структуре графа является важным результатом в области теории графов . Результат устанавливает глубокую и фундаментальную связь между теорией миноров графов и топологическими вложениями . Теорема сформулирована в семнадцатой из серии из 23 статей Нила Робертсона и Пола Сеймура . Его доказательство очень длинное и сложное. Kawarabayashi & Mohar (2007) и Lovász (2006) представляют собой обзоры, доступные для неспециалистов, описывающие теорему и ее следствия.

Постановка и мотивация теоремы

Минор — это графа G любой граф H изоморфный графу, который можно получить из подграфа G стягиванием , некоторых ребер. Если G не имеет графа H в качестве минора, то мы говорим, что H G - свободна . Пусть 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 ₄ , полный граф на четырех вершинах, для которого k = 3 ). Это одна из причин, по которой говорят, что теорема о структуре графа описывает «грубую структуру» H -свободных графов.

Поверхностные вложения

Грубо говоря, поверхность — это набор точек с локальной топологической структурой диска. Поверхности делятся на два бесконечных семейства: к ориентируемым поверхностям относятся сфера , тор , двойной тор и т. д.; поверхностям к неориентируемым относятся действительная проективная плоскость , бутылка Клейна и т. д. Граф встраивается в поверхность, если граф можно нарисовать на поверхности как набор точек (вершин) и дуг (ребер), которые не пересекаются и не касаются друг друга, за исключением тех случаев, когда ребра и вершины инцидентны или смежны. Граф является плоским, если он вложен в сферу. Если граф G вкладывается в определенную поверхность, то каждый минор графа G также вкладывается в эту же поверхность. Следовательно, «веская причина» для того, чтобы G был H -свободным, состоит в том, что G встраивается в поверхность, в которую H не вкладывается.

Когда H не планарна, теорему о структуре графа можно рассматривать как обширное обобщение теоремы Куратовского. Версия этой теоремы, доказанная Вагнером (1937), утверждает, что если граф G одновременно K ₅ -свободен и K _3,3 -свободен, то G планарен. Эта теорема дает «вескую причину» для того, чтобы в графе G не было K ₅ или K _3,3 в качестве миноров; в частности, G вкладывается в сферу, тогда как ни K ₅ , ни K _3,3 не вкладываются в сферу. К сожалению, это понятие «веской причины» недостаточно сложно для теоремы о структуре графа. Требуются еще два понятия: клик-суммы и вихри .

Клика-суммы

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

Если G ₁ , G ₂ , …, G _n — список графов, то мы можем создать новый граф, объединив список графов с помощью k -clique-sums . То есть мы берем k сумму G1 _k и G2 _{клику -} , затем берем - сумму G3 _{-клику -} с полученным графом и так далее. Граф имеет ширину дерева не более k, если его можно получить с помощью k -кликовых сумм из списка графов, где каждый граф в списке имеет не более k + 1 вершин.

Следствие 1 указывает нам, что k -кликовые суммы малых графов описывают грубую структуру H -свободных графов, когда H планарен. Когда H непланарно, нам также необходимо рассмотреть k -кликовые суммы списка графов, каждый из которых вложен в поверхность. Следующий пример с H = K ₅ иллюстрирует это. Граф К ₅ вкладывается во все поверхности, кроме сферы. Однако существуют K ₅ -свободные графы, которые далеки от планарности. В частности, сумма 3-клик любого списка плоских графов приводит к графу, свободному от K ₅ . Вагнер (1937) определил точную структуру графов, свободных от 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 интервалов в Λ .

Формулировка теоремы о структуре графа

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

1. Начнем со списка графов, где каждый граф в списке вложен в поверхность, в которую H не вкладывается.
2. к каждому встроенному графу в списке мы добавляем не более k вихрей, где каждый вихрь имеет глубину не более k
3. к каждому полученному графу мы добавляем не более k новых вершин (называемых вершинами ) и добавляем любое количество ребер, каждое из которых имеет хотя бы одну конечную точку среди вершин.
4. наконец, мы объединяем с помощью k -clique-sums. полученный список графов

Обратите внимание, что шаги 1 и 2 приводят к пустому графу, если H планарно, но ограниченное число вершин, добавленное на шаге 3, делает утверждение совместимым со следствием 1.

Уточнения

Усиленные версии теоремы о структуре графа возможны в зависимости от множества H запрещенных миноров. Например, когда один из графов в H планарен , то каждый H граф без миноров имеет древесное разложение ограниченной ширины; эквивалентно, его можно представить как клик-сумму графов постоянного размера. Когда один из графов в H можно нарисовать на плоскости только с одним пересечением , то графы без миноров H допускают разложение в виде клик-суммы графов постоянного размера и графов ограниченного рода без вихрей. Известно также другое усиление, когда один из графов в H является вершинным графом .

См. также

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

Ссылки

• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Каварабаяши, Кен-ичи (2009), «Алгоритмы аппроксимации с помощью структурных результатов для графов без вершинных миноров», Proc. 36-й Международный коллоквиум «Автоматы, языки и программирование» (ICALP '09) (PDF) , Конспекты лекций по информатике, том. 5555, Springer-Verlag, стр. 316–327, doi : 10.1007/978-3-642-02927-1_27 , MR   2544855 .
• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2002), «1,5-аппроксимация древовидной ширины графов, исключая граф с одним второстепенным пересечением», Proc. 5-й международный семинар по аппроксимационным алгоритмам для комбинаторной оптимизации (APPROX 2002) , Конспекты лекций по информатике, том. 2462, Springer-Verlag, стр. 67–80, doi : 10.1007/3-540-45753-4_8 , hdl : 2117/97497 , MR   2091577 .
• Каварабаяси, Кеничи ; Мохар, Боян (2007), «Некоторые недавние достижения и приложения в теории минорных графов», Graphs and Combinatorics , 23 (1): 1–46, doi : 10.1007/s00373-006-0684-x , MR   2292102 , S2CID   7237484 .
• Ловас, Ласло (2006), «Теория граф-миноров», Бюллетень Американского математического общества , 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8 , MR   2188176 .
• Робертсон, Нил ; Сеймур, П.Д. (1983), «Минорные графы. I. Исключение леса», Журнал комбинаторной теории , серия B, 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5 , MR   0723569 .
• Робертсон, Нил ; Сеймур, П.Д. (1986), «Минорные графы. II. Алгоритмические аспекты ширины дерева», Журнал алгоритмов , 7 (3): 309–322, doi : 10.1016/0196-6774(86)90023-4 , MR   0855559 .
• Робертсон, Нил ; Сеймур, П.Д. (1984), «Минорные графы. III. Ширина плоского дерева», Журнал комбинаторной теории , серия B, 36 (1): 49–64, doi : 10.1016/0095-8956(84)90013-3 , МР   0742386 .
• Робертсон, Нил ; Сеймур, П. Д. (1990), «Минорные графы. IV. Ширина дерева и хороший квазиупорядочение», Журнал комбинаторной теории , серия B, 48 (2): 227–254, doi : 10.1016/0095-8956 (90 )90120-О , МР   1046757 .
• Робертсон, Нил ; Сеймур, П.Д. (1986), «Минорные графы. V. Исключение плоского графа», Журнал комбинаторной теории , серия B, 41 (1): 92–114, doi : 10.1016/0095-8956(86)90030-4 , МР   0854606 .
• Робертсон, Нил ; Сеймур, П.Д. (1986), «Минорные графы. VI. Непересекающиеся пути по диску», Журнал комбинаторной теории , серия B, 41 (1): 115–138, doi : 10.1016/0095-8956(86)90031-6 , МР   0854607 .
• Робертсон, Нил ; Сеймур, П.Д. (1988), «Минорные графы. VII. Непересекающиеся пути на поверхности», Журнал комбинаторной теории , серия B, 45 (2): 212–254, doi : 10.1016/0095-8956(88)90070-6 , МР   0961150 .
• Робертсон, Нил ; Сеймур, П.Д. (1990), «Минорные графы. VIII. Теорема Куратовского для общих поверхностей», Журнал комбинаторной теории , серия B, 48 (2): 255–288, doi : 10.1016/0095-8956(90)90121- Ф , МР   1046758 .
• Робертсон, Нил ; Сеймур, PD (1990), «Минорные графы. IX. Непересекающиеся пересекающиеся пути», Журнал комбинаторной теории , серия B, 49 (1): 40–77, doi : 10.1016/0095-8956(90)90063-6 , MR   1056819 .
• Робертсон, Нил ; Сеймур, П.Д. (1991), «Минорные графы. X. Препятствия к разложению дерева», Журнал комбинаторной теории , серия B, 52 (2): 153–190, doi : 10.1016/0095-8956(91)90061-N , МР   1110468 .
• Робертсон, Нил ; Сеймур, П.Д. (1993), «Исключение графа с одним пересечением», Робертсон, Нил; Сеймур, Пол (ред.), Теория структуры графов: Proc. Совместная летняя исследовательская конференция AMS – IMS – SIAM по минорным графам , Современная математика, том. 147, Американское математическое общество, стр. 669–675, doi : 10.1090/conm/147/01206 , MR   1224738 .
• Робертсон, Нил ; Сеймур, П.Д. (1994), «Минорные графы. XI. Цепи на поверхности», Журнал комбинаторной теории , серия B, 60 (1): 72–106, doi : 10.1006/jctb.1994.1007 , MR   1256585 .
• Робертсон, Нил ; Сеймур, П.Д. (1995), «Минорные графы. XII. Расстояние на поверхности», Журнал комбинаторной теории , серия B, 64 (2): 240–272, doi : 10.1006/jctb.1995.1034 , MR   1339851 .
• Робертсон, Нил ; Сеймур, П.Д. (1995), «Минорные графы. XIII. Проблема непересекающихся путей», Журнал комбинаторной теории , серия B, 63 (1): 65–110, doi : 10.1006/jctb.1995.1006 , MR   1309358 .
• Робертсон, Нил ; Сеймур, П.Д. (1995), «Минорные графы. XIV. Расширение вложения», Журнал комбинаторной теории , серия B, 65 (1): 23–50, doi : 10.1006/jctb.1995.1042 , MR   1347339 .
• Робертсон, Нил ; Сеймур, П. Д. (1996), «Минорные графы. XV. Гигантские шаги», Журнал комбинаторной теории , серия B, 68 (1): 112–148, doi : 10.1006/jctb.1996.0059 , MR   1405708
• Робертсон, Нил ; Сеймур, П.Д. (2003), «Минорные графы. XVI. Исключение непланарного графа», Журнал комбинаторной теории , серия B, 89 (1): 43–76, doi : 10.1016/S0095-8956(03)00042- Х , МР   1999736 .
• Робертсон, Нил ; Сеймур, П.Д. (1999), «Минорные графы. XVII. Укрощение вихря», Журнал комбинаторной теории , серия B, 77 (1): 162–210, doi : 10.1006/jctb.1999.1919 , MR   1710538 .
• Робертсон, Нил ; Сеймур, Пол (2003), «Минорные графы. XVIII. Древовидные разложения и хороший квазиупорядочение», Журнал комбинаторной теории , серия B, 89 (1): 77–108, doi : 10.1016/S0095-8956(03 )00067-4 , МР   1999737 .
• Робертсон, Нил ; Сеймур, П.Д. (2004), «Минорные графы. XIX. Хороший квазиупорядочение на поверхности», Журнал комбинаторной теории , серия B, 90 (2): 325–385, doi : 10.1016/j.jctb.2003.08. 005 , МР   2034033 .
• Робертсон, Нил ; Сеймур, П.Д. (2004), «Минорные графы. XX. Гипотеза Вагнера», Журнал комбинаторной теории , серия B, 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001 , MR   2099147 .
• Робертсон, Нил ; Сеймур, Пол (2009), «Минорные графы. XXI. Графы с уникальными связями», Журнал комбинаторной теории , серия B, 99 (3): 583–616, doi : 10.1016/j.jctb.2008.08.003 , MR   2507943 .
• Робертсон, Нил ; Сеймур, Пол (2012), «Минорные графы. XXII. Нерелевантные вершины в задачах сцепления» (PDF) , Журнал комбинаторной теории , серия B, 102 (2): 530–563, doi : 10.1016/j.jctb.2007.12. 007 , МР   2885434 .
• Робертсон, Нил ; Сеймур, Пол (2010), «Минорные графы XXIII. Гипотеза погружения Нэша-Вильямса», Журнал комбинаторной теории , серия B, 100 (2): 181–205, doi : 10.1016/j.jctb.2009.07.003 , MR   2595703 .
• Вагнер, Клаус (1937), «О расширении теоремы Куратовского», German Mathematics , 2 : 280–285 .