Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

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

Кубічний граф
Не плутати із графіком кубічної функції

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

image
Граф Петерсена — кубічний граф
image
Повний двочастковий граф є прикладом бікубічного графа

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

Симетрія

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

Примітки

  1. R. M. Foster. Geometrical Circuits of Electrical Networks // . — 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 // [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 // . — 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 // . — 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) // . — 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 // . — 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) — . — 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 // . — 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. . Архів оригіналу за 23 жовтня 2011. Процитовано 28 листопада 2014.
  • Weisstein, Eric W. Bicubic Graph(англ.) на сайті Wolfram MathWorld.
  • Weisstein, Eric W. Cubic Graph(англ.) на сайті Wolfram MathWorld.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Ne plutati iz grafikom kubichnoyi funkciyi Kubi chnij graf v teoriyi grafiv ce graf vsi vershini yakogo mayut stepin tri Inakshe kazhuchi kubichnij graf ce 3 regulyarnij graf Kubichni grafi takozh nazivayut trivale ntnimi gra fami Graf Petersena kubichnij grafPovnij dvochastkovij graf K3 3 displaystyle K 3 3 ye prikladom bikubichnogo grafa Bikubi chnij graf kubichnij dvochastkovij graf Simetriya1932 roku Ronald Foster pochav zbirati prikladi kubichnih simetrichnih grafiv sho poklalo pochatok spisku Fostera Bagato vidomih grafiv ye kubichnimi ta simetrichnimi vklyuchayuchi taki grafi yak Voda gaz ta elektrika graf Petersena graf Hivuda graf Mebiusa Kantora graf Pappa graf Dezarga graf Nauru graf Koksetera graf Tatta Koksetera graf Dika graf Fostera i graf Bigsa Smitta Vilyam Tatt klasifikuvav simetrichni kubichni grafi po yih menshomu cilogo nomera s pri yakomu bud yaki dva oriyentovanih shlyahu dovzhini s mozhut buti perevedeni odin v inshij yedinoyu simetriyeyu grafa Vin pokazav sho s ne perevishuye 5 i naviv prikladi grafiv dlya vsih znachen s vid 1 do 5 Napivsimetrichni kubichni grafi vklyuchayut graf Greya najmenshij napivsimetrichnij kubichnij graf graf Lyublyani i 12 klitka Tatta Graf Fruhta ye odnim z dvoh najmenshih kubichnih grafiv bez simetrij vin maye yedinij avtomorfizm totozhnij avtomorfizm Rozfarbovuvannya ta nezalezhni mnozhiniZgidno z teoremoyu Bruksa bud yakij kubichnij graf vidminnij vid povnogo grafa K4 mozhna rozfarbuvati v tri kolori Takim chinom bud yakij kubichnij graf vidminnij vid K4 maye nezalezhnu mnozhinu sho maye ne mensh n 3 vershin de n chislo vershin grafa Zgidno z teoremoyu Vizinga dlya bud yakogo kubichnogo grafa potribno tri abo chotiri kolori dlya rozmalovki reber Hromatichnij indeks v 3 kolori vidomij yak rozfarbuvannya Teta i vono utvoryuye rozbittya reber grafa na tri doskonalih parospoluchennya Za teoremoyu Keniga bud yakij bikubichnij graf maye rozmalovku Teta Kubichni grafi bez mostiv yaki ne mayut rozmalovki Teta vidomi yak snarki Voni vklyuchayut graf Petersena graf Titce snark Blanushi snark Kvitka snark podvijna zirka snark Sekeresha i snark Uotkinsa Isnuye neskinchenne chislo riznih snarkiv Topologiya ta geometriyaKubichni grafi prirodnim chinom vinikayut u bagatoh rozdilah topologiyi zokrema pri vivchenni CW kompleksiv Takozh kubichnimi ye grafi prostih bagatogrannikiv v trivimirnomu prostori takih yak dodekaedr Dovilne vkladennya grafa v dvovimirnu poverhnyu mozhna podati u viglyadi strukturi kubichnogo grafa vidomoyi yak karta koduvannya grafa U cij strukturi kozhna vershina kubichnogo grafa predstavlyayetsya yak prapor vkladennya i yavlyaye soboyu trijku vershina rebro ta gran Tri susidi kozhnogo prapora ce tri prapori yaki mozhna otrimati zminivshi odin z elementiv prapora ta zalishivshi dva inshih Gamiltonovi shlyahi ta cikliBagato robit prisvyacheno gamiltonovim ciklam kubichnih grafiv 1880 roku Piter Tet visloviv gipotezu sho bud yakij kubichnij bagatogrannij graf ye gamiltonovim Ale 1946 roku Vilyam Tatt naviv kontrpriklad gipotezi Teta graf Tatta z 46 vershinami 1971 roku Tatt pripustiv sho vsi bikubichni grafi gamiltonovi Odnak Dzhozef Horton znajshov kontrpriklad z 96 vershinami graf Hortona Piznishe Mark Ellingham pobuduvav dva inshih prikladi en Gipoteza Barneta ne sprostovana i ne dovedena kombinaciya gipotez Teta i Tatta stverdzhuye sho bud bikubichnij graf bagatogrannika ye gamiltonovim Yaksho kubichnij graf gamiltoniv LCF notaciya dozvolyaye predstaviti jogo stislo Yaksho vibrati kubichnij graf vipadkovo z usih kubichnih grafiv z n vershinami z velikoyu jmovirnistyu vin bude gamiltonovim vidnoshennya grafiv z n vershinami yaki ye gamiltonovi do vsih kubichnim grafiv nablizhayetsya do odinici pri n nablizhenim do neskinchennosti Devid Epshtejn visloviv gipotezu sho kubichnij graf z n vershinami maye maksimum 2n 3 sho priblizno 1 260n riznih gamiltonovih cikliv ta predstaviv prikladi grafiv z takim chislom cikliv Najkrasha verhnya dovedena mezha chisla riznih gamiltonovih cikliv dorivnyuye 1 276n Inshi vlastivostiShlyahova shirina bud yakogo kubichnogo grafa z n vershinami ne perevishuye n 6 Odnak najkrasha vidoma nizhnya mezha shlyahovoyi shirini grafa mensha vona dorivnyuye 0 082n Z lemi pro rukostiskannya dovedenoyu Ejlerom v 1736 yak chastini jogo pershoyi roboti z teoriyi grafiv viplivaye sho bud yakij kubichnij graf maye parne chislo vershin Teorema Petersona stverdzhuye sho bud kubichnij graf bez mostiv maye doskonale paruvannya Lovas i Plamer vislovili gipotezu sho bud kubichnij graf bez mostiv maye eksponencialne chislo doskonalih paruvan Gipoteza bula nedavno dovedena A same bulo dovedeno sho bud yakij kubichnij graf z n vershinami maye yak minimum 2n 3656 doskonalih paruvannya Algoritmi ta skladnistDeyaki doslidniki vivchali skladnist eksponencijnih za chasom algoritmiv pri zastosuvanni yih na kubichni grafi Napriklad pri zastosuvanni dinamichnogo programuvannya do rozkladannya grafa na shlyahi Fomin i Hoji Hoie pokazali yak znajti nezalezhni mnozhini za chas O 2n 6 o n Zadachu komivoyazhera mozhna virishiti na kubichnih grafah za chas O 1 251n Deyaki optimizacijni zadachi na grafah ye APX skladnimi sho oznachaye sho hocha dlya nih i isnuyut aproksimacijni algoritmi garantovana efektivnist yakih nablizhayetsya do 1 lishe yaksho P NP Do nih nalezhat zavdannya poshuku minimalnogo vershinnogo pokrittya maksimalno nezalezhnoyi mnozhini minimalnoyi dominivnoyi mnozhini i en Zavdannya poshuku chisla shreshen minimalne chislo reber yaki peretinayutsya v bud yakomu malyunka grafa kubichnogo grafa ye takozh NP vazhkoyu ale zavdannya piddayetsya aproksimaciyi Dovedeno sho zadacha komivoyazhera na kubichnih grafah NP vazhko aproksimuvati dlya bud yakogo koeficiyenta menshogo 1153 1152 Div takozhBidiakis kubPrimitkiR M Foster Geometrical Circuits of Electrical Networks 1932 T 51 vip 2 S 309 317 DOI 10 1109 T AIEE 1932 5056068 Tutte W T On the symmetry of cubic graphs Canad J Math 1959 T 11 S 621 624 DOI 10 4153 CJM 1959 057 2 z dzherela 16 lipnya 2011 Procitovano 28 listopada 2014 R Isaacs Infinite families of nontrivial trivalent graphs which are not Tait colorable American Mathematical Monthly 1975 T 82 vip 3 S 221 239 DOI 10 2307 2319844 C Paul Bonnington Charles H C Little The Foundations of Topological Graph Theory Springer Verlag 1995 J A Bondy U S R Murty Graph Theory with Applications New York North Holland 1976 S 240 Ellingham M N Non Hamiltonian 3 Connected Cubic Partite Graphs Research Report No 28 Dept of Math Univ Melbourne Melbourne 1981 M N Ellingham J D Horton Non Hamiltonian 3 connected cubic bipartite graphs en 1983 T 34 vip 3 S 350 353 Series B DOI 10 1016 0095 8956 83 90046 1 R W Robinson N C Wormald Almost all regular graphs are Hamiltonian Random Structures and Algorithms 1994 T 5 vip 2 S 363 374 DOI 10 1002 rsa 3240050209 David Eppstein The traveling salesman problem for cubic graphs 2007 T 11 vip 1 S 61 81 arXiv cs DS 0302030 z dzherela 24 lyutogo 2021 Procitovano 28 listopada 2014 Gebauer Proc 4th Workshop on Analytic Algorithmics and Combinatorics ANALCO 08 2008 Fedor V Fomin Kjartan Hoie Pathwidth of cubic graphs and exact algorithms 2006 T 97 vip 5 S 191 196 DOI 10 1016 j ipl 2005 10 012 Julius Peter Christian Petersen Die Theorie der regularen Graphs The theory of regular graphs 1891 T 15 vip 15 S 193 220 DOI 10 1007 BF02392606 Louis Esperet Frantisek Kardos Andrew D King Daniel Kral Serguei Norine Exponentially many perfect matchings in cubic graphs 2011 T 227 vip 4 S 1646 1664 DOI 10 1016 j aim 2011 03 015 Kazuo Iwama Takuya Nakashima Computing and Combinatorics Springer Verlag 2007 T 4598 S 108 117 Lecture Notes in Computer Science ISBN 978 3 540 73544 1 DOI 10 1007 978 3 540 73545 8 13 Paola Alimonti Viggo Kann Some APX completeness results for cubic graphs Theoretical Computer Science 2000 T 237 vip 1 2 S 123 134 DOI 10 1016 S0304 3975 98 00158 3 Petr Hlineny Crossing number is hard for cubic graphs 2006 T 96 vip 4 S 455 471 Series B DOI 10 1016 j jctb 2005 09 009 Marek Karpinski Richard Schmied Approximation Hardness of Graphic TSP on Cubic Graphs 2013 arXiv 1304 6800 PosilannyaRoyle Gordon Arhiv originalu za 23 zhovtnya 2011 Procitovano 28 listopada 2014 Weisstein Eric W Bicubic Graph angl na sajti Wolfram MathWorld Weisstein Eric W Cubic Graph angl na sajti Wolfram MathWorld

Дата публікації:
Топ