Теорема Робертсона – Сеймура - Robertson–Seymour theorem

В теории графов , то теорема Робертсон-Сеймура (также называемая теоремой графа второстепенной ) утверждает , что неориентированные графы , частично упорядоченных по малому графу отношений, образуют хорошо квази-упорядочивание . Эквивалентно каждое семейство графов, замкнутое относительно миноров, может быть определено конечным набором запрещенных миноров , точно так же, как теорема Вагнера характеризует планарные графы как графы, не имеющие полного графа K 5 или полного двудольного графа. граф 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 5 и полный двудольный граф K 3,3 , а планарные графы - это в точности те графы, которые не имеют минора в множестве { K 5 ,  K 3,3 }.

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

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

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

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

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

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

Семья Петерсена , препятствие для вложения без звеньев.

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

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

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

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

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

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

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

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

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

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

Теорема : для любого натурального числа n существует такое большое целое число m, что если G 1 , ..., G m является последовательностью конечных неориентированных графов,
где каждый G i имеет размер не более n + i , тогда G j ≤ G k для некоторого j < k .

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

Смотрите также

Примечания

использованная литература

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