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

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

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

Бікубічний граф — кубічний дводольний граф.

Симетрія[ред.ред. код]

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

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

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

Розфарбовування та незалежні множини[ред.ред. код]

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

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

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

Топологія та геометрія[ред.ред. код]

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

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

Гамільтонові шляхи та цикли[ред.ред. код]

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

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

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

Інші властивості[ред.ред. код]

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

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

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

Алгоритми та складність[ред.ред. код]

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

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

Примітки[ред.ред. код]

  1. R. M. Foster Geometrical Circuits of Electrical Networks 51 (1932) С. 309–317. — DOI:10.1109/T-AIEE.1932.5056068..
  2. Tutte On the symmetry of cubic graphs 11 (1959) С. 621–624. — DOI:10.4153/CJM-1959-057-2..
  3. R. Isaacs Infinite families of nontrivial trivalent graphs which are not Tait colorable 82 (1975) С. 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 34 (1983) С. 350–353. — DOI:10.1016/0095-8956(83)90046-1.
  8. R. W. Robinson, N. C. Wormald Almost all regular graphs are Hamiltonian 5 (1994) С. 363–374. — DOI:10.1002/rsa.3240050209..
  9. David Eppstein The traveling salesman problem for cubic graphs 11 (2007) С. 61–81. — arXiv:cs.DS/0302030.
  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 97 (2006) С. 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) 15 (1891) С. 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 227 (2011) С. 1646–1664. — DOI:10.1016/j.aim.2011.03.015..
  14. Kazuo Iwama, Takuya Nakashima Computing and Combinatorics. — Springer-Verlag, 2007. — Т. 4598. — С. 108–117. — 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 237 (2000) С. 123–134. — DOI:10.1016/S0304-3975(98)00158-3..
  16. Petr Hliněný Crossing number is hard for cubic graphs 96 (2006) С. 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..

Посилання[ред.ред. код]