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

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

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

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

Симметрия[править | править код]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. ↑ R. M. Foster. Geometrical Circuits of Electrical Networks // Transactions of the American Institute of Electrical Engineers. — 1932. — Т. 51, вып. 2. — С. 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. — Т. 82, вып. 3. — С. 221—239. — doi:10.2307/2319844. — JSTOR 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. — Т. 34, вып. 3. — С. 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. — Т. 5, вып. 2. — С. 363—374. — doi:10.1002/rsa.3240050209.
  9. ↑ David Eppstein. The traveling salesman problem for cubic graphs // Journal of Graph Algorithms and Applications. — 2007. — Т. 11, вып. 1. — С. 61—81. — arXiv:cs.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. — Т. 97, вып. 5. — С. 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. — Т. 227, вып. 4. — С. 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. — Т. 237, вып. 1—2. — С. 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. — Т. 96, вып. 4. — С. 455—471. — doi:10.1016/j.jctb.2005.09.009.
  17. ↑ Marek Karpinskiб Richard Schmied. Approximation Hardness of Graphic TSP on Cubic Graphs. — 2013. — arXiv:1304.6800.

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Кубический_граф&oldid=131269076