Снарк (теория графов)

Перейти к навигацииПерейти к поиску
Снарк «Цветок» J5 — один из шести снарков с 20 вершинами.

Снарк в теории графов — связный кубический граф без мостов c хроматическим индексом 4. Другими словами, это граф, в котором каждая вершина имеет три соседние вершины и рёбра нельзя выкрасить только в три цвета, так чтобы два ребра одного цвета не сходились в одной вершине. (По теореме Визинга хроматический индекс кубического графа равен 3 или 4.) Чтобы избежать тривиальных случаев, снарками часто не считают графы, имеющие обхват меньше 5.

Считается, что несмотря на простое определение и длительную историю изучения, свойства и структура снарков малоизвестны[1].

История

Питер Тэт впервые заинтересовался снарками в 1880 году, когда им было доказано, что теорема о четырёх красках эквивалентна утверждению, что никакой снарк не является планарным[2]. Первым известным снарком стал граф Петерсена, найденный в 1898 году. В 1946 году югославский математик Данило Блануша нашёл ещё два снарка, оба с 18 вершинами, получившие название снарков Блануши[3]. Четвёртый снарк был найден двумя годами позже Таттом, работавшим под псевдонимом Бланш Декарт (Blanche Descartes), и это был граф порядка 210[4][5]. В 1973 году Секереш нашёл пятый снарк — Снарк Секереша.[6] В 1975 году Айзекс Руфус обобщил метод Блануши для построения двух бесконечных семейств снарков — цветы и BDS (снарк Блануши — Декарта — Секереша), семейство, включающее два снарка Блануши, снарк Декарта и снарк Секереша[7]. Айзекс обнаружил также снарк с 30 вершинами, не принадлежащий семейству BDS и не являющийся цветком — двойную звезду.

Термин «снарк» был введён Мартином Гарднером в 1976 году по неуловимому существу снарку из поэмы «Охота на Снарка» Льюиса Кэрролла[8].

Свойства

Все снарки являются негамильтоновыми и многие из известных снарков являются гипогамильтоновы — удаление любой отдельной вершины даёт гамильтонов подграф. Гипогамильтоновы снарки должны быть бикритическими — удаление любых двух вершин даёт подграф, раскрашиваемый рёберно в 3 цвета.[9][10]

Было показано, что число снарков для заданного числа вершин ограничена экспоненциальной функцией[11]. (Будучи кубическими графами, все снарки должны иметь чётное число вершин.) OEIS последовательность A130315 содержит число нетривиальных снарков с 2n вершинами для малых значений n[12].

Гипотеза о двойном покрытии циклами утверждает, что в любом графе без мостов можно найти набор циклов, покрывающих каждое ребро дважды, или, что эквивалентно, что граф можно вложить в поверхность таким образом, что все грани будут простыми циклами. Снарки образуют трудный случай для этой гипотезы — если она верна для снарков, она верна для всех графов[13]. В этой связи Бранко Грюнбаум высказал гипотезу, что нельзя вложить любой снарк в поверхность таким способом, что все грани являются простыми циклами и при этом две любых грани либо не имеют общих рёбер, либо имеют одно общее ребро. Однако Мартин Кохол нашёл контпример к этой гипотезе Грюнбаума[14][15][16].

Теорема о снарках

Татт высказал гипотезу, что любой снарк имеет граф Петерсена в качестве минора. Таким образом, он предположил, что наименьший снарк, граф Петерсена, можно получить из любого другого снарка путём стягивания некоторых рёбер и удаления других. Что эквивалентно (поскольку граф Петерсена имеет максимальную степень три), утверждению, что любой снарк содержит подграф, который можно получить из графа Петерсена путём деления некоторых рёбер. Эта гипотеза является усилением теоремы о четырёх красках, поскольку любой граф, содержащий граф Петерсена в качестве минора, не может быть планарным. В 1999 году Робертсон[англ.], Сандерс[англ.], Сеймур и Томас объявили о доказательстве гипотезы[17], однако по состоянию на 2012 год доказательство опубликовано лишь частично[18].

Татт также предложил в качестве гипотезы обобщённую теорему о снарках для произвольных графов — любой граф без мостов, не имеющий граф Петерсена в качестве минора, имеет нигде не нулевой 4-поток. Что означает, что рёбрам графа можно задать направления и пометить числами из множества {1, 2, 3} так, что сумма входящих чисел минус сумма исходящих в каждой вершине делится на четыре. Как показал Татт, такое назначение для кубических графов существует в том и только в том случае, когда рёбра можно раскрасить в три цвета, так что в этом случае гипотеза следует из теоремы о снарках. Однако гипотеза остаётся открытой для остальных графов (не кубических)[19].

Список снарков

Список всех снарков с 36 вершинами, за исключением снарков с 36 вершинами и обхватом 4, был создан Гуннаром Бринкманом, Яном Гёдгебером, Джонасом Хегглундом и Класом Маркстрёмом в 2012 году[20].

Примечания

  1. ↑ Miroslav Chladný, Martin Škoviera. Factorisation of snarks // The Electronic Journal of Combinatorics. — 2010. — Т. 17. — С. R32. — «In the study of various important and difficult problems in graph theory (such as the Cycle double cover conjecture and the 5-Flow Conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition… and over a century long investigation, their properties and structure are largely unknown.» Перевод: «При изучении различных важных и сложных задач теории графов (таких, как гипотеза о двойном покрытии циклами и гипотеза о 5-потоке) попадаются интересные, но в чём-то странные графы, называемые снарками. Вопреки своему простому определению … и более чем вековому изучению, их свойства и структура в большей части остаются неизвестными.»
  2. ↑ P. G. Tait. Remarks on the colourings of maps // Proc. R. Soc. Edinburgh. — 1880. — Т. 10. — С. 729.
  3. ↑ Danilo Blanuša. Problem četiriju boja // Glasnik Mat. Fiz. Astr. Ser II. — 1946. — Т. 1. — С. 31–42.
  4. ↑ Blanche Descartes, Network-colourings, The Mathematical Gazette (London) 32, 67-69, 1948.
  5. ↑ Martin Gardner, The Last Recreations: Hydras, Eggs, and Other Mathematical Mystifications, Springer, 2007, ISBN 0-387-25827-2, ISBN 978-0-387-25827-0
  6. ↑ G. Szekeres. Polyhedral decompositions of cubic graphs // Bull. Austral. Math. Soc.. — 1973. — Т. 8, вып. 3. — С. 367–387. — doi:10.1017/S0004972700042660.
  7. ↑ R. Isaacs. Infinite families of non-trivial trivalent graphs which are not Tait-colorable // American Mathematical Monthly. — 1975. — Т. 82, вып. 3. — С. 221–239. — doi:10.2307/2319844. — JSTOR 2319844.
  8. ↑ Martin Gardner. Mathematical Games // Scientific American. — 1976. — Т. 4, вып. 234. — С. 126–130.
  9. ↑ Steffen E. Classification and characterizations of snarks // Discrete Mathematics. — 1998. — Т. 188, вып. 1–3. — С. 183–203. — doi:10.1016/S0012-365X(97)00255-0.
  10. ↑ Steffen E. On bicritical snarks // Math. Slovaca. — 2001. — Т. 51, вып. 2. — С. 141–150.
  11. ↑ Z. Skupień. 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. — Electronic Notes in Discrete Mathematics. — 2007. — Т. 28. — С. 417–424. — doi:10.1016/j.endm.2007.01.059.
  12. ↑ последовательность A130315 в OEIS
  13. ↑ F. Jaeger. Annals of Discrete Mathematics 27 – Cycles in Graphs. — 1985. — Т. 27. — С. 1–12. — (North-Holland Mathematics Studies). — ISBN 978-0-444-87803-8. — doi:10.1016/S0304-0208(08)72993-1..
  14. ↑ Martin Kochol. Journal of Combinatorial Theory, Series B. — 1996. — Т. 67. — С. 34–47.
  15. ↑ Martin Kochol. Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani. — 2009. — Т. 5417. — С. 319–323..
  16. ↑ Martin Kochol. Proceedings of the American Mathematical Society. — 2009. — Т. 137. — С. 1613–1619.
  17. ↑ Robin Thomas. Surveys in Combinatorics, 1999. — Cambridge University Press, 1999. — С. 201–222. Архивировано 3 августа 2016 года.
  18. ↑ Sarah-Marie Belcastro. The continuing saga of snarks // The College Mathematics Journal. — 2012. — Т. 43, вып. 1. — С. 82–87. — doi:10.4169/college.math.j.43.1.082.. См. также гипотезу Хадвигера и результаты, связанные раскраской миноров графа.
  19. ↑ 4-flow conjecture Архивная копия от 8 февраля 2012 на Wayback Machine, Open Problem Garden.
  20. ↑ Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund and Klas Markström. Generation and Properties of Snarks. — 2012.

Ссылки

  • Weisstein, Eric W. Snark (англ.) на сайте Wolfram MathWorld.
  • Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). «Blanuša Double». Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia.