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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф Петерсена — кубічний граф
Повний дводольний граф 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, можна розфарбувати в три кольори. Таким чином, будь-який кубічний граф, відмінний від 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..

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