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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Якщо вибрати кубічний граф випадково з усіх кубічних графів з n вершинами, з великою ймовірністю він буде гамільтоновим — відношення графів з n вершинами, які є гамільтонові, до всіх кубічним графів наближається до одиниці при 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]

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

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

Деякі оптимізаційні задачі на графах є APX-складними[en], що означає, що хоча для них і існують апроксимаційні алгоритми[en], гарантована ефективність[en] яких обмежена константою, для них немає наближеної схеми поліноміального часу[en], гарантована ефективність яких наближається до 1, лише якщо P=NP. До них належать завдання пошуку мінімального вершинного покриття, максимально незалежної множини, мінімальної домінівної множини і максимального розрізу[en].[15] Завдання пошуку числа схрещувань[en] (мінімальне число ребер, які перетинаються в будь-якому малюнку графа[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. — Т. 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..
  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. — (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.
  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..

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