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

В теория графов, то Теорема Робертсона – Сеймура (также называемый малая теорема о графике[1]) утверждает, что неориентированные графы, частично заказанный посредством граф минор отношения, сформировать хорошо квазиупорядоченный.[2] Эквивалентно, любое семейство графов, замкнутое относительно миноров, может быть определено конечным набором запрещенные несовершеннолетние, так же, как Теорема Вагнера характеризует планарные графы как графики, не имеющие полный график K5 или полный двудольный граф K3,3 как несовершеннолетние.

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

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

Заявление

А незначительный из неориентированный граф грамм любой граф, который может быть получен из грамм последовательностью из нуля или более стягиваний ребер грамм и удаления ребер и вершин грамм. Второстепенные отношения образуют частичный заказ на множестве всех различных конечных неориентированных графов, поскольку он подчиняется трем аксиомам частичного порядка: рефлексивный (каждый граф является второстепенным сам по себе), переходный (несовершеннолетний или несовершеннолетний грамм сам является несовершеннолетним из грамм), и антисимметричный (если два графика грамм и ЧАС являются несовершеннолетними друг друга, то они должны быть изоморфный ). Однако, если графы, которые изоморфны, тем не менее, могут рассматриваться как отдельные объекты, то второстепенный порядок на графах формирует Предварительный заказ, отношение, которое является рефлексивным и транзитивным, но не обязательно антисимметричным.[6]

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

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

Другая эквивалентная форма теоремы состоит в том, что в любом бесконечном множестве S графов должна существовать пара графов, один из которых является второстепенным по отношению к другому.[8] Утверждение, что каждое бесконечное множество имеет конечное число минимальных элементов, влечет эту форму теоремы, поскольку, если существует только конечное число минимальных элементов, то каждый из оставшихся графов должен принадлежать паре этого типа с одним из минимальных элементов. С другой стороны, эта форма теоремы подразумевает утверждение, что не может быть бесконечных антицепей, потому что бесконечная антицепь - это множество, которое не содержит никаких пар, связанных второстепенным отношением.

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

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

Например, планарные графы замкнуты относительно взятия миноров: сжатие ребра в плоском графе или удаление ребер или вершин из графа не может нарушить его планарность. Следовательно, планарные графы имеют запрещенную второстепенную характеристику, которая в этом случае дается Теорема Вагнера: набор ЧАС минорно-минимальных неплоских графов содержит ровно два графа, полный график K5 и полный двудольный граф K3,3, а планарные графы - это именно те графы, которые не имеют минора в множестве {K5, K3,3}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

  1. ^ Бинсток и Лэнгстон (1995).
  2. ^ Робертсон и Сеймур (2004).
  3. ^ Робертсон и Сеймур (1983, 2004 ); Дистель (2005 г.), п. 333).
  4. ^ Дистель (2005 г., п. 355).
  5. ^ Дистель (2005 г.), стр. 335–336); Ловас (2005), Раздел 3.3, стр. 78–79.
  6. ^ Например, см. Бинсток и Лэнгстон (1995), Раздел 2, «ну-квази-порядки».
  7. ^ Дистель (2005 г., п. 334).
  8. ^ а б Ловас (2005 г., п. 78).
  9. ^ Бинсток и Лэнгстон (1995), Следствие 2.1.1; Ловас (2005), Теорема 4, с. 78.
  10. ^ а б Ловас (2005 г. С. 76–77).
  11. ^ Мирвольд и Вальдшнеп (2018).
  12. ^ Каварабаяши, Кобаяши и Рид (2012)
  13. ^ Робертсон и Сеймур (1995); Бинсток и Лэнгстон (1995), Теорема 2.1.4 и следствие 2.1.5; Ловас (2005), Теорема 11, с. 83.
  14. ^ Товарищи и Лэнгстон (1988); Бинсток и Лэнгстон (1995), Раздел 6.

Рекомендации

внешняя ссылка