Введение
Граф со всеми вершинами степени 3
В математической области теории графов, кубический граф — это граф, в котором все вершины имеют степень три. Иными словами, кубический граф — это 3-регулярный граф. Кубические графы также называются тривалентными графами. Бикубический граф — это кубический двудольный граф.
Симметрия
В 1932 году Рональд М. Фостер начал собирать примеры кубических симметричных графов, положив начало переписи Фостера. Многие известные графы являются кубическими и симметричными, включая граф полезности, граф Петерсена, граф Хейвуда, граф Мёбиуса — Кантора, граф Паппуса, граф Дезаргеса, граф Науру, граф Коксетера, граф Тютте — Коксетера, граф Дика, граф Фостера и граф Биггса — Смита. У. Т. Тутте классифицировал симметричные кубические графы по наименьшему целому числу s, такому что любые две ориентированные пути длины s можно перевести друг в друга ровно одной симметрией графа. Он показал, что s не превосходит 5, и привел примеры графов с каждым возможным значением s от 1 до 5. К полусимметричным кубическим графам относятся граф Грея (наименьший полусимметричный кубический граф), граф Любляны и клетка Тутте 12. Граф Фрухта — один из пяти наименьших кубических графов, не имеющих никакой симметрии: он обладает единственным автоморфизмом графа — тождественным автоморфизмом.
Цветочные и независимые наборы
Согласно теореме Брукса, любой связный кубический граф, кроме полного графа K4, допускает раскраску вершин не более чем в три цвета. Следовательно, любой связный кубический граф, кроме K4, содержит независимое множество, состоящее как минимум из n/3 вершин, где n — число вершин графа: например, наибольший цветовой класс при раскраске в 3 цвета содержит как минимум столько вершин. Согласно теореме Визинга, для раскраски рёбер любого кубического графа требуется либо три, либо четыре цвета. Раскраска рёбер в три цвета называется раскраской Таита и представляет собой разбиение рёбер графа на три полных сопоставления. По теореме Кёнига о раскраске линий, любой бикубический граф имеет раскраску Таита. Бессвязные кубические графы, не имеющие раскраски Таита, называются снарками. К ним относятся граф Петерсена, граф Тиетце, снарки Блануши, цветочный снарк, снарк двойной звезды, снарк Секереша и снарк Уоткинса. Существует бесконечное количество различных снарков.
Топология и геометрия
Кубические графы возникают естественным образом в топологии несколькими способами. Например, кубические графы с 2g + 2 вершинами описывают различные способы разрезания поверхности рода g ≥ 2 на «штаны». Если рассматривать граф как 1-мерный CW-комплекс, то кубические графы являются типичными, поскольку большинство отображений прикрепления 1-ячеек не пересекаются с 0-скелетом графа. Кубические графы также формируются как графы простых многогранников в трех измерениях, таких как правильный додекаэдр, у которого три грани сходятся в каждой вершине. Произвольное вложение графа на двумерную поверхность может быть представлено как кубическая графовая структура, известная как кодированное отображение графа. В этой структуре каждая вершина кубического графа представляет собой флаг вложения – тройку, состоящую из вершины, ребра и грани поверхности, взаимно инцидентных друг другу. Три соседних флага – это три флага, которые можно получить из данного, изменяя один из элементов этой взаимно инцидентной тройки и оставляя два других без изменений.
Гамильтоносообразность
Было много исследований гамильтоновости кубических графов. В 1880 году П. Г. Тейт предположил, что каждый кубический полиэдрический граф имеет гамильтонов цикл. Уильям Томас Тютте привел контрпример к гипотезе Тейта – граф Тютте с 46 вершинами – в 1946 году. В 1971 году Тютте предположил, что все бикубические графы являются гамильтоновыми. Однако Джозеф Хортон привел контрпример на 96 вершинах – граф Хортона. Позже Марк Эллингэм построил еще два контрпримера: графы Эллингхэма — Хортона. Гипотеза Барнетта, до сих пор не решенная комбинация гипотез Тейта и Тютте, утверждает, что каждый бикубический полиэдрический граф является гамильтоновым. Если кубический граф является гамильтоновым, LCF-нотация позволяет компактно его представить. Если кубический граф выбирается равномерно случайно среди всех кубических графов с n вершинами, то он с большой вероятностью будет гамильтоновым: доля кубических графов с n вершинами, являющихся гамильтоновыми, стремится к единице при n, стремящемся к бесконечности. Дэвид Эппштейн предположил, что каждый кубический граф с n вершинами имеет не более 2n/3 (приблизительно 1,260n) различных гамильтоновых циклов и привел примеры кубических графов с таким количеством циклов. Лучшая доказанная оценка для числа различных гамильтоновых циклов – .
Другие свойства
Ширина пути любого кубического графа с n вершинами не превышает n/6. Наилучшая известная нижняя оценка ширины пути кубических графов равна 0,082n. Неизвестно, как сократить этот разрыв между нижней оценкой и верхней границей n/6. Из леммы о связях, доказанной Леонардом Эйлером в 1736 году в первой работе по теории графов, следует, что любой кубический граф имеет четное число вершин. Теорема Петерсена утверждает, что любой кубический связный граф без мостов имеет совершенное паросочетание. Ловас и Пламмер предположили, что любой кубический связный граф без мостов имеет экспоненциальное количество совершенных паросочетаний. Недавно это предположение было доказано, и показано, что любой кубический связный граф без мостов с n вершинами имеет не менее 2n/3656 совершенных паросочетаний.
Алгоритмы и сложность
Несколько исследователей изучали сложность алгоритмов экспоненциального времени, ограниченных кубическими графами. Например, применяя динамическое программирование к разложению по путям графа, Фомин и Хёйе показали, как находить их максимальные независимые множества за время 2ⁿ/6 + o(n). Ряд важных задач оптимизации графов являются APX-трудными, что означает, что, хотя для них существуют алгоритмы приближения с коэффициентом приближения, ограниченным константой, не существует полиномиальных схем приближения, коэффициент приближения которых стремится к 1, если только P≠NP. К ним относятся задачи нахождения минимального вершинного покрытия, максимального независимого множества, минимального доминирующего множества и максимального разреза. Число пересечений (минимальное количество рёбер, пересекающихся на любом изображении графа) кубического графа также является NP-трудной задачей для кубических графов, но может быть приближено. Доказано, что задачу коммивояжёра на кубических графах NP-трудно приблизить с точностью до любого коэффициента, меньшего чем 1153/1152.