В математической области теории графов снарком называется неориентированный граф с ровно тремя ребрами на вершину , ребра которого не могут быть раскрашены только тремя цветами. Чтобы избежать тривиальных случаев, снарки часто ограничиваются дополнительными требованиями к их связности и длине их циклов . Существует бесконечно много снарков.
Одной из эквивалентных форм теоремы о четырех красках является то, что каждый снарки является непланарным графом . Исследования снарков берут начало в работе Питера Г. Тейта над теоремой о четырех красках в 1880 году, но их название гораздо более новое, данное им Мартином Гарднером в 1976 году. Помимо раскраски, снарки также связаны с другими сложными проблемами в теории графов: в своей статье в Electronic Journal of Combinatorics Мирослав Хладны и Мартин Шковиера утверждают, что
При изучении различных важных и сложных проблем в теории графов (таких как гипотеза о двойном покрытии цикла и гипотеза о 5-потоке ) мы сталкиваемся с интересным, но несколько загадочным разнообразием графов, называемых снарками. Несмотря на их простое определение... и более чем столетие исследований, их свойства и структура в значительной степени неизвестны. [1]
Помимо упомянутых ими проблем, гипотеза Снарка У. Т. Тутта касается существования графов Петерсена как миноров графов Снарков; ее доказательство было давно анонсировано, но остается неопубликованным и разрешило бы особый случай существования нигде не нулевых 4-потоков .
Снарки были так названы американским математиком Мартином Гарднером в 1976 году в честь таинственного и неуловимого объекта поэмы Льюиса Кэрролла «Охота на Снарка» . [2] Однако изучение этого класса графов значительно старше их названия. Питер Г. Тейт инициировал изучение снарков в 1880 году, когда доказал, что теорема о четырех красках эквивалентна утверждению, что ни один снарк не является планарным . [3] Первым графом, известным как снарк, был граф Петерсена ; то, что он является снарком, было доказано Юлиусом Петерсеном в 1898 году, [4] хотя он уже изучался с другой целью Альфредом Кемпе в 1886 году. [5]
Следующие четыре известных снарка были
В 1975 году Руфус Айзекс обобщил метод Блануши, чтобы построить два бесконечных семейства снарков: снарки цветов и снарки Блануши–Декарта–Секереша, семейство, которое включает два снарка Блануши, снарки Декарта и снарки Секереша. Айзекс также открыл снарку с 30 вершинами, которая не принадлежит семейству Блануши–Декарта–Секереша и которая не является снарком цветов: снарки двойной звезды . [9] Снарки Уоткинса с 50 вершинами были обнаружены в 1989 году. [10]
Другим примечательным кубическим графом, не поддающимся раскраске тремя ребрами, является граф Титце с 12 вершинами; как обнаружил Генрих Франц Фридрих Титце в 1910 году, он образует границу подразделения ленты Мёбиуса , требующего шести цветов. [11] Однако, поскольку он содержит треугольник, его обычно не считают снарком. Согласно строгим определениям снарков, наименьшими снарками являются граф Петерсена и снарки Блануши, за которыми следуют шесть различных снарков с 20 вершинами. [12]
Список всех снарков до 36 вершин (согласно строгому определению) и до 34 вершин (согласно более слабому определению) был создан Гуннаром Бринкманном, Яном Годгебером, Йонасом Хэгглундом и Класом Маркстрёмом в 2012 году. [12] Количество снарков для заданного четного числа вершин растет по крайней мере экспоненциально с числом вершин. [13] (Поскольку они имеют вершины нечетной степени, все снарки должны иметь четное число вершин по лемме о рукопожатии .) [14] Последовательность OEIS A130315 содержит количество нетривиальных снарков вершин для малых значений . [15]
Точное определение снарков различается у разных авторов, [12] [9], но обычно относится к кубическим графам (имеющим ровно три ребра в каждой вершине), чьи ребра не могут быть раскрашены только тремя цветами. По теореме Визинга , количество цветов, необходимых для ребер кубического графа, равно либо трем (графы «класса один»), либо четырем (графы «класса два»), поэтому снарки являются кубическими графами класса два. Однако, чтобы избежать случаев, когда снарки имеют класс два по тривиальным причинам или построены тривиальным способом из меньших графов, часто накладываются дополнительные ограничения на связность и длину цикла. В частности:
Хотя эти определения учитывают ограничения только на обхват до пяти, существуют снарки с произвольно большим обхватом. [16]
Работа Питера Г. Тейта установила, что теорема о четырех красках верна тогда и только тогда, когда каждый снарк непланарен. [3] Эта теорема утверждает, что каждый планарный граф имеет раскраску своих вершин четырьмя цветами, но Тейт показал, как преобразовать 4-вершинные раскраски максимальных планарных графов в 3-реберные раскраски их двойственных графов , которые являются кубическими и планарными, и наоборот. Поэтому планарный снарк обязательно будет двойственным контрпримеру к теореме о четырех красках. Таким образом, последующее доказательство теоремы о четырех красках [17] также демонстрирует, что все снарки непланарны. [18]
Все снарки негамильтоновы : когда кубический граф имеет гамильтонов цикл, всегда возможно раскрасить его ребра в 3 цвета, используя два цвета попеременно для цикла и третий цвет для оставшихся ребер. Однако многие известные снарки близки к гамильтоновым в том смысле, что они являются гипогамильтоновыми графами : удаление любой одной вершины оставляет гамильтонов подграф. Гипогамильтонов снарки должны быть бикритическими : удаление любых двух вершин оставляет подграф, поддающийся трехреберной раскраске. [19] Нечетность кубического графа определяется как минимальное количество нечетных циклов в любой системе циклов, которая покрывает каждую вершину один раз ( 2-фактор ). По той же причине, по которой у них нет гамильтоновых циклов, снарки имеют положительную нечетность: полностью четный 2-фактор привел бы к трехреберной раскраске, и наоборот. Можно построить бесконечное множество снарков, нечетность которых линейно растет с числом вершин. [14]
Гипотеза о двойном покрытии циклов утверждает, что в каждом графе без мостов можно найти набор циклов, покрывающих каждое ребро дважды, или, что эквивалентно, что граф может быть вложен в поверхность таким образом, что все грани вложения являются простыми циклами. Когда кубический граф имеет 3-рёберную раскраску, он имеет двойное покрытие циклов, состоящее из циклов, образованных каждой парой цветов. Поэтому среди кубических графов снарки являются единственными возможными контрпримерами. В более общем смысле, снарки образуют сложный случай для этой гипотезы: если это верно для снарков, то это верно и для всех графов. [20] В этой связи Бранко Грюнбаум предположил, что никакой снарки не может быть вложен в поверхность таким образом, что все грани являются простыми циклами и что каждые две грани либо не пересекаются, либо имеют только одно ребро; если бы любой снарк имел такое вложение, его грани образовали бы двойное покрытие циклов. Однако контрпример к гипотезе Грюнбаума был найден Мартином Кохолем. [21]
Определение того, является ли заданный циклически 5-связный кубический граф 3-рёберно-раскрашиваемым, является NP-полным . Следовательно, определение того, является ли граф снарком, является ко-NP-полным . [22]
WT Tutte предположил, что каждый снарком имеет граф Петерсена в качестве минора . То есть, он предположил, что наименьший снарком, граф Петерсена, может быть образован из любого другого снарка путем сжатия некоторых ребер и удаления других. Эквивалентно (поскольку граф Петерсена имеет максимальную степень три) каждый снарком имеет подграф, который может быть образован из графа Петерсена путем подразделения некоторых его ребер . Эта гипотеза является усиленной формой теоремы о четырех цветах , поскольку любой граф, содержащий граф Петерсена в качестве минора, должен быть непланарным. В 1999 году Нил Робертсон , Дэниел П. Сандерс , Пол Сеймур и Робин Томас объявили о доказательстве этой гипотезы. [23] Шаги к этому результату были опубликованы в 2016 и 2019 годах, [24] [25], но полное доказательство остается неопубликованным. [18] См . гипотезу Хадвигера для других проблем и результатов, связанных с раскраской графа и минорами графа.
Тутт также предположил обобщение на произвольные графы: каждый граф без мостов без минора Петерсена имеет нигде не нулевой 4-поток . То есть, ребрам графа можно присвоить направление и число из множества {1, 2, 3}, так что сумма входящих чисел за вычетом суммы исходящих чисел в каждой вершине делится на четыре. Как показал Тутт, для кубических графов такое назначение существует тогда и только тогда, когда ребра можно раскрасить тремя цветами, поэтому в этом случае гипотеза будет следовать из гипотезы Снарка. Однако доказательство гипотезы Снарка не решит вопрос о существовании 4-потоков для некубических графов. [26]
