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

В математике , то теорема графа структуры является основным результатом в области теории графов . Результат устанавливает глубокую и фундаментальную связь между теорией миноров графов и топологическими вложениями . Теорема сформулирована в семнадцатой из 23 статей Нила Робертсона и Пола Сеймура . Его доказательство очень длинное и сложное. Каварабаяши и Мохар (2007) и Ловас (2006) - это обзоры, доступные неспециалистам, в которых описывается теорема и ее следствия.

Основание и мотивация теоремы [ править ]

Минор графа G является любым графом Н , изоморфная графы , который может быть получен из подграфа G от заражения некоторых ребер. Если G имеет не имеет граф H , как несовершеннолетние, то мы говорим , что G является H -бесплатно . Пусть H - фиксированный граф. Интуитивно понятно, что если G - огромный граф, свободный от H , то для этого должна быть «веская причина». Структура графа теорема дает такую «хорошую причину» в виде грубого описания структуры G . По сути, каждый Н -бесплатно граф 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 _5, ни K _3,3встроить в сферу. К сожалению, это понятие «веская причина» недостаточно сложно для теоремы о структуре графа. Требуются еще два понятия: клик-суммы и вихри .

Клики-суммы [ править ]

Кликой в графе G любое множество вершин, попарно смежны в G . Для неотрицательного числа к , в K -clique суммы два графов G и K является любым графиком , полученный путем выбора неотрицательного целого числа м  ≤  K , выбирая клику размера м в каждом из G и K , идентификация два клики в одну клику размера 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 ₅ -свободному графу.Вагнер (1937) определил точную структуру K ₅ -свободных графов как часть группы результатов, известной как теорема Вагнера :

Теорема 2. Если G является К ₅ -бесплатно, то 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 , v _{+ 1} , ...,v _{a + s} }, где a и s - целые числа, а индексы уменьшены по модулю  n . Пусть Λ конечный список круговых интервалов для F . Строим новый граф следующим образом. Для каждого кругового интервала L в Л мы добавим новую вершину v _L , который соединяет к нулю или более вершин L . Наконец, для каждой пары { L ,  M } интервалов в Λ мы можем добавить ребро, соединяющее v _L с v _M, при условии, что L и Mимеют непустое пересечение. Полученный граф называется быть получено из G путем добавления вихря глубины не более к (к лицу  F ) при условии , что ни одна из вершин на границе F не появятся больше , чем к интервалам в Л.

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

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

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

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

Уточнения [ править ]

Возможны усиленные версии теоремы о структуре графа в зависимости от множества H запрещенных миноров. Например, если один из графов в H является плоским , то каждый граф без H- миноров имеет древовидное разложение ограниченной ширины; эквивалентно, это может быть представлено как клик-сумма графов постоянного размера. ^[1] Когда один из графов в H может быть нарисован на плоскости только с одним пересечением , тогда графы без H- миноров допускают разложение в виде клик-суммы графов постоянного размера и графов ограниченного рода без вихри. ^[2]Другое усиление также известно, когда один из графов в H является вершинным графом . ^[3]

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги; Каварабаяси, Кен-ичи (2009), "Алгоритмы приближения через структурные результаты для графов без апекс-минор", Proc. 36-й Международный коллоквиум «Автоматы, языки и программирование» (ICALP '09) (PDF) , Lecture Notes in Computer Science, 5555 , Springer-Verlag, pp. 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), "Некоторые недавние достижения и приложения в теории второстепенных графов", Графы и комбинаторика , 23 (1): 1–46, DOI : 10.1007 / s00373-006-0684-x , MR  2292102.
• Lovász, Ласло (2006), "Теория графов минор", Бюллетень Американского математического общества , 43 (1): 75-86, DOI : 10,1090 / S0273-0979-05-01088-8 , MR  2188176 CS1 maint: обескураженный параметр ( ссылка ).
• Робертсон, Нил ; Seymour, PD (1983), "Graph несовершеннолетних 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.
• Робертсон, Нил ; Seymour, PD (1990), "Graph несовершеннолетние И.В. Дерево ширины и хорошо квази-упорядочение..", Журнал комбинаторной теории , Series B, 48 (2): 227-254, DOI : 10.1016 / 0095-8956 (90 ) 90120-О , MR  1046757.
• Робертсон, Нил ; Seymour, PD (1986), "Graph несовершеннолетние В. За исключением плоский граф.", Журнал комбинаторной теории , Series B, 41 (1): 92-114, DOI : 10,1016 / 0095-8956 (86) 90030-4 , Руководство по ремонту  0854606.
• Робертсон, Нил ; Seymour, PD (1986), "Graph несовершеннолетних В.И. дорожки дизъюнктных через диск..", Журнал комбинаторной теории , Series B, 41 (1): 115-138, DOI : 10,1016 / 0095-8956 (86) 90031-6 , Руководство по ремонту  0854607.
• Робертсон, Нил ; Seymour, PD (1988), "Graph несовершеннолетние VII непересекающиеся пути на поверхность..", Журнал комбинаторной теории , Series B, 45 (2): 212-254, DOI : 10,1016 / 0095-8956 (88) 90070-6 , Руководство по ремонту  0961150.
• Робертсон, Нил ; Seymour, PD (1990), "Graph несовершеннолетних VIII , теорема Куратовской для общих поверхностей..", Журнал комбинаторной теории , Series B, 48 (2): 255-288, DOI : 10,1016 / 0095-8956 (90) 90121- F , Руководство по ремонту  1046758.
• Робертсон, Нил ; Сеймур, PD (1990), «Миноры графа. IX. Непересекающиеся пересекающиеся пути», Журнал комбинаторной теории , серия B, 49 (1): 40–77, DOI : 10.1016 / 0095-8956 (90) 90063-6 , MR  1056819.
• Робертсон, Нил ; Seymour, PD (1991), "Graph несовершеннолетнего X. Препятствие к дереву-разложению.", Журнал комбинаторной теории , Series 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.
• Робертсон, Нил ; Seymour, PD (1994), "Graph несовершеннолетние XI схемы на поверхности..", Журнал комбинаторной теории , Series B, 60 (1): 72-106, DOI : 10,1006 / jctb.1994.1007 , МР  1256585.
• Робертсон, Нил ; Seymour, PD (1995), "Graph несовершеннолетние XII Расстояние от поверхности.." Журнал комбинаторной теории , Series B, 64 (2): 240-272, DOI : 10,1006 / jctb.1995.1034 , MR  1339851.
• Робертсон, Нил ; Seymour, PD (1995), "Graph несовершеннолетних XIII дизъюнктного путем проблема..", Журнал комбинаторной теории , Series B, 63 (1): 65-110, DOI : 10,1006 / jctb.1995.1006 , МР  1309358.
• Робертсон, Нил ; Seymour, PD (1995), "Graph несовершеннолетнего XIV Продление вложения..", Журнал комбинаторной теории , Series B, 65 (1): 23-50, DOI : 10,1006 / jctb.1995.1042 , МР  1347339.
• Робертсон, Нил ; Seymour, PD (1996), "Graph несовершеннолетние XV Гигантские шаги..", Журнал комбинаторной теории , Series B, 68 (1): 112-148, DOI : 10,1006 / jctb.1996.0059 , МР  1405708
• Робертсон, Нил ; Seymour, PD (2003), "Graph несовершеннолетний XVI Исключение непланарного графа..", Журнал комбинаторной теории , серии B, 89 (1): 43-76, DOI : 10.1016 / S0095-8956 (03) 00042- Х , МР  1999736.
• Робертсон, Нил ; Seymour, PD (1999), "Graph несовершеннолетних XVII Укрощение вихря..", Журнал комбинаторной теории , Series B, 77 (1): 162-210, DOI : 10,1006 / jctb.1999.1919 , МР  1710538.
• Робертсон, Нил ; Сеймур, Пол (2003), «Миноры графа. XVIII. Древовидные разложения и хорошее квазиупорядочение», Журнал комбинаторной теории , серия B, 89 (1): 77–108, DOI : 10.1016 / S0095-8956 (03 ) 00067-4 , Руководство по эксплуатации  1999737.
• Робертсон, Нил ; Seymour, PD ". Graph миноры XIX Хорошо квази-упорядочение на поверхности" (2004),, Журнал комбинаторной теории , серии B, 90 (2): 325-385, DOI : 10.1016 / j.jctb.2003.08. 005 , Руководство MR  2034033.
• Робертсон, Нил ; Seymour, PD (2004), "Graph миноры XX гипотеза Вагнера..", Журнал комбинаторной теории , серии B, 92 (2): 325-357, DOI : 10.1016 / j.jctb.2004.08.001 , MR  2099147.
• Робертсон, Нил ; Seymour, Павел (2009), "Graph миноры XXI Графы с уникальными связями..", Журнал комбинаторной теории , серии B, 99 (3): 583-616, DOI : 10.1016 / j.jctb.2008.08.003 , MR  2507943.
• Робертсон, Нил ; Seymour, Paul (2012), "Graph миноры XXII Ненужные вершины проблем сцепления..", Журнал комбинаторной теории , серии B, 102 (2): 530-563, DOI : 10.1016 / j.jctb.2007.12.007 , MR  2885434.
• Робертсон, Нил ; Seymour, Пол (2010) "Graph миноры XXIII Нэш-Вильямса погружной гипотеза", Журнал комбинаторной теории , серии B, 100 (2): 181-205, DOI : 10.1016 / j.jctb.2009.07.003 , MR  2595703.
• Вагнер, Клаус (1937), "Uber eine Erweiterung des Satzes von Kuratowski", Deutsche Mathematik , 2 : 280–285.