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

У теорії графів товщина графа G це найменша кількість плоских підграфів на які можна розкласти ребра графа G Тобто якщо

Товщина графа

Товщина графа

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

Таким чином, плоский граф має товщину 1. Графи з товщиною 2 називають двопланарними графами. Концепція товщини виникла в гіпотезі Френка Харарі 1962 року: будь-який граф з 9 вершинами або сам, або його доповнення, є непланарним. Задача еквівалентна визначенню, чи є повний граф K9 біпланарним (він не біпланарний, так що гіпотеза істинна). Всебічний огляд з теми товщини графа (станом на 1998 рік) написали Мутцель, Оденталь і Шарбродт.

Конкретні графи

Товщина повного графа з n вершинами, Kn, дорівнює

image

за винятком випадків n = 9, 10, для яких товщина дорівнює трьом.

За винятком кількох випадків, товщина повного двочасткового графа Ka,b дорівнює

image

Пов'язані задачі

Будь-який ліс є планарним, а будь-який планарний граф можна розкласти на три ліси або менше. Отже, товщина будь-якого графа G не більша від деревності того ж графа (найменшої кількості лісів, на які граф можна розкласти) і не менша від деревності, поділеної на 3. Товщина графа G пов'язана з іншим стандартним інваріантом, виродженістю, що визначається як максимум за всіма підграфами графа G найменшого степеня підграфа. Якщо граф з n вершинами має товщину t то число його ребер не перевищує t(3n − 6), звідки випливає, що виродженість не перевищує 6t − 1. З іншого боку, якщо виродженість графа дорівнює D, його деревність і товщина не перевищують D.

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

Інший інваріант графів — прямолінійна товщина або геометрична товщина графа G, підраховує найменшу кількість планарних графів, на які можна розкласти G з обмеженням, що їх можна намалювати одночасно за допомогою відрізків. Книжкова товщина (або товщина книги) додає обмеження, що всі вершини мають лежати на згині (корінці книги), формуючи колову схему графа. Однак, на відміну від деревності та виродженості, між цими величинами немає прямого зв'язку.

Обчислювальна складність

Обчислення товщини заданого графа є NP-складною, а перевірка, що товщина не перевищує двох, є NP-повною задачею. Однак, зв'язок із деревністю дозволяє апроксимувати товщину з апроксимаційним коефіцієнтом 3 за поліноміальний час.

Примітки

  1. Tutte, 1963, с. 567—577.
  2. Mutzel, Odenthal, Scharbrodt, 1998, с. 59—73.
  3. Christian, 2009.
  4. Алексеев, Гончаков, 1976, с. 212.
  5. Mäkinen, Poranen, 2012, с. 76—87.
  6. Petra Mutzel, Thomas Odenthal and Mark Scharbrodt, The Thickness of Graphs: A Survey
  7. Mutzel, Odenthal, Scharbrodt, 1998.
  8. Алексеев, Гончаков, 1976, с. 212—230.
  9. Beineke, Harary, Moon, 1964, с. 1—5.
  10. Dean, Hutchinson, Scheinerman, 1991, с. 147—151.
  11. Brass и др., 2007, с. 117—130.
  12. Eppstein, 2004, с. 75—86.
  13. Mansfield, 1983, с. 9—23.

Література

  • David Eppstein. Towards a theory of geometric graphs. — Amer. Math. Soc., Providence, RI, 2004. — Т. 342. — (Contemp. Math) — DOI:10.1090/conm/342/06132.
  • Anthony Mansfield. Determining the thickness of graphs is NP-hard // Mathematical Proceedings of the Cambridge Philosophical Society. — 1983. — Т. 93, вип. 1. — DOI:10.1017/S030500410006028X.
  • W. T. Tutte. The thickness of a graph. — Indag. Math. — 1963. — Т. 25.
  • Petra Mutzel, Thomas Odenthal, Mark Scharbrodt. The thickness of graphs: a survey // Graphs and Combinatorics. — 1998. — Т. 14, вип. 1. — DOI:10.1007/PL00007219.
  • Christian A. Duncan. On Graph Thickness, Geometric Thickness, and Separator Theorems // CCCG. — Vancouver, BC, 2009. — August.
  • Erkki Mäkinen, Timo Poranen. An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph // Missouri J. Math. Sci. — 2012. — Т. 24, вип. 1 (17 червня).
  • В. Б. Алексеев, В. С. Гончаков. Толщина произвольного полного графа // . — 1976. — Т. 101(143), вип. 2(10).
  • Peter Brass, Eowyn Cenek, Cristian A. Duncan, Alon Efrat, Cesim Erten, Dan P. Ismailescu, Stephen G. Kobourov, Anna Lubiw, Joseph S. B. Mitchell. On simultaneous planar graph embeddings // Computational Geometry. — 2007. — Т. 36, вип. 2. — DOI:10.1016/j.comgeo.2006.05.006.
  • Alice M. Dean, Joan P. Hutchinson, Edward R. Scheinerman. On the thickness and arboricity of a graph // . — 1991. — Т. 52, вип. 1. — (Series B). — DOI:10.1016/0095-8956(91)90100-X.
  • Lowell W. Beineke, Frank Harary, John W. Moon. On the thickness of the complete bipartite graph // Proc. Cambridge Philos. Soc. — 1964. — Т. 60. — DOI:10.1017/s0305004100037385.

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

U teoriyi grafiv tovshina grafa G ce najmensha kilkist ploskih pidgrafiv na yaki mozhna rozklasti rebra grafa G Tobto yaksho isnuye nabir k ploskih grafiv yaki mayut odnakovij nabir vershin poyednannya yakih daye graf G to tovshina grafa G ne bilshe k Takim chinom ploskij graf maye tovshinu 1 Grafi z tovshinoyu 2 nazivayut dvoplanarnimi grafami Koncepciya tovshini vinikla v gipotezi Frenka Harari 1962 roku bud yakij graf z 9 vershinami abo sam abo jogo dopovnennya ye neplanarnim Zadacha ekvivalentna viznachennyu chi ye povnij graf K9 biplanarnim vin ne biplanarnij tak sho gipoteza istinna Vsebichnij oglyad z temi tovshini grafa stanom na 1998 rik napisali Mutcel Odental i Sharbrodt Konkretni grafiTovshina povnogo grafa z n vershinami Kn dorivnyuye n 7 6 displaystyle left lfloor frac n 7 6 right rfloor za vinyatkom vipadkiv n 9 10 dlya yakih tovshina dorivnyuye trom Za vinyatkom kilkoh vipadkiv tovshina povnogo dvochastkovogo grafa Ka b dorivnyuye a b 2 a b 2 displaystyle left lceil frac ab 2 a b 2 right rceil Pov yazani zadachiBud yakij lis ye planarnim a bud yakij planarnij graf mozhna rozklasti na tri lisi abo menshe Otzhe tovshina bud yakogo grafa G ne bilsha vid derevnosti togo zh grafa najmenshoyi kilkosti lisiv na yaki graf mozhna rozklasti i ne mensha vid derevnosti podilenoyi na 3 Tovshina grafa G pov yazana z inshim standartnim invariantom virodzhenistyu sho viznachayetsya yak maksimum za vsima pidgrafami grafa G najmenshogo stepenya pidgrafa Yaksho graf z n vershinami maye tovshinu t to chislo jogo reber ne perevishuye t 3n 6 zvidki viplivaye sho virodzhenist ne perevishuye 6t 1 Z inshogo boku yaksho virodzhenist grafa dorivnyuye D jogo derevnist i tovshina ne perevishuyut D Tovshina tisno pov yazana iz zadacheyu odnochasnogo vkladennya Yaksho dva abo bilshe planarnih grafiv mayut toj samij nabir vershin to ye mozhlivist vklasti vsi ci grafi v ploshinu z podannyam reber u viglyadi krivih tak sho vsi vershini budut mati tu samu poziciyu u vsih malyunkah Odnak mozhe viyavitisya sho pobudova takih malyunkiv nemozhliva yaksho vikoristovuvati vidrizki pryamih Inshij invariant grafiv pryamolinijna tovshina abo geometrichna tovshina grafa G pidrahovuye najmenshu kilkist planarnih grafiv na yaki mozhna rozklasti G z obmezhennyam sho yih mozhna namalyuvati odnochasno za dopomogoyu vidrizkiv Knizhkova tovshina abo tovshina knigi dodaye obmezhennya sho vsi vershini mayut lezhati na zgini korinci knigi formuyuchi kolovu shemu grafa Odnak na vidminu vid derevnosti ta virodzhenosti mizh cimi velichinami nemaye pryamogo zv yazku Obchislyuvalna skladnistObchislennya tovshini zadanogo grafa ye NP skladnoyu a perevirka sho tovshina ne perevishuye dvoh ye NP povnoyu zadacheyu Odnak zv yazok iz derevnistyu dozvolyaye aproksimuvati tovshinu z aproksimacijnim koeficiyentom 3 za polinomialnij chas PrimitkiTutte 1963 s 567 577 Mutzel Odenthal Scharbrodt 1998 s 59 73 Christian 2009 Alekseev Gonchakov 1976 s 212 Makinen Poranen 2012 s 76 87 Petra Mutzel Thomas Odenthal and Mark Scharbrodt The Thickness of Graphs A Survey Mutzel Odenthal Scharbrodt 1998 Alekseev Gonchakov 1976 s 212 230 Beineke Harary Moon 1964 s 1 5 Dean Hutchinson Scheinerman 1991 s 147 151 Brass i dr 2007 s 117 130 Eppstein 2004 s 75 86 Mansfield 1983 s 9 23 LiteraturaDavid Eppstein Towards a theory of geometric graphs Amer Math Soc Providence RI 2004 T 342 Contemp Math DOI 10 1090 conm 342 06132 Anthony Mansfield Determining the thickness of graphs is NP hard Mathematical Proceedings of the Cambridge Philosophical Society 1983 T 93 vip 1 DOI 10 1017 S030500410006028X W T Tutte The thickness of a graph Indag Math 1963 T 25 Petra Mutzel Thomas Odenthal Mark Scharbrodt The thickness of graphs a survey Graphs and Combinatorics 1998 T 14 vip 1 DOI 10 1007 PL00007219 Christian A Duncan On Graph Thickness Geometric Thickness and Separator Theorems CCCG Vancouver BC 2009 August Erkki Makinen Timo Poranen An Annotated Bibliography on the Thickness Outerthickness and Arboricity of a Graph Missouri J Math Sci 2012 T 24 vip 1 17 chervnya V B Alekseev V S Gonchakov Tolshina proizvolnogo polnogo grafa 1976 T 101 143 vip 2 10 Peter Brass Eowyn Cenek Cristian A Duncan Alon Efrat Cesim Erten Dan P Ismailescu Stephen G Kobourov Anna Lubiw Joseph S B Mitchell On simultaneous planar graph embeddings Computational Geometry 2007 T 36 vip 2 DOI 10 1016 j comgeo 2006 05 006 Alice M Dean Joan P Hutchinson Edward R Scheinerman On the thickness and arboricity of a graph 1991 T 52 vip 1 Series B DOI 10 1016 0095 8956 91 90100 X Lowell W Beineke Frank Harary John W Moon On the thickness of the complete bipartite graph Proc Cambridge Philos Soc 1964 T 60 DOI 10 1017 s0305004100037385

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