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

Эта статья о термине в теории графов. Чтобы узнать о других значениях, см. Снарк (значения) .

Граф Петерсена — наименьшая хитрость.

Цветочный снарк J ₅ — один из шести снарков на 20 вершинах.

В математической области теории графов снарк неориентированный — это граф , имеющий ровно три ребра на вершину , ребра которого нельзя раскрасить только тремя цветами. Чтобы избежать тривиальных случаев, снарки часто ограничиваются дополнительными требованиями к их связности и длине их циклов . Существует бесконечно много снарков.

Одна из эквивалентных форм теоремы о четырех цветах состоит в том, что каждый снарк представляет собой непланарный граф . Исследование снарков зародилось в работе Питера Г. Тейта над теоремой о четырех цветах в 1880 году, но их название гораздо более новое, данное им Мартином Гарднером в 1976 году. Помимо раскраски, снарки также связаны с другими сложными проблемами теории графов. : в статье в «Электронном журнале комбинаторики » Мирослав Хладный и Мартин Шковьера заявляют, что

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

Помимо упомянутых ими проблем, У.Т. Тутте касается гипотеза о снарках существования графов Петерсена как миноров снарков; его доказательство уже давно анонсировано, но остается неопубликованным и разрешает частный случай существования нигде ненулевых 4-потоков .

История и примеры

Снарки были названы так американским математиком Мартином Гарднером в 1976 году, в честь загадочного и неуловимого объекта стихотворения Охота на Снарка» « Льюиса Кэрролла . Однако изучение этого класса графов значительно старше их названия. Питер Г. Тейт инициировал изучение снарков в 1880 году, когда доказал, что теорема о четырех цветах эквивалентна утверждению о том, что ни один снарк не является плоским . Первым графом, который, как известно, был снарком, был граф Петерсена ; доказал, что это была шутка . Юлиус Петерсен в 1898 году хотя его уже изучал с другой целью Альфред Кемпе в 1886 году.

Следующие четыре известных снарка были

• снарки Блануши (два по 18 вершин), открытые Данило Бланушей в 1946 году,
• снарк Декарта (210 вершин), открытый Биллом Таттом в 1948 году, и
• снарк Секереса (50 вершин), открытый Джорджем Секересом в 1973 году.

В 1975 году Руфус Айзекс обобщил метод Блануши, создав два бесконечных семейства снарков: цветочные снарки и снарки Блануши-Декарта-Секереса, семейство, которое включает двух снарков Блануши, снарков Декарта и снарков Секереса. Айзекс также обнаружил снарк с 30 вершинами, который не принадлежит семейству Блануши-Декарта-Секереса и не является цветочным снарком: снарк с двойной звездой . с 50 вершинами Снарк Уоткинса был открыт в 1989 году.

Еще один примечательный кубический граф, не раскрашиваемый по трем ребрам, — это граф Титце с 12 вершинами; как обнаружил Генрих Франц Фридрих Титце в 1910 году, он образует границу подразделения ленты Мёбиуса, требующего шести цветов. Однако, поскольку он содержит треугольник, его обычно не считают снарком. Согласно строгим определениям снарков, наименьшими снарками являются граф Петерсена и снарки Блануши, за которыми следуют шесть различных снарков с 20 вершинами.

Список всех снарков до 36 вершин (согласно строгому определению) и до 34 вершин (согласно более слабому определению) был создан Гуннаром Бринкманном, Яном Гегебером, Йонасом Хэгглундом и Класом Маркстремом в 2012 году. Количество снарков для заданного четного числа вершин растет по крайней мере экспоненциально с увеличением количества вершин. (Поскольку у них есть вершины нечетной степени, все снарки должны иметь четное количество вершин по лемме о согласовании связи .) OEIS Последовательность A130315 содержит количество нетривиальных снарков $2n$ вершины для малых значений $n$.

Определение

Точное определение снарков варьируется среди авторов. но обычно относится к кубическим графам (имеющим ровно три ребра в каждой вершине), ребра которых нельзя раскрасить только тремя цветами. По теореме Визинга количество цветов, необходимых для ребер кубического графа, равно либо трем («графы первого класса»), либо четырем («графы второго класса»), поэтому снарки — это кубические графы второго класса. Однако, чтобы избежать случаев, когда снарк относится ко второму классу по тривиальным причинам или строится тривиальным образом из меньших графов, часто накладываются дополнительные ограничения на связность и длину цикла. В частности:

• Если кубический граф имеет мост , ребро, удаление которого могло бы его разъединить, то он не может принадлежать к классу один. По лемме о согласовании подграфы по обе стороны моста имеют нечетное количество вершин каждый. Какой бы из трех цветов ни был выбран для моста, их нечетное количество вершин предотвращает покрытие этих подграфов циклами, которые чередуются между двумя другими цветами, как это было бы необходимо при раскраске с тремя ребрами. По этой причине снарки обычно должны быть без мостов.
• Петля (ребро , соединяющее вершину с самой собой) не может быть раскрашена без того, чтобы один и тот же цвет не появился дважды в этой вершине, что является нарушением обычных требований к раскраске ребер графа. Кроме того, цикл, состоящий из двух вершин, соединенных двумя ребрами, всегда можно заменить одним ребром, соединяющим двух других соседей, что упрощает граф без изменения его трехреберной раскраски. По этим причинам снарки обычно ограничиваются простыми графами , графами без циклов или множественных смежностей.
• Если граф содержит треугольник, то его снова можно упростить, не меняя его трехреберной раскраски, сжимая три вершины треугольника в одну вершину. Поэтому многие определения снарков запрещают треугольники. Однако, хотя это требование было также указано в работе Гарднера, дав этим графам название «снарк», Гарднер называет граф Титце , который содержит треугольник, снарком.
• Если граф содержит цикл из четырех вершин, его можно упростить двумя разными способами, удалив два противоположных ребра цикла и заменив полученные пути вершин второй степени одиночными ребрами. Он имеет трехгранную раскраску тогда и только тогда, когда выполнено хотя бы одно из этих упрощений. Следовательно, Айзексу требуется «нетривиальный» кубический граф второго класса, чтобы избежать циклов с четырьмя вершинами. и другие авторы последовали их примеру, запретив эти циклы. Требование, чтобы снарк избегал циклов длиной четыре или меньше, можно резюмировать, утверждая, что обхват этих графов, длина их самых коротких циклов, равен как минимум пяти.
• Более строго, определение, использованное Brinkmann et al. (2012) требует, чтобы снарки были циклически 4-реберными. Это означает, что не может быть подмножества из трех или менее ребер, удаление которых разделило бы граф на два подграфа, каждый из которых имеет хотя бы один цикл. Бринкманн и др. определить снарк как кубический и циклически 4-реберно-связный граф обхвата пять или более и класса два; они определяют «слабую загвоздку», позволяющую иметь обхват четыре.

Хотя эти определения учитывают только ограничения на обхват до пяти, существуют снарки с сколь угодно большим обхватом.

Характеристики

Работа Питера Г. Тейта установила, что теорема о четырех цветах верна тогда и только тогда, когда каждый снарк непланарен. Эта теорема утверждает, что каждый планарный граф имеет графическую раскраску своих вершин в четыре цвета, но Тейт показал, как преобразовать 4-раскраски вершин максимальных планарных графов в 3-раскраски рёбер их двойственных графов , которые являются кубическими и плоскими. , и наоборот. Таким образом, плоский снарк обязательно будет двойственным контрпримеру к теореме о четырех цветах. Таким образом, последующее доказательство теоремы о четырех красках также демонстрирует, что все снарки неплоские.

Все снарки не гамильтоновы : когда кубический граф имеет гамильтонов цикл, всегда можно раскрасить его ребра в три цвета, используя попеременно два цвета для цикла и третий цвет для остальных ребер. Однако многие известные снарки близки к гамильтоновым в том смысле, что они являются гипогамильтоновыми графами : удаление любой отдельной вершины оставляет гамильтонов подграф. Гипогамильтонов снарк должен быть бикритическим : удаление любых двух вершин оставляет подграф, раскрашиваемый по трем ребрам. Нечетность 2 кубического графа определяется как минимальное количество нечетных циклов в любой системе циклов, которая покрывает каждую вершину один раз ( -фактор ). По той же причине, по которой у них нет гамильтоновых циклов, снарки имеют положительную нечетность: полностью четный 2-фактор приведет к 3-раскраске ребер, и наоборот. Можно построить бесконечные семейства снарков, нечетность которых растет линейно с увеличением количества вершин.

Гипотеза о двойном покрытии цикла утверждает, что в каждом графе без мостов можно найти набор циклов, дважды покрывающих каждое ребро, или, что то же самое, что граф может быть вложен в поверхность таким образом, что все грани вложения являются простыми циклами. Когда кубический граф имеет 3-реберную раскраску, он имеет двойное покрытие цикла, состоящее из циклов, образованных каждой парой цветов. Поэтому среди кубических графов снарки — единственно возможные контрпримеры. В более общем смысле, снарки представляют собой трудный случай для этой гипотезы: если она верна для снарков, то она верна и для всех графов. В этой связи Бранко Грюнбаум предположил, что ни один снарк не может быть встроен в поверхность таким образом, чтобы все грани представляли собой простые циклы и чтобы каждые две грани либо не пересекались, либо имели только одно ребро; если бы какой-либо снарк имел такое вложение, его грани образовывали бы двойную крышку цикла. Однако контрпример гипотезе Грюнбаума нашел Мартин Кохоль.

Определение того, является ли данный циклически 5-связный кубический граф раскрашиваемым в 3 ребра, является NP-полным . Следовательно, определение того, является ли граф снарком, является ко-NP-полным .

Гипотеза Снарка

У. Т. Тутте предположил, что каждая шутка имеет граф Петерсена в качестве минора . То есть он предположил, что наименьший снарк, граф Петерсена, может быть образован из любого другого снарка путем стягивания одних ребер и удаления других. Эквивалентно (поскольку граф Петерсена имеет максимальную степень три), каждый снарк имеет подграф, который можно сформировать из графа Петерсена путем разделения некоторых его ребер . Эта гипотеза является усиленной формой теоремы о четырех цветах , поскольку любой граф, содержащий граф Петерсена в качестве минора, должен быть непланарным. В 1999 году Нил Робертсон , Дэниел П. Сандерс , Пол Сеймур и Робин Томас объявили о доказательстве этой гипотезы. Шаги к этому результату были опубликованы в 2016 и 2019 годах. но полное доказательство остается неопубликованным. см . в гипотезе Хадвигера Другие проблемы и результаты, связанные с раскраской графа и минорами графа, .

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

Внешние ссылки

• Вайсштейн, Эрик В. , «Снарк» , MathWorld