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

Теорема Робертсона — Сеймура (также называемая теоремой о минорах графа [1]) утверждает, что любое семейство графов, замкнутое относительно операций удаления и стягивания рёбер, может быть определено конечным набором запрещённых графов.

Например, множество планарных графов замкнуто по операциям удаления и стягивания рёбер; запрещёнными графами в этом случае являются полный граф K5 и полный двудольный граф K3,3. Последнее утверждение называется теоремой Вагнера и тесно связано с теоремой Понтрягина — Куратовского.

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

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

Утверждение

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

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

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

Другая эквивалентная формулировка теоремы утверждает, что в любом бесконечном множестве S графов должна быть пара графов, один из которых является минором другого[9]. Из утверждения, что любое бесконечное множество имеет конечное число минимальных элементов, следует эта последняя формулировка, поскольку все оставшиеся (неминимальные) графы образуют такую пару. В другом направлении, из этой формулировки теоремы следует, что не может быть бесконечных антицепей, поскольку бесконечная антицепь не содержит элементов, связанных отношением минорности.

Описание запрещёнными минорами

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

Например, планарные графы замкнуты по образованию минора — стягивание ребра в планарном графе или удаление ребра или вершины не может разрушить планарность. Таким образом, планарные графы имеют характеризацию запрещёнными минорами, которые, в этом случае, определяются теоремой Вагнера — множество H минорно минимальных непланарных графов содержит в точности два графа, полный граф K5 и полный двудольный граф K3,3. Планарные же графы — это в точности те графы, которые не имеют в качестве миноров элементы из множества {K5, K3,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. В этих случаях препятствие состоит из единственного элемента, но в общем случае элементов может быть больше. Теорема Вагнера утверждает, что граф планарен тогда и только тогда, когда он не содержит ни K5, ни K3,3 в качестве минора. Другими словами, множество {K5, K3,3} является препятствующим множеством для всех планарных графов, и оно является минимальным препятствующим множеством. Похожая теорема утверждает, что K4 и K2,3 являются запрещёнными минорами для множества внешнепланарных графов.

Хотя теорема Робертсона — Сеймура распространяет эти результаты на произвольные замкнутые по минорам семейства графов, она не подменяет эти результаты, поскольку не даёт явного описания препятствующего множества для любого семейства. Например, теорема указывает, что множество тороидальных графов имеет конечное препятствующее множество, но не даёт ни одного такого множества. Полный набор запрещённых миноров для тороидальных графов остаётся неизвестным и содержит по меньшей мере 16000 графов [13].

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

Теорема Робертсона — Сеймура имеет важное следствие в теории вычислительной сложности, поскольку Робертсон и Сеймур доказали, что для каждого фиксированного графа G существует алгоритм полиномиального времени для проверки, имеет ли больший граф G в качестве минора. Время работы этого алгоритма выражается кубическим многочленом от размера большего графа (хотя есть в этом многочлене постоянный множитель, зависящий сверхполиномно от размера G), и это время улучшили до квадратичного Каварабаяши, Кобаяши и Рид[14]. Таким образом, для любого замкнутого по минорам семейства F существует алгоритм с полиномиальным временем работы, проверяющий, принадлежит ли граф семейству F — просто для всех запрещённых миноров для F проверяем, не содержит ли заданный граф этот запрещённый минор[15][16][17].

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

Фиксированно-параметрическая разрешимость

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

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

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

Фридман, Робертсон и Сеймур[20] показали, что следующая теорема демонстрирует феномен независимости, будучи недоказуемой в различных формальных системах, более строгих, чем арифметика Пеано, но она доказуема в системах, существенно более слабых, чем теория множеств Цермело — Френкеля:

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

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

См. также

Примечания

  1. ↑ 1 2 Bienstock, Langston, 1995.
  2. ↑ Robertson, Seymour, 1983.
  3. ↑ Robertson, Seymour, 2004.
  4. ↑ Diestel, 2005, p. 333.
  5. ↑ Diestel, 2005, p. 355.
  6. ↑ Diestel, 2005, pp. 335–336.
  7. ↑ Lovász, 2005, с. 78–79, Section 3.3.
  8. ↑ Diestel, 2005, p. 334.
  9. ↑ 1 2 Lovász, 2005, p. 78.
  10. ↑ Bienstock, Langston, 1995, с. Corollary 2.1.1.
  11. ↑ Lovász, 2005, с. 78, Theorem 4.
  12. ↑ 1 2 Lovász, 2005, pp. 76–77.
  13. ↑ Chambers, 2002.
  14. ↑ Kawarabayashi, Kobayashi, Reed, 2012.
  15. ↑ Robertson, Seymour, 1995.
  16. ↑ Bienstock, Langston, 1995, с. Th. 2.1.4, C. 2.1.5.
  17. ↑ Lovász, 2005, с. 83, Theorem 11.
  18. ↑ Fellows, Langston, 1988.
  19. ↑ Bienstock, Langston, 1995, с. Section 6.
  20. ↑ Friedman, Robertson, Seymour, 1987.

Литература

  • Daniel Bienstock, Michael A. Langston. Network Models. — 1995. — Т. 7. — С. 481—502. — (Handbooks in Operations Research and Management Science). — doi:10.1016/S0927-0507(05)80125-2.
  • J. Chambers. Hunting for torus obstructions. — Department of Computer Science, University of Victoria, 2002. — (M.Sc. thesis).
  • Reinhard Diestel. Graph Theory. — Electronic Edition 2005. — Springer, 2005. — С. 326—367.
  • Michael R. Fellows, Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability // Journal of the ACM. — 1988. — Т. 35, вып. 3. — С. 727—739. — doi:10.1145/44483.44491.
  • Harvey Friedman, Neil Robertson, Paul Seymour. Logic and Combinatorics / S. Simpson. — American Mathematical Society, 1987. — Т. 65. — С. 229—261. — (Contemporary Mathematics).
  • Ken-ichi Kawarabayashi, Yusuke Kobayashi, Bruce Reed. The disjoint paths problem in quadratic time // Journal of Combinatorial Theory, Series B. — 2012. — Т. 102, вып. 2. — С. 424—435. — doi:10.1016/j.jctb.2011.07.004.
  • László Lovász. Graph Minor Theory // Bulletin of the American Mathematical Society (New Series). — 2005. — Т. 43, вып. 1. — С. 75—86. — doi:10.1090/S0273-0979-05-01088-8.
  • Neil Robertson, Paul Seymour. Graph Minors. I. Excluding a forest // Journal of Combinatorial Theory, Series B. — 1983. — Т. 35, вып. 1. — С. 39—61. — doi:10.1016/0095-8956(83)90079-5..
  • Neil Robertson, Paul Seymour. Graph Minors. XIII. The disjoint paths problem // Journal of Combinatorial Theory, Series B. — 1995. — Т. 63, вып. 1. — С. 65—110. — doi:10.1006/jctb.1995.1006..
  • Neil Robertson, Paul Seymour. Graph Minors. XX. Wagner's conjecture // Journal of Combinatorial Theory, Series B. — 2004. — Т. 92, вып. 2. — С. 325—357. — doi:10.1016/j.jctb.2004.08.001..

Ссылки