В теории графов теорема Робертсона –Сеймура (также называемая теоремой о минорах графа [1] ) утверждает, что неориентированные графы , частично упорядоченные отношением миноров графа , образуют вполне квазиупорядоченный граф . [2] Эквивалентно, каждое семейство графов, замкнутое относительно миноров, может быть определено конечным набором запрещенных миноров , таким же образом, как теорема Вагнера характеризует планарные графы как графы , которые не имеют полного графа K5 или полного двудольного графа K3,3 в качестве миноров.
Теорема Робертсона–Сеймура названа в честь математиков Нила Робертсона и Пола Д. Сеймура , которые доказали ее в серии из двадцати статей, охватывающих более 500 страниц, с 1983 по 2004 год. [3] До доказательства утверждение теоремы было известно как гипотеза Вагнера в честь немецкого математика Клауса Вагнера , хотя Вагнер утверждал, что никогда не выдвигал эту гипотезу. [4]
Более слабый результат для деревьев следует из теоремы Крускала о деревьях , которая была выдвинута в 1937 году Эндрю Важсони и доказана в 1960 году независимо Джозефом Крускалом и С. Тарковским. [5]
Минор неориентированного графа G — это любой граф, который может быть получен из G последовательностью нуля или более сокращений ребер G и удалений ребер и вершин G. Минорное отношение образует частичный порядок на множестве всех различных конечных неориентированных графов, поскольку оно подчиняется трем аксиомам частичных порядков: оно рефлексивно (каждый граф является минором самого себя), транзитивно (минор минора G сам является минором G ) и антисимметрично (если два графа G и H являются минорами друг друга, то они должны быть изоморфны ). Однако, если графы, которые являются изоморфными, тем не менее могут рассматриваться как различные объекты, то минорное упорядочение на графах образует предпорядок — отношение, которое рефлексивно и транзитивно, но не обязательно антисимметрично. [6]
Говорят, что предпорядок образует вполне квазиупорядоченный порядок , если он не содержит ни бесконечной нисходящей цепи , ни бесконечной антицепи . [7] Например, обычный порядок на неотрицательных целых числах является вполне квазиупорядоченным, но тот же самый порядок на множестве всех целых чисел не является таковым, поскольку он содержит бесконечную нисходящую цепь 0, −1, −2, −3... Другим примером является множество положительных целых чисел, упорядоченное по делимости , которое не имеет бесконечных нисходящих цепей, но где простые числа образуют бесконечную антицепь.
Теорема Робертсона–Сеймура утверждает, что конечные неориентированные графы и миноры графов образуют хорошо квазиупорядоченный граф. Отношение минора графа не содержит бесконечной нисходящей цепи, поскольку каждое сжатие или удаление уменьшает количество ребер и вершин графа (неотрицательное целое число). [8] Нетривиальная часть теоремы заключается в том, что не существует бесконечных антицепей, бесконечных множеств графов, которые не связаны друг с другом минорным упорядочением. Если S — множество графов, а M — подмножество S, содержащее один репрезентативный граф для каждого класса эквивалентности минимальных элементов (графов, которые принадлежат S , но для которых ни один собственный минор не принадлежит S ), то M образует антицепь; следовательно, эквивалентный способ сформулировать теорему состоит в том, что в любом бесконечном множестве графов S должно быть только конечное число неизоморфных минимальных элементов.
Другая эквивалентная форма теоремы заключается в том, что в любом бесконечном множестве графов S должна быть пара графов, один из которых является минором другого. [8] Утверждение о том, что каждое бесконечное множество имеет конечное число минимальных элементов, подразумевает эту форму теоремы, поскольку если имеется только конечное число минимальных элементов, то каждый из оставшихся графов должен принадлежать паре этого типа с одним из минимальных элементов. И в другом направлении эта форма теоремы подразумевает утверждение о том, что не может быть бесконечных антицепей, поскольку бесконечная антицепь — это множество, которое не содержит ни одной пары, связанной минорным отношением.
Семейство графов F называется замкнутым относительно операции взятия миноров, если каждый минор графа из F также принадлежит F . Если F является замкнутым по минорам семейством, то пусть S будет классом графов, которые не принадлежат F ( дополнение к F ). Согласно теореме Робертсона–Сеймура, существует конечное множество H минимальных элементов в S . Эти минимальные элементы образуют характеристику запрещенного графа F : графы из F — это в точности графы, которые не имеют ни одного графа из H в качестве минора. [9] Члены 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 и F не пересекаются, а H — минимальные графы в C . Рассмотрим граф G в H . G не может иметь собственного минора в S , поскольку G минимален в C . В то же время G должен иметь минор в S , поскольку в противном случае G был бы элементом в F . Следовательно, G является элементом в S , т.е. H является подмножеством S , и все другие графы в S имеют минор среди графов в H , поэтому H является конечным множеством минимальных элементов S.
Для другого следствия предположим, что каждое множество графов имеет конечное подмножество минимальных графов, и пусть задано минорно-замкнутое множество F. Мы хотим найти множество графов H , такое, что граф принадлежит F тогда и только тогда, когда у него нет минора в H. Пусть E — графы, которые не являются минорами ни одного графа из F , и пусть H — конечное множество минимальных графов из E. Теперь пусть задан произвольный граф G. Предположим сначала , что G принадлежит F. G не может иметь минор в H, поскольку G принадлежит F , а H является подмножеством E. Теперь предположим, что G не принадлежит F. Тогда G не является минором ни одного графа из F , поскольку F является минорно-замкнутым. Следовательно, G принадлежит E , поэтому G имеет минор в H.
Следующие множества конечных графов являются минорно замкнутыми и, следовательно (по теореме Робертсона–Сеймура), имеют запрещенные минорные характеризации:
Некоторые примеры конечных множеств препятствий были известны для определенных классов графов еще до доказательства теоремы Робертсона–Сеймура. Например, препятствием для множества всех лесов является петлевой граф (или, если ограничиться простыми графами , цикл с тремя вершинами). Это означает, что граф является лесом тогда и только тогда, когда ни один из его миноров не является петлей (или циклом с тремя вершинами соответственно). Единственным препятствием для множества путей является дерево с четырьмя вершинами, одна из которых имеет степень 3. В этих случаях множество препятствий содержит один элемент, но в общем случае это не так. Теорема Вагнера утверждает, что граф является планарным тогда и только тогда, когда он не имеет ни K 5 , ни K 3,3 в качестве минора. Другими словами, множество { K 5 , K 3,3 } является множеством препятствий для множества всех планарных графов и фактически единственным минимальным множеством препятствий. Аналогичная теорема утверждает, что K 4 и K 2,3 являются запрещенными минорами для множества внешнепланарных графов.
Хотя теорема Робертсона–Сеймура распространяет эти результаты на произвольные семейства минорно-замкнутых графов, она не является полной заменой этих результатов, поскольку не дает явного описания множества препятствий для любого семейства. Например, она говорит нам, что множество тороидальных графов имеет конечное множество препятствий, но не дает никакого такого множества. Полный набор запрещенных миноров для тороидальных графов остается неизвестным, но он содержит по крайней мере 17 535 графов. [11]
Теорема Робертсона–Сеймура имеет важное следствие в вычислительной сложности, благодаря доказательству Робертсона и Сеймура, что для каждого фиксированного графа h существует алгоритм полиномиального времени для проверки, содержит ли граф h в качестве минора. Время работы этого алгоритма является кубическим (по размеру проверяемого графа), хотя с постоянным множителем, который зависит суперполиномиально от размера минора h . Время работы было улучшено до квадратичного Каварабаяши, Кобаяши и Ридом. [12] В результате для каждого замкнутого по минорам семейства F существует алгоритм полиномиального времени для проверки принадлежности графа F : просто проверьте, содержит ли заданный граф h для каждого запрещенного минора h в множестве препятствий F. [ 13]
Однако этот метод требует для работы определенного конечного множества препятствий, а теорема его не предоставляет. Теорема доказывает, что такое конечное множество препятствий существует, и поэтому задача является полиномиальной из-за приведенного выше алгоритма. Однако алгоритм может быть использован на практике только в том случае, если предоставлено такое конечное множество препятствий. В результате теорема доказывает, что задача может быть решена за полиномиальное время, но не предоставляет конкретного алгоритма с полиномиальным временем для ее решения. Такие доказательства полиномиальности неконструктивны : они доказывают полиномиальность задач, не предоставляя явного алгоритма с полиномиальным временем. [14] Во многих конкретных случаях проверка того, находится ли граф в заданном минорно-замкнутом семействе, может быть выполнена более эффективно: например, проверка того, является ли граф планарным, может быть выполнена за линейное время.
Для инвариантов графа со свойством, что для каждого k графы с инвариантом не более k являются минорно замкнутыми, применяется тот же метод. Например, согласно этому результату, treewidth, branchwidth и pathwidth, vertex cover и минимальный род вложения поддаются этому подходу, и для любого фиксированного k существует алгоритм полиномиального времени для проверки того, являются ли эти инварианты не более k , в котором показатель степени во времени выполнения алгоритма не зависит от k . Проблема с этим свойством, то есть ее можно решить за полиномиальное время для любого фиксированного k с показателем степени, не зависящим от k , известна как fixed-parameter tractable .
Однако этот метод не предоставляет напрямую единого алгоритма с фиксированными параметрами для вычисления значения параметра для заданного графа с неизвестным k из-за сложности определения набора запрещенных миноров. Кроме того, большие постоянные факторы, вовлеченные в эти результаты, делают их крайне непрактичными. Поэтому разработка явных алгоритмов с фиксированными параметрами для этих задач с улучшенной зависимостью от k продолжает оставаться важным направлением исследований.
Фридман, Робертсон и Сеймур (1987) показали, что следующая теорема демонстрирует феномен независимости , будучи недоказуемой в различных формальных системах, которые намного сильнее арифметики Пеано , но при этом доказуемой в системах намного слабее ZFC :
(Здесь размер графа — это общее число его вершин и ребер, а ≤ обозначает второстепенный порядок.)