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

В теории графов теорема Робертсона -Сеймура (также называемая малой теоремой о графах) ) утверждает, что неориентированные графы , частично упорядоченные , минорными отношениями графов образуют хорошо квазиупорядоченный . Эквивалентно, каждое семейство графов, замкнутое относительно миноров, может быть определено конечным набором запрещенных миноров , точно так же, как теорема Вагнера характеризует плоские графы как графы, которые не имеют полного графа K ₅ или полного двудольного графа. граф К _3,3 как миноры.

Теорема Робертсона-Сеймура названа в честь математиков Нила Робертсона и Пола Д. Сеймура , которые доказали ее в серии из двадцати статей объемом более 500 страниц с 1983 по 2004 год. До доказательства утверждение теоремы было известно как гипотеза Вагнера в честь немецкого математика Клауса Вагнера , хотя Вагнер сказал, что никогда не выдвигал эту гипотезу.

Более слабый результат для деревьев следует из теоремы Крускала о дереве , которая была выдвинута в 1937 году Эндрю Вассони и доказана в 1960 году независимо Джозефом Крускалом и С. Тарковски.

Заявление

Минором G неориентированного графа G является любой граф, который может быть получен из G последовательностью нуля или более стягиваний ребер и удаления ребер и вершин G . Минорное отношение образует частичный порядок на множестве всех различных конечных неориентированных графов, поскольку оно подчиняется трем аксиомам частичного порядка: оно рефлексивно (каждый граф является минором самого себя), транзитивно (минор минора графа G есть сам является минором G ) и антисимметричен (если два графа G и H являются минорами друг друга, то они должны быть изоморфны ). Однако, если изоморфные графы, тем не менее, можно рассматривать как отдельные объекты, тогда меньший порядок на графах образует предварительный порядок — отношение, которое является рефлексивным и транзитивным, но не обязательно антисимметричным.

Говорят, что предпорядок образует хороший квазиупорядочение , если он не содержит ни бесконечной нисходящей цепи , ни бесконечной антицепи . Например, обычный порядок неотрицательных целых чисел является хорошим квазиупорядочением, но тот же порядок на множестве всех целых чисел таковым не является, поскольку он содержит бесконечную нисходящую цепочку 0, −1, −2, −3. ... Другой пример - набор положительных целых чисел, упорядоченный по делимости , который не имеет бесконечных нисходящих цепей, но где простые числа составляют бесконечную антицепь.

Теорема Робертсона-Сеймура утверждает, что конечные неориентированные графы и миноры графа образуют хороший квазиупорядочение. Второстепенная связь графа не содержит бесконечной нисходящей цепи, поскольку каждое сокращение или удаление уменьшает количество ребер и вершин графа (неотрицательное целое число). Нетривиальная часть теоремы состоит в том, что не существует бесконечных антицепей, бесконечных наборов графов, не связанных друг с другом минорным порядком. Если S — набор графов, а M — подмножество S, содержащее один репрезентативный граф для каждого класса эквивалентности минимальных элементов (графы, которые принадлежат S, но для которых ни один собственный минор не принадлежит S ), то M образует антицепь; следовательно, эквивалентный способ формулировки теоремы состоит в том, что в любом бесконечном множестве S графов должно быть только конечное число неизоморфных минимальных элементов.

Другая эквивалентная форма теоремы состоит в том, что в любом бесконечном множестве S графов должна существовать пара графов, один из которых является минорным по отношению к другому. Из утверждения о том, что каждое бесконечное множество имеет конечное число минимальных элементов, следует такая форма теоремы, ибо если минимальных элементов только конечное число, то каждый из оставшихся графов должен принадлежать паре этого типа с одним из минимальных элементов. А в другую сторону эта форма теоремы подразумевает утверждение, что бесконечных антицепей быть не может, поскольку бесконечная антицепь — это множество, не содержащее ни одной пары, связанной минорным отношением.

Запрещенные второстепенные характеристики

Основная статья: Характеристика запрещенного графа

Семейство графов F называется замкнутым относительно операции взятия миноров, если каждый минор графа из F также принадлежит F . Если F — минорно-замкнутое семейство, то пусть S — класс графов, не входящих в F ( дополнение к F ). Согласно теореме Робертсона–Сеймура, существует конечное множество H минимальных элементов в S . Эти минимальные элементы образуют запрещенную графическую характеристику F F : графы в - это в точности те графы , которые не имеют ни одного графа в H в качестве минора. Члены H называются исключенными минорами (или запрещенными минорами , или минорно-минимальными препятствиями для семейства F. )

Например, планарные графы замкнуты относительно миноров: стягивание ребра в планарном графе или удаление ребер или вершин из графа не может нарушить его планарность. Следовательно, планарные графы имеют запрещенную второстепенную характеризацию, которая в данном случае дается теоремой Вагнера : множество H минорно-минимальных непланарных графов содержит ровно два графа, полный граф K ₅ и полный двудольный граф K _3,3 , а планарные графы — это именно те графы, которые не имеют минора в множестве { K ₅ , K _3,3 }.

Существование запрещенных второстепенных характеристик для всех минорно-замкнутых семейств графов является эквивалентным способом формулировки теоремы Робертсона-Сеймура. Действительно, предположим, что каждое минорно-замкнутое семейство F имеет конечное множество H минимальных запрещенных миноров и пусть S — любое бесконечное множество графов. Определим F из S не имеющих минора в S. как семейство графов , Тогда F минорно-замкнуто и имеет конечное множество H минимальных запрещенных миноров. Пусть C дополнение к F. — S — подмножество C поскольку S и F не пересекаются, а H — минимальные графы в C. , Рассмотрим граф G в H . G не может иметь собственного минора в S, G минимальна в C. поскольку В то же время G должен иметь минор в S , так как в противном случае был бы элементом в F. G Следовательно, G — элемент в S , т. е. H — подмножество S , а все остальные графы в S имеют минор среди графов в H , поэтому H — конечное множество минимальных S. элементов

Для другого импликации предположим, что каждый набор графов имеет конечное подмножество минимальных графов, и пусть минорно-замкнутое множество F. задано Мы хотим найти множество графов H такое, что граф находится в F тогда и только тогда, когда у него нет минора в H . Пусть E — графы, которые не являются минорами ни одного графа из , и пусть H — конечное множество минимальных графов из E. F произвольный граф G. Пусть теперь дан Предположим сначала, что G находится в F . G не может иметь минор в H, G находится в F , а H является подмножеством E. поскольку Теперь предположим, что G не находится в F . Тогда G не является минором какого-либо графа из F , поскольку F минорно замкнут. Следовательно, G в E , поэтому G имеет минор в H. находится

Примеры несовершеннолетних-замкнутых семей

Следующие множества конечных графов минорно-замкнуты и, следовательно, (по теореме Робертсона-Сеймура) имеют запрещенные второстепенные характеризации:

• леса , линейные леса ( непересекающиеся объединения графов путей ), псевдолеса и графы кактусов ;
• плоские графы , внешнепланарные графы , вершинные графы (сформированные путем добавления одной вершины к планарному графу), тороидальные графы и графы, которые можно встроить в любое фиксированное двумерное многообразие ;
• графы, вложимые без зацеплений в евклидово 3-пространство, и графы, вложимые без узлов в евклидово 3-пространство;
• графы с множеством вершин обратной связи , размер которых ограничен некоторой фиксированной константой; графы с графическим инвариантом Колена де Вердьера, ограниченным некоторой фиксированной константой; графы с шириной дерева , шириной пути или шириной ветки, ограниченной некоторой фиксированной константой.

Наборы препятствий

Семейство Петерсенов — набор препятствий для бессвязного встраивания.

Некоторые примеры конечных множеств препятствий для конкретных классов графов были известны еще до того, как была доказана теорема Робертсона – Сеймура. Например, препятствием для множества всех лесов является петлевой граф (или, если ограничиться простыми графами , цикл с тремя вершинами). Это означает, что граф является лесом тогда и только тогда, когда ни один из его миноров не является петлей (или циклом с тремя вершинами соответственно). Единственным препятствием для множества путей является дерево с четырьмя вершинами, одна из которых имеет степень 3. В этих случаях множество препятствий содержит единственный элемент, но в общем случае это не так. Теорема Вагнера утверждает, что граф планарен тогда и только тогда, когда он не имеет ни K ₅ , ни K _3,3 в качестве минора. Другими словами, набор { K ₅ , K _3,3 } является множеством препятствий для множества всех планарных графов и фактически единственным минимальным множеством препятствий. Аналогичная теорема утверждает, что K ₄ и K _2,3 являются запрещенными минорами для множества внешнепланарных графов.

Хотя теорема Робертсона-Сеймура распространяет эти результаты на произвольные минорно-замкнутые семейства графов, она не является полной заменой этих результатов, поскольку не дает явного описания множества препятствий для любого семейства. Например, он сообщает нам, что набор тороидальных графов имеет конечное множество препятствий, но не предоставляет такого набора. Полный набор запрещенных миноров тороидальных графов остается неизвестным, но он содержит не менее 17 535 графов.

Полиномиальное распознавание времени

Теорема Робертсона-Сеймура имеет важное значение для сложности вычислений благодаря доказательству Робертсона и Сеймура, что для каждого фиксированного графа h существует алгоритм с полиномиальным временем для проверки того, имеет ли граф h в качестве минора. Время работы этого алгоритма является кубическим (размером проверяемого графа), хотя и с постоянным коэффициентом, который суперполиномиально зависит от размера минора h . Каварабаяши, Кобаяши и Рид увеличили время работы до квадратичного. В результате для каждого минорно-замкнутого семейства F существует алгоритм с полиномиальным временем проверки принадлежности графа F : просто проверьте, содержит ли данный граф h для каждого запрещенного минора h в F. множестве препятствий

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

Управляемость с фиксированными параметрами

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

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

Конечная форма малой теоремы о графе

Фридман, Робертсон и Сеймур (1987) показали, что следующая теорема демонстрирует феномен независимости , будучи недоказуемой в различных формальных системах, которые намного сильнее, чем арифметика Пеано , но при этом доказуемы в системах, намного более слабых, чем ZFC :

Теорема : Для каждого натурального числа n существует целое число m , настолько большое, что если G ₁ , ..., G _m — последовательность конечных неориентированных графов,

где каждый G _i имеет размер не более n + i , то G _j ≤ G _k для некоторого j < k .

(Здесь размер графа — это общее количество его вершин и ребер, а ≤ обозначает младший порядок.)

См. также

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

Ссылки

• Биншток, Дэниел; Лэнгстон, Майкл А. (1995), «Алгоритмические последствия малой теоремы о графе» (PDF) , Сетевые модели , Справочники по исследованию операций и науке управления, том. 7, стр. 481–502, номер документа : 10.1016/S0927-0507(05)80125-2 .
• Дистель, Рейнхард (2005), «Несовершеннолетние, деревья и WQO», Теория графов (PDF) (электронное издание, 2005 г.), Springer, стр. 326–367 .
• Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1988), «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время», Journal of the ACM , 35 (3): 727–739, doi : 10.1145/44483.44491 .
• Фридман, Харви ; Робертсон, Нил ; Сеймур, Пол (1987), «Метаматематика второстепенной теоремы о графе», в Симпсон, С. (редактор), Логика и комбинаторика , Современная математика, том. 65, Американское математическое общество , стр. 229–261 .
• Каварабаяси, Кеничи ; Кобаяши, Юсуке; Рид, Брюс (2012), «Проблема непересекающихся путей в квадратичном времени» (PDF) , Journal of Combinatorial Theory, Series B , 102 (2): 424–435, doi : 10.1016/j.jctb.2011.07.004 .
• Ловас, Ласло (2005), «Теория минорных графов», Бюллетень Американского математического общества , Новая серия, 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8 .
• Мирволд, Венди ; Вудкок, Дженнифер (2018), «Большой набор торических препятствий и как они были обнаружены» , Электронный журнал комбинаторики , 25 (1): P1.16, doi : 10.37236/3797 .
• Робертсон, Нил ; Сеймур, Пол (1983), «Незначительные графы. I. Исключая лес», Журнал комбинаторной теории, серия B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5 .
• Робертсон, Нил ; Сеймур, Пол (1995), «Незначительные графы. XIII. Проблема непересекающихся путей», Журнал комбинаторной теории, серия B , 63 (1): 65–110, doi : 10.1006/jctb.1995.1006 .
• Робертсон, Нил ; Сеймур, Пол (2004), «Незначительные графы. XX. Гипотеза Вагнера», Журнал комбинаторной теории, серия B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001 .

Внешние ссылки

• Вайсштейн, Эрик В. , «Теорема Робертсона-Сеймура» , MathWorld