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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Снарк «цветок»[en] J5 — один из шести снарков с 20 вершинами.

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

В статье журнала The Electronic Journal of Combinatorics Мирослав Хладный утверждает, что

При изучении различных важных и сложных задач теории графов (таких, как гипотеза о двойном покрытии циклами[en] и гипотеза о 5-потоке) попадаются интересные, но в чём-то странные графы, называемые снарками. Вопреки своему простому определению … и более чем вековому изучению, их свойства и структура в большей части остаются неизвестными. [1]

— Мирослав Хладный (Miroslav Chladný)

История[править | править вики-текст]

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

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

Свойства[править | править вики-текст]

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

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

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

Теорема о снарках[править | править вики-текст]

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

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

Список снарков[править | править вики-текст]

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

Ссылки[править | править вики-текст]

  1. Miroslav Chladný, Martin Škoviera Factorisation of snarks // The Electronic Journal of Combinatorics. — 2010. — Т. 17. — С. R32.
  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. — В. 3. — Т. 8. — С. 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. — В. 3. — Т. 82. — С. 221–239. — DOI:10.2307/2319844
  8. Martin Gardner Mathematical Games // Scientific American. — 1976. — В. 234. — Т. 4. — С. 126–130.
  9. Steffen Classification and characterizations of snarks // Discrete Mathematics. — 1998. — В. 1–3. — Т. 188. — С. 183–203. — DOI:10.1016/S0012-365X(97)00255-0
  10. «» 
  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. 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.
  13. Martin Kochol Journal of Combinatorial Theory, Series B. — 1996. — Т. 67. — С. 34–47..
  14. Martin Kochol Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani. — 2009. — Т. 5417. — С. 319–323..
  15. Martin Kochol Proceedings of the American Mathematical Society. — 2009. — Т. 137. — С. 1613–1619..
  16. Robin Thomas Surveys in Combinatorics, 1999. — Cambridge University Press, 1999. — С. 201–222.
  17. Sarah-Marie Belcastro The continuing saga of snarks // The College Mathematics Journal. — 2012. — В. 1. — Т. 43. — С. 82–87. — DOI:10.4169/college.math.j.43.1.082.
  18. 4-flow conjecture, Open Problem Garden.
  19. 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.