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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Петерсена является кубическим.
Полный двудольный граф K_{3,3} является примером бикубического графа

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

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

Симметрия[править | править вики-текст]

В 1932 году Рональд Фостер[en] начал собирать примеры кубических симметричных графов, что положило начало списку Фостера.[1] Многие хорошо известные графы являются кубическими и симметричными, включая граф, известный как «Вода, газ и электричество», граф Петерсена, граф Хивуда, граф Мёбиуса — Кантора, граф Паппа, граф Дезарга, граф Науру[en], граф Коксетера, граф Татта — Коксетера, Граф Дика, Граф Фостера и Граф Биггса — Смита[en]. Татт[en] классифицировал симметричные кубические графы по их меньшему целому номеру s, при котором любые два ориентированных пути длины s могут быть переведены один в другой единственной симметрией графа. Он показал, что s не превосходит 5, и привёл примеры графов для всех значений s от 1 до 5.[2]

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

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

Раскраска и независимые множества[править | править вики-текст]

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

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

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

Топология и геометрия[править | править вики-текст]

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

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

Гамильтоновы пути и циклы[править | править вики-текст]

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

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

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

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

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

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

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

Алгоритмы и сложность[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

  1. R. M. Foster Geometrical Circuits of Electrical Networks // Transactions of the American Institute of Electrical Engineers. — 1932. — В. 2. — Т. 51. — С. 309–317. — DOI:10.1109/T-AIEE.1932.5056068.
  2. Tutte On the symmetry of cubic graphs // Canad. J. Math. — 1959. — Т. 11. — С. 621–624. — DOI:10.4153/CJM-1959-057-2.
  3. R. Isaacs Infinite families of nontrivial trivalent graphs which are not Tait colorable // American Mathematical Monthly. — 1975. — В. 3. — Т. 82. — С. 221–239. — DOI:10.2307/2319844.
  4. C. Paul Bonnington, Charles H. C. Little The Foundations of Topological Graph Theory. — Springer-Verlag, 1995.
  5. J. A. Bondy, U. S. R. Murty Graph Theory with Applications.. — New York: North Holland, 1976. — С. 240.
  6. Ellingham, M. N. "Non-Hamiltonian 3-Connected Cubic Partite Graphs."Research Report No. 28, Dept. of Math., Univ. Melbourne, Melbourne, 1981.
  7. M. N. Ellingham, J. D. Horton Non-Hamiltonian 3-connected cubic bipartite graphs // Journal of Combinatorial Theory. — 1983. — В. 3. — Т. 34. — С. 350–353. — DOI:10.1016/0095-8956(83)90046-1
  8. R. W. Robinson, N. C. Wormald Almost all regular graphs are Hamiltonian // Random Structures and Algorithms. — 1994. — В. 2. — Т. 5. — С. 363–374. — DOI:10.1002/rsa.3240050209.
  9. David Eppstein The traveling salesman problem for cubic graphs // Journal of Graph Algorithms and Applications. — 2007. — В. 1. — Т. 11. — С. 61–81. — arΧivcs.DS/0302030
  10. Gebauer Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08). — 2008.
  11. 1 2 Fedor V. Fomin, Kjartan Høie Pathwidth of cubic graphs and exact algorithms // Information Processing Letters. — 2006. — В. 5. — Т. 97. — С. 191–196. — DOI:10.1016/j.ipl.2005.10.012.
  12. Julius Peter Christian Petersen Die Theorie der regulären Graphs (The theory of regular graphs) // Acta Mathematica. — 1891. — В. 15. — Т. 15. — С. 193–220. — DOI:10.1007/BF02392606.
  13. Louis Esperet, František Kardoš, Andrew D. King, Daniel Král, Serguei Norine Exponentially many perfect matchings in cubic graphs // Advances in Mathematics. — 2011. — В. 4. — Т. 227. — С. 1646–1664. — DOI:10.1016/j.aim.2011.03.015.
  14. Kazuo Iwama, Takuya Nakashima Computing and Combinatorics. — Springer-Verlag, 2007. — Т. 4598. — С. 108–117. — (Lecture Notes in Computer Science). — ISBN 978-3-540-73544-1. — DOI:10.1007/978-3-540-73545-8_13.
  15. Paola Alimonti, Viggo Kann Some APX-completeness results for cubic graphs // Theoretical Computer Science. — 2000. — В. 1–2. — Т. 237. — С. 123–134. — DOI:10.1016/S0304-3975(98)00158-3.
  16. Petr Hliněný Crossing number is hard for cubic graphs // Journal of Combinatorial Theory. — 2006. — В. 4. — Т. 96. — С. 455–471. — DOI:10.1016/j.jctb.2005.09.009.
  17. Marek Karpinskiб Richard Schmied Approximation Hardness of Graphic TSP on Cubic Graphs. — 2013. — arΧiv1304.6800.

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