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

Кажуть що сімейство графів має обме жене розши рення якщо всі його мінори обмеженої глибини є розрідженими графами Багат

Обмежене розширення графа

Обмежене розширення графа

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

Сімейства з цими властивостями мають ефективні алгоритми для задач, у числі яких пошук ізоморфного підграфа і перевірка моделей для теорії першого порядку для графів.

Визначення та еквівалентні описи

Мінор глибини t графа G визначається як граф, утворений із G стягуванням набору підграфів радіуса t, які не мають спільних вершин, і видаленням решти вершин. Сімейство графів має обмежене розширення, якщо існує функція f, така, що для будь-якого мінора глибини t графа зі сімейства відношення числа ребер до числа вершин не перевищує f(t).

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

Поліноміальне розширення та теореми про розбиття

Строгіше поняття — поліноміальне розширення, що означає, що функція f, що використовується для обмеження щільності ребер мінорів обмеженої глибини, поліноміальна . Якщо сімейство графів, що успадковується, задовольняє теоремі про розбиття, яка стверджує, що будь-який граф з n вершинами в сімействі може бути розбитий на дві частини, що містять не більше n /2 вершин, шляхом видалення O (n c) вершин для деякої константи c < 1, це сімейство обов'язково має поліноміальне розширення. Назад — графи з поліноміальним розширенням мають теореми із сублінійним сепаратором .

Класи графів з обмеженим розширенням

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

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

Алгоритмічні застосування

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

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

Примітки

  1. Nešetřil, Ossona de Mendez, 2012, с. 104–107.
  2. Nešetřil, Ossona de Mendez, Wood, 2012, с. 350–373.
  3. Dvořák, Norin, 2015.
  4. Nešetřil, Ossona de Mendez, 2012, с. 319–321, 14.2 Crossing Number.
  5. Grigoriev, Bodlaender, 2007, с. 1–11.
  6. Dujmović, Eppstein, Wood, 2015, с. 371.
  7. Miller, Teng, Thurston, Vavasis, 1997, с. 1–29.
  8. Dujmović, Sidiropoulos, Wood, 2015.
  9. Nešetřil, Ossona de Mendez, 2012, с. 327–328; 14.5 Stack Number.
  10. Nešetřil, Ossona de Mendez, 2012, с. 307.
  11. Nešetřil, Ossona de Mendez, 2012, с. 314–319; 14.1 Random Graphs (Erdős–Rényi Model).
  12. Nešetřil, Ossona de Mendez, 2012, с. 321–327.
  13. Nešetřil, Ossona de Mendez, 2012, с. 400–401; 18.3 The Subgraph Isomorphism Problem and Boolean Queries.
  14. Dvořák, Kráľ, Thomas, 2010, с. 133–142.
  15. Har-Peled, Quanrud, 2015, с. 717–728.

Література

  • Jaroslav Nešetřil, Patrice Ossona de Mendez. 5.5 Classes with Bounded Expansion // Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — С. 104–107. — (Algorithms and Combinatorics) — . — DOI:10.1007/978-3-642-27875-4.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez, David R. Wood. Characterisations and examples of graph classes with bounded expansion // . — 2012. — Т. 33, вип. 3. — С. 350–373. — arXiv:0902.3265. — DOI:10.1016/j.ejc.2011.09.008.
  • Zdeněk Dvořák, Sergey Norin. Strongly sublinear separators and polynomial expansion. — 2015. — arXiv:1504.04821.
  • Alexander Grigoriev, Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge // . — 2007. — Т. 49, вип. 1. — С. 1–11. — DOI:10.1007/s00453-007-0010-x.
  • Jacob Fox, János Pach. A separator theorem for string graphs and its applications // . — 2009. — Т. 19, вип. 3. — С. 371. — DOI:10.1017/s0963548309990459.
  • Gary L. Miller, Shang-Hua Teng, William Thurston, Stephen A. Vavasis. Separators for sphere-packings and nearest neighbor graphs // . — 1997. — Т. 44, вип. 1. — С. 1–29. — DOI:10.1145/256292.256294.
  • Vida Dujmović, David Eppstein, David R. Wood. Genus, treewidth, and local crossing number // Proc. 23rd Int. Symp. Graph Drawing (GD 2015). — 2015.
  • Vida Dujmović, Anastasios Sidiropoulos, David R. Wood. 3-Monotone Expanders. — 2015. — arXiv:1501.05020.
  • Zdeněk Dvořák, Daniel Kráľ, Robin Thomas. Deciding first-order properties for sparse graphs // . — IEEE Computer Soc., Los Alamitos, CA, 2010. — С. 133–142.
  • Sariel Har-Peled, Kent Quanrud. Approximation algorithms for polynomial-expansion and low-density graphs // Algorithms – ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14–16, 2015, Proceedings. — Springer-Verlag, 2015. — Т. 9294. — С. 717–728. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-662-48350-3_60.

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

Kazhut sho simejstvo grafiv maye obme zhene rozshi rennya yaksho vsi jogo minori obmezhenoyi glibini ye rozridzhenimi grafami Bagato prirodnih simejstv rozridzhenih grafiv mayut obmezhene rozshirennya Blizka ale silnisha vlastivist polinomia lne rozshi rennya ekvivalentne isnuvannyu teorem rozbittya dlya cih simejstv Simejstva z cimi vlastivostyami mayut efektivni algoritmi dlya zadach u chisli yakih poshuk izomorfnogo pidgrafa i perevirka modelej dlya teoriyi pershogo poryadku dlya grafiv Viznachennya ta ekvivalentni opisiMinor glibini t grafa G viznachayetsya yak graf utvorenij iz G styaguvannyam naboru pidgrafiv radiusa t yaki ne mayut spilnih vershin i vidalennyam reshti vershin Simejstvo grafiv maye obmezhene rozshirennya yaksho isnuye funkciya f taka sho dlya bud yakogo minora glibini t grafa zi simejstva vidnoshennya chisla reber do chisla vershin ne perevishuye f t Inshe viznachennya klasiv obmezhenogo rozshirennya vsi minori obmezhenoyi glibini mayut hromatichne chislo obmezhene deyakoyu funkciyeyu vid t abo zadane simejstvo maye obmezhene znachennya topologichnogo parametra Takim parametrom ye invariant grafa monotonnij vidnosno operaciyi vzyattya pidgrafa takij sho znachennya parametra mozhe zminyuvatisya tilki kontrolovanim sposobom koli graf dilitsya i z obmezhenosti znachennya parametra viplivaye sho graf maye obmezhenu virodzhenist Polinomialne rozshirennya ta teoremi pro rozbittyaStrogishe ponyattya polinomialne rozshirennya sho oznachaye sho funkciya f sho vikoristovuyetsya dlya obmezhennya shilnosti reber minoriv obmezhenoyi glibini polinomialna Yaksho simejstvo grafiv sho uspadkovuyetsya zadovolnyaye teoremi pro rozbittya yaka stverdzhuye sho bud yakij graf z n vershinami v simejstvi mozhe buti rozbitij na dvi chastini sho mistyat ne bilshe n 2 vershin shlyahom vidalennya O n c vershin dlya deyakoyi konstanti c lt 1 ce simejstvo obov yazkovo maye polinomialne rozshirennya Nazad grafi z polinomialnim rozshirennyam mayut teoremi iz sublinijnim separatorom Klasi grafiv z obmezhenim rozshirennyamOskilki isnuye zv yazok mizh separatorami ta rozshirennyam bud yake zamknute za minorami simejstvo grafiv vklyuchno zi simejstvom planarnih grafiv maye polinomialne rozshirennya Te same stosuyetsya 1 planarnih grafiv i zagalnishe grafiv yaki mozhna vklasti v poverhni obmezhenogo rodu z obmezhenoyu kilkistyu peretiniv na rebro tak samo yak i strunni grafi bez biklik oskilki dlya nih ye teoremi pro separatori shozhi na teoremi dlya planarnih grafiv U evklidovih prostorah vishih rozmirnostej grafi peretiniv sistem kul iz vlastivistyu sho bud yaka tochka prostoru pokrita obmezhenim chislom kul takozh zadovolnyayut teoremam pro rozbittya zvidki viplivaye isnuvannya polinomialnogo rozshirennya Hocha grafi obmezhenoyi knizhkovoyi shirini ne mistyat linijnih separatoriv voni takozh mayut obmezhene rozshirennya Do klasu grafiv z obmezhenim rozshirennyam vhodyat grafi obmezhenogo stepenya vipadkovi grafi obmezhenogo serednogo stepenya v modeli Erdesha Renyi ta grafi z obmezhenim chislom cherg Algoritmichni zastosuvannyaPrimirnik zadachi izomorfizmu pidgrafa v yakij metoyu ye poshuk grafa obmezhenogo rozmiru sho ye pidgrafom bilshogo grafa rozmir yakogo ne obmezhenij mozhna rozv yazati za linijnij chas yaksho bilshij graf nalezhit do simejstva grafiv z obmezhenim rozshirennyam Te zh same stosuyetsya poshuku klik fiksovanogo rozmiru poshuku dominivnih mnozhin fiksovanogo rozmiru abo zagalnishogo vipadku perevirki vlastivostej yaki mozhna viraziti formuloyu obmezhenogo rozmiru v en pershogo poryadku Dlya grafiv iz polinomialnim rozshirennyam isnuyut shemi nablizhennya do polinomialnogo chasu dlya zadachi pro pokrittya mnozhini zadachi pro maksimalnu nezalezhnu mnozhinu zadachi pro dominivnu mnozhinu ta deyakih inshih pov yazanih zadach optimizaciyi PrimitkiNesetril Ossona de Mendez 2012 s 104 107 Nesetril Ossona de Mendez Wood 2012 s 350 373 Dvorak Norin 2015 Nesetril Ossona de Mendez 2012 s 319 321 14 2 Crossing Number Grigoriev Bodlaender 2007 s 1 11 Dujmovic Eppstein Wood 2015 s 371 Miller Teng Thurston Vavasis 1997 s 1 29 Dujmovic Sidiropoulos Wood 2015 Nesetril Ossona de Mendez 2012 s 327 328 14 5 Stack Number Nesetril Ossona de Mendez 2012 s 307 Nesetril Ossona de Mendez 2012 s 314 319 14 1 Random Graphs Erdos Renyi Model Nesetril Ossona de Mendez 2012 s 321 327 Nesetril Ossona de Mendez 2012 s 400 401 18 3 The Subgraph Isomorphism Problem and Boolean Queries Dvorak Kraľ Thomas 2010 s 133 142 Har Peled Quanrud 2015 s 717 728 LiteraturaJaroslav Nesetril Patrice Ossona de Mendez 5 5 Classes with Bounded Expansion Sparsity Graphs Structures and Algorithms Springer 2012 T 28 S 104 107 Algorithms and Combinatorics ISBN 978 3 642 27874 7 DOI 10 1007 978 3 642 27875 4 Jaroslav Nesetril Patrice Ossona de Mendez David R Wood Characterisations and examples of graph classes with bounded expansion 2012 T 33 vip 3 S 350 373 arXiv 0902 3265 DOI 10 1016 j ejc 2011 09 008 Zdenek Dvorak Sergey Norin Strongly sublinear separators and polynomial expansion 2015 arXiv 1504 04821 Alexander Grigoriev Hans L Bodlaender Algorithms for graphs embeddable with few crossings per edge 2007 T 49 vip 1 S 1 11 DOI 10 1007 s00453 007 0010 x Jacob Fox Janos Pach A separator theorem for string graphs and its applications 2009 T 19 vip 3 S 371 DOI 10 1017 s0963548309990459 Gary L Miller Shang Hua Teng William Thurston Stephen A Vavasis Separators for sphere packings and nearest neighbor graphs 1997 T 44 vip 1 S 1 29 DOI 10 1145 256292 256294 Vida Dujmovic David Eppstein David R Wood Genus treewidth and local crossing number Proc 23rd Int Symp Graph Drawing GD 2015 2015 Vida Dujmovic Anastasios Sidiropoulos David R Wood 3 Monotone Expanders 2015 arXiv 1501 05020 Zdenek Dvorak Daniel Kraľ Robin Thomas Deciding first order properties for sparse graphs IEEE Computer Soc Los Alamitos CA 2010 S 133 142 Sariel Har Peled Kent Quanrud Approximation algorithms for polynomial expansion and low density graphs Algorithms ESA 2015 23rd Annual European Symposium Patras Greece September 14 16 2015 Proceedings Springer Verlag 2015 T 9294 S 717 728 Lecture Notes in Computer Science DOI 10 1007 978 3 662 48350 3 60

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