Кубический граф

Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

Бикубический граф — это кубический двудольный граф.

В 1932 году Рональд Фостер начал собирать примеры кубических симметричных графов, что положило начало списку Фостера^[1]. Многие хорошо известные графы являются кубическими и симметричными, включая граф, известный как граф ${\displaystyle K_{3,3}}$(из задачи о домиках и колодцах), граф Петерсена, граф Хивуда, граф Мёбиуса — Кантора, граф Паппа, граф Дезарга, граф Науру, граф Коксетера, граф Татта — Коксетера, граф Дика, граф Фостера и граф Биггса — Смита. Татт классифицировал симметричные кубические графы по их меньшему целому числу ${\displaystyle s}$, при котором любые два ориентированных пути длины ${\displaystyle s}$ могут быть переведены один в другой единственной симметрией графа. Он показал, что ${\displaystyle s}$ не превосходит 5 и привёл примеры графов для всех значений ${\displaystyle s}$ от 1 до 5^[2].

Полусимметричные кубические графы включают граф Грея (наименьший полусимметричный кубический граф), граф Любляны и 12-клетка Татта.

Граф Фрухта является одним из двух наименьших кубических графов без симметрий — он обладает единственным автоморфизмом — тождественным автоморфизмом.

Согласно теореме Брукса любой кубический граф, отличный от полного графа ${\displaystyle K_{4}}$, можно раскрасить в три цвета. Таким образом, любой кубический граф, отличный от ${\displaystyle K_{4}}$, имеет независимое множество, имеющее не менее ${\displaystyle n/3}$ вершин, где ${\displaystyle n}$ — число вершин графа.

Согласно теореме Визинга, для любого кубического графа нужно три или четыре цвета для раскраски рёбер. Рёберная раскраска в 3 цвета известна как раскраска Тэта, и она образует разбиение рёбер графа на три совершенных паросочетания. По теорема Кёнига любой бикубический граф имеет раскраску Тэта.

Кубические графы без мостов, не имеющие раскраски Тэта, известны как снарки. Они включают граф Петерсена, граф Титце, снарки Блануши, цветок, двойная звезда, снарк Секереша и снарк Уоткинса. Существует бесконечное число различных снарков^[3].

Кубические графы естественным образом возникают во многих разделах топологии, в частности, при изучении CW-комплексов. Также кубическими являются графы простых многогранников в трёхмерном пространстве, таких, как додекаэдр.

Произвольное вложение графа в двумерную поверхность можно представить в виде структуры кубического графа, известной как карта кодировки графа. В этой структуре каждая вершина кубического графа представляется как флаг вложения, и представляет собой тройку — вершина, ребро и грань. Три соседа каждого флага — это три флага, которые можно получить, изменив один из элементов флага и оставив два других^[4].

Существует много работ, посвящённых гамильтоновым циклам кубических графов. В 1880 году Питер Тэт высказал гипотезу, что любой кубический граф многогранника является гамильтоновым. Но в 1946 году Уильям Татт представил контрпример гипотезе Тэта, граф Татта с 46 вершинами. В 1971 году Татт предположил, что все бикубические графы гамильтоновы. Однако Джозеф Хортон нашёл контрпример с 96 вершинами, граф Хортона^[5]. Позднее Марк Эллингхам^[англ.] построил два других примера — графы Эллингема — Хортона^[6][7]. Гипотеза Барнетта — не опровергнутая и не доказанная комбинация гипотез Тэта и Татта — утверждает, что любой бикубический граф многогранника является гамильтоновым. Если кубический граф гамильтонов, LCF-нотация позволяет представить его кратко^[].

Если выбрать кубический граф случайно из всех кубических графов с n вершинами, с большой вероятностью он будет гамильтоновым — отношение графов с n вершинами, являющихся гамильтоновыми, ко всем кубическим графам стремится к единице при n стремящемся к бесконечности^[8].

Дэвид Эпштейн^[англ.] высказал гипотезу, что кубический граф с n вершинами имеет максимум 2^n/3 (что примерно 1,260ⁿ) различных гамильтоновых циклов и представил примеры графов с таким числом циклов^[9]. Лучшая верхняя доказанная граница числа различных гамильтоновых циклов равна 1,276^n[10].

Путевая ширина графа любого кубического графа с n вершинами не превосходит n/6. Однако лучшая известная нижняя граница путевой ширины графа меньше, она равна 0,082n^[11].

Из леммы о рукопожатиях, доказанной Эйлером в 1736 году, как части его первой работы по теории графов, следует, что любой кубический граф имеет чётное число вершин.

Теорема Петерсена утверждает, что любой кубический граф без мостов имеет совершенное паросочетание^[12]. Ловас и Пламмер^[англ.] высказали гипотезу, что любой кубический граф без мостов имеет экспоненциальное число совершенных паросочетаний. Гипотеза недавно доказана, а именно доказано, что любой кубический граф с n вершинами имеет как минимум 2^n/3656 совершенных паросочетаний^[13].

Некоторые исследователи изучали сложность экспоненциальных по времени алгоритмов при применении их на кубические графы. Например, при применении динамического программирования к разложению графа на пути, Фомин и Хойи (Høie) показали как найти независимые множества за время O(2^{n/6 + o(n)})^[11]. Задачу коммивояжёра можно решить на кубических графах за время O(1,251ⁿ)^[14].

Некоторые оптимизационные задачи на графах являются APX-сложными, что означает, что хотя для них существуют аппроксимационные алгоритмы, гарантированная эффективность которых ограничена константой, для них нет приближенной схемы полиномиального времени, гарантированная эффективность которых стремится к 1, только если не P=NP. К ним принадлежат задачи поиска минимального вершинного покрытия, максимального независимого множества, минимального доминирующего множества и максимального разреза ^[15]. Задача поиска числа скрещиваний (минимальное число рёбер, которые пересекаются в любом рисунке графа) кубического графа является также NP-трудной, но задача поддаётся аппроксимации^[16]. Доказано, что задачу коммивояжёра на кубических графах NP-трудно аппроксимировать для любого коэффициента, меньшего 1153/1152^[17].

• Royle, Gordon Cubic symmetric graphs (The Foster Census)  (неопр.). Архивировано 23 октября 2011 года.
• Weisstein, Eric W. Bicubic Graph (англ.) на сайте Wolfram MathWorld.
• Weisstein, Eric W. Cubic Graph (англ.) на сайте Wolfram MathWorld.