Перейти до вмісту

Кубічний граф

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

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

Бікубі́чний граф — кубічний двочастковий граф.

Симетрія

[ред. | ред. код]

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

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

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

Розфарбовування та незалежні множини

[ред. | ред. код]

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

Згідно з теоремою Візінга для будь-якого кубічного графа потрібно три або чотири кольори для розмальовки ребер. Хроматичний індекс в 3 кольори відомий як розфарбування Тета, і воно утворює розбиття ребер графа на три досконалих паросполучення. За теоремою Кеніга будь-який бікубічний граф має розмальовку Тета.

Кубічні графи без мостів, які не мають розмальовки Тета, відомі як снарки. Вони включають граф Петерсена, граф Тітце, снарк Блануші, снарк «Квітка», снарк подвійна зірка, снарк Секереша і снарк Уоткінса. Існує нескінченне число різних снарків.[3]

Топологія та геометрія

[ред. | ред. код]

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

Довільне вкладення графа в двовимірну поверхню можна подати у вигляді структури кубічного графа, відомої як карта кодування графа. У цій структурі кожна вершина кубічного графа представляється як прапор вкладення, і являє собою трійку — вершина, ребро та грань. Три сусіди кожного прапора — це три прапори, які можна отримати, змінивши один з елементів прапора та залишивши два інших[4].

Гамільтонові шляхи та цикли

[ред. | ред. код]

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

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

Девід Епштейн висловив гіпотезу, що кубічний граф з n вершинами має максимум 2n/3 (що приблизно 1,260n) різних гамільтонових циклів та представив приклади графів з таким числом циклів[9]. Найкраща верхня доведена межа числа різних гамільтонових циклів дорівнює 1,276n[10].

Інші властивості

[ред. | ред. код]

Шляхова ширина будь-якого кубічного графа з n вершинами не перевищує n/6. Однак, найкраща відома нижня межа шляхової ширини графа менша, вона дорівнює 0.082n.[11]

З леми про рукостискання, доведеною Ейлером в 1736, як частини його першої роботи з теорії графів, випливає, що будь який кубічний граф має парне число вершин.

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

Алгоритми та складність

[ред. | ред. код]

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

Деякі оптимізаційні задачі на графах є APX-складними, що означає, що хоча для них і існують апроксимаційні алгоритми, гарантована ефективність яких наближається до 1, лише якщо P=NP. До них належать завдання пошуку мінімального вершинного покриття, максимально незалежної множини, мінімальної домінівної множини і максимального розрізу[en].[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 W. T. On the symmetry of cubic graphs // Canad. J. Math. — 1959. — Т. 11. — С. 621–624. — DOI:10.4153/CJM-1959-057-2. Архівовано з джерела 16 липня 2011. Процитовано 28 листопада 2014..
  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..
  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[en]. — 1983. — Т. 34, вип. 3. — С. 350–353. — (Series B). — 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. Архівовано з джерела 24 лютого 2021. Процитовано 28 листопада 2014.
  10. ↑ Gebauer. Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08). — 2008.
  11. ↑ а б 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. — (Series B). — 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..

Посилання

[ред. | ред. код]
  • Royle, Gordon. Cubic symmetric graphs (The Foster Census). Архів оригіналу за 23 жовтня 2011. Процитовано 28 листопада 2014.
  • Weisstein, Eric W. Bicubic Graph(англ.) на сайті Wolfram MathWorld.
  • Weisstein, Eric W. Cubic Graph(англ.) на сайті Wolfram MathWorld.
Отримано з https://uk.wikipedia.org/w/index.php?title=Кубічний_граф&oldid=42730427