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 з виділеним коренем зі властивістю, що будь-які дві суміжні вершини в графі G пов'язані відношенням предок/нащадок. Всі дерева пошуку в глибину і всі гамільтонові шляхи є деревами Тремо. Дерева Тремо названо на честь Чарльза П'єра Тремо, французького автора XIX століття, який використовував варіант пошуку в глибину як стратегію . Дерева Тремо також називають норма́льними кістяко́вими дере́вами, особливо в контексті нескінченних графів.

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

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

Приклад

У графі, показаному нижче, дерево з ребрами 1-3, 2-3 і 3-4 є деревом Тремо, якщо його коренем призначити вершину 1 або вершину 2 — будь-яке ребро графа належить дереву, за винятком ребра 1-2, яке (при виборі зазначеного кореня) з'єднує пару предок-нащадок.

image

Однак, якщо вибрати за корінь для того ж дерева вершину 3 або вершину 4, отримаємо кореневе дерево, яке не є деревом Тремо, оскільки з цими коренями вершини 1 і 2 вже не будуть предком/нащадком.

У скінченних графах

Існування

Будь-який скінченний зв'язний неорієнтований граф має щонайменше одне дерево Тремо. Можна побудувати таке дерево за допомогою пошуку в глибину і з'єднання кожної вершини (відмінної від початкової вершини пошуку) з ранішою вершиною, з якої отримано доступ до поточної вершини. Дерево, побудоване так, відоме як дерево пошуку в глибину. Якщо uv є довільним ребром у графі і u є ранішою з двох вершин, досягнутих під час пошуку, тоді v повинна належати піддереву нащадків u в дереві пошуку в глибину, оскільки пошук обов'язково виявить вершину v, переглядаючи це дерево або з однієї з вершин піддерева, або безпосередньо з вершини u. Будь-яке скінченне дерево Тремо можна утворити як дерево пошуку в глибину — якщо T є деревом Тремо скінченного графа і пошук у глибину досліджує нащадків T кожної вершини перед розглядом будь-якої іншої вершини, це обов'язково генерує T як дерево пошуку в глибину графа.

Паралельна побудова

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

Логічний вираз

Можна виразити властивість, що множина T ребер з вибраною кореневою вершиною r утворює дерево Тремо, в одномісній [en] другого порядку, і такий вираз називають MSO2. Цю властивість можна виразити як поєднання таких властивостей:

  • Граф пов'язаний ребрами з T. Це можна виразити логічно як твердження, що для будь-якої непорожньої власної підмножини вершин графа існує ребро в T, що має рівно одну кінцеву точку в цій підмножині.
  • T ациклічна. Це можна виразити логічно як твердження, що не існує непорожньої підмножини C множини T, для якої кожна вершина має або нуль, або два ребра з C.
  • Будь-яке ребро e, що не належить T, з'єднує пару предок/нащадок вершин у T. Це істинне, коли обидва кінці ребра e належать шляху в T. Це можна висловити логічно як твердження, що для всіх ребер e існує підмножина P множини T, така, що рівно дві вершини, одна з яких r, інцидентні одному ребру в P, і обидва кінці дуги e інцидентні принаймні одному ребру в P.

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

Пов'язані властивості

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

Дерева Тремо тісно пов'язані з концепцією (деревної глибини). Деревну глибину графа G можна визначити як найменше число d, таке, що G можна вкласти у вигляді підграфа графа H, який має дерево Тремо T глибини d. Обмежена глибина дерева в сімействі графів еквівалентна існуванню шляху, який не може з'явитися як (мінор) графа в сімействі. Багато складних обчислювальних задач на графах мають [en] алгоритми, якщо параметризувати деревною глибиною.

Дерева Тремо відіграють також ключову роль у [en] для перевірки, чи є граф планарним. За цим критерієм граф G планарний, якщо для будь-якого дерева Тремо T графа G решту ребер можна розташувати ліворуч і праворуч від дерева, що запобігає перетину ребер (з цієї причини іноді застосовують назву «ЛП алгоритм» з абревіатурою Лівий/Правий).

У нескінченних графах

Існування

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

Навіть у зліченних графах пошук у глибину може виявитися неуспішним при перегляді всього графа, і не будь-яке нормальне кістякове дерево можна утворити пошуком у глибину — щоб бути деревом пошуку в глибину, зліченне нормальне кістякове дерево повинне мати тільки один нескінченний шлях або один вузол з нескінченним числом сусідів (але не обидва випадки одночасно).

Мінор

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

Деталі цього опису залежать від вибору аксіоматики теорії множин, використовуваноїув формалізації математики. Зокрема, в моделях теорії множин, у яких істинна (аксіома Мартіна), а континуум-гіпотеза хибна, клас двочастинних графів можна замінити одним забороненим мінором. Однак для моделей, у яких континуум-гіпотеза істинна, цей клас містить графи, які непорівнянні в упорядкуванні мінорів.

Промені і метризованість

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

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

Примітки

  1. Even, 2011, с. 46–48.
  2. Sedgewick, 2002, с. 149–157.
  3. Soukup, 2008, с. 193 Theorem 3.
  4. Reif, 1985, с. 229–234.
  5. Aggarwal, Anderson, 1988, с. 1–12.
  6. Karger, Motwani, 1997, с. 255–272.
  7. Courcelle, 1996, с. 33–62.
  8. Chartrand, Kronk, 1968, с. 696–700.
  9. Nešetřil, Ossona de Mendez, 2012, с. 115–144.
  10. de Fraysseix, Rosenstiehl, 1982, с. 75–80.
  11. de Fraysseix, Ossona de Mendez, Rosenstiehl, 2006, с. 1017–1029.
  12. Diestel, Leader, 2001, с. 16–32.
  13. Bowler, Geschke, Pitz, 2016.
  14. Diestel, 2006, с. 846–854.

Література

  • Shimon Even. [1] — 2nd. — Cambridge University Press, 2011. — С. 46–48. — . з джерела 23 лютого 2017
  • Robert Sedgewick. [2] — 3rd. — Pearson Education, 2002. — С. 149–157. — . з джерела 11 березня 2022
    • Роберт Седжвик. Часть 5. Алгоритмы на графах // Фундаментальные алгоритмы на C. — Москва, Санкт-Петербург, Киев : DiaSoft, 2003. — .
  • John H.Reif. Depth-first search is inherently sequential. — . — 1985. — Т. 20. — С. 229–234. — DOI:10.1016/0020-0190(85)90024-9.
  • Aggarwal A., Anderson R. J. A random NC algorithm for depth first search // . — 1988. — Т. 8, вип. 1 (28 червня). — С. 1–12. — DOI:10.1007/BF02122548.
  • David R. Karger, Rajeev Motwani. An NC algorithm for minimum cuts. — . — 1997. — Т. 26. — С. 255–272. — DOI:10.1137/S0097539794273083.
  • Bruno Courcelle. On the expression of graph properties in some fragments of monadic second-order logic // [3] / Neil Immerman, Phokion G. Kolaitis. — Amer. Math. Soc, 1996. — Т. 31. — С. 33–62. — (DIMACS) з джерела 21 вересня 2017
  • Gary Chartrand, Hudson V. Kronk. Randomly traceable graphs // (SIAM Journal on Applied Mathematics). — 1968. — Т. 16 (28 червня). — С. 696–700.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Chapter 6. Bounded height trees and tree-depth // Sparsity: Graphs, Structures, and Algorithms. — Heidelberg : Springer, 2012. — Т. 28. — С. 115–144. — (Algorithms and Combinatorics) — . — DOI:10.1007/978-3-642-27875-4.
  • Hubert de Fraysseix, Pierre Rosenstiehl. A depth-first-search characterization of planarity // Graph theory (Cambridge, 1981). — Amsterdam : North-Holland, 1982. — Т. 13. — С. 75–80. — (Ann. Discrete Math.)
  • Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl. Trémaux trees and planarity // International Journal of Foundations of Computer Science. — 2006. — Т. 17, вип. 5 (28 червня). — С. 1017–1029. — DOI:10.1142/S0129054106004248.
  • Lajos Soukup. Infinite combinatorics: from finite to infinite // [4] — Berlin : Springer, 2008. — Т. 17. — С. 189–213. — (Bolyai Soc. Math. Stud.) — . — DOI:10.1007/978-3-540-77200-2_10. з джерела 11 березня 2022
  • Reinhard Diestel, Imre Leader. Normal spanning trees, Aronszajn trees and excluded minors // Journal of the London Mathematical Society. — 2001. — Т. 63, вип. 1 (28 червня). — С. 16–32. — (Second Series). — DOI:10.1112/S0024610700001708. з джерела 10 червня 2007. Процитовано 11 березня 2022.
  • Nathan Bowler, Stefan Geschke, Max Pitz. Minimal obstructions for normal spanning trees. — 2016. — 28 червня. — arXiv:1609.01042.
  • Reinhard Diestel. End spaces and spanning trees // . — 2006. — Т. 96, вип. 6 (28 червня). — С. 846–854. — (Series B). — DOI:10.1016/j.jctb.2006.02.010.

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

Дата публікації:
De revo Tremo neoriyentovanogo grafa G ce kistyakove derevo grafa G z vidilenim korenem zi vlastivistyu sho bud yaki dvi sumizhni vershini v grafi G pov yazani vidnoshennyam predok nashadok Vsi dereva poshuku v glibinu i vsi gamiltonovi shlyahi ye derevami Tremo Dereva Tremo nazvano na chest Charlza P yera Tremo francuzkogo avtora XIX stolittya yakij vikoristovuvav variant poshuku v glibinu yak strategiyu vihodu z labirinta Dereva Tremo takozh nazivayut norma lnimi kistyako vimi dere vami osoblivo v konteksti neskinchennih grafiv U skinchennih grafah hocha poshuk u glibinu sam po sobi spochatku poslidovnij dereva Tremo mozhna pobuduvati randomizovanim paralelnim algoritmom iz klasom skladnosti RNC Dereva Tremo mozhna vikoristovuvati dlya viznachennya derevnoyi glibini grafa i yak chastinu en dlya perevirki chi ye graf planarnim Opis derev Tremo odnomisnoyu en drugogo poryadku dozvolyaye efektivno rozpiznati vlastivosti grafa zalezhni vid oriyentaciyi dlya grafiv z obmezhenoyu derevnoyu shirinoyu za vikoristannya teoremi Kurselya Ne kozhen neskinchennij graf maye derevo Tremo i grafi yaki takogo dereva ne mayut mozhna opisati zaboronenimi minorami Derevo Tremo isnuye v bud yakomu grafi zi zlichennim chislom vershin navit yaksho variant neskinchennogo poshuku v glibinu ne mozhe uspishno pereviriti vsih vershin grafa U neskinchennomu grafi derevo Tremo povinne mati rivno odin neskinchennij shlyah dlya kozhnogo kincya grafa i isnuvannya dereva Tremo harakterizuye grafi topologichni popovnennya yakih utvoreni dodannyam neskinchenno viddalenoyi tochki dlya kozhnogo promenya ye metrichnimi prostorami PrikladU grafi pokazanomu nizhche derevo z rebrami 1 3 2 3 i 3 4 ye derevom Tremo yaksho jogo korenem priznachiti vershinu 1 abo vershinu 2 bud yake rebro grafa nalezhit derevu za vinyatkom rebra 1 2 yake pri vibori zaznachenogo korenya z yednuye paru predok nashadok Odnak yaksho vibrati za korin dlya togo zh dereva vershinu 3 abo vershinu 4 otrimayemo koreneve derevo yake ne ye derevom Tremo oskilki z cimi korenyami vershini 1 i 2 vzhe ne budut predkom nashadkom U skinchennih grafahIsnuvannya Bud yakij skinchennij zv yaznij neoriyentovanij graf maye shonajmenshe odne derevo Tremo Mozhna pobuduvati take derevo za dopomogoyu poshuku v glibinu i z yednannya kozhnoyi vershini vidminnoyi vid pochatkovoyi vershini poshuku z ranishoyu vershinoyu z yakoyi otrimano dostup do potochnoyi vershini Derevo pobudovane tak vidome yak derevo poshuku v glibinu Yaksho uv ye dovilnim rebrom u grafi i u ye ranishoyu z dvoh vershin dosyagnutih pid chas poshuku todi v povinna nalezhati pidderevu nashadkiv u v derevi poshuku v glibinu oskilki poshuk obov yazkovo viyavit vershinu v pereglyadayuchi ce derevo abo z odniyeyi z vershin piddereva abo bezposeredno z vershini u Bud yake skinchenne derevo Tremo mozhna utvoriti yak derevo poshuku v glibinu yaksho T ye derevom Tremo skinchennogo grafa i poshuk u glibinu doslidzhuye nashadkiv T kozhnoyi vershini pered rozglyadom bud yakoyi inshoyi vershini ce obov yazkovo generuye T yak derevo poshuku v glibinu grafa Paralelna pobudova Zadacha poshuku dereva Tremo ye en yaksho shukati za dopomogoyu poslidovnogo algoritmu poshuku v glibinu v yakomu susidi kozhnoyi vershini pereglyadayutsya v poryadku yih nomeriv Prote mozhna znajti inshe derevo Tremo skoristavshis randomizovanim paralelnim algoritmom sho pokazuye nalezhnist pobudovi derev Tremo do klasu skladnosti RNC Zalishayetsya nevidomim chi mozhna pobuduvati derevo Tremo determinovanim paralelnim algoritmom sho nalezhit do klasu NC Logichnij viraz Mozhna viraziti vlastivist sho mnozhina T reber z vibranoyu korenevoyu vershinoyu r utvoryuye derevo Tremo v odnomisnij en drugogo poryadku i takij viraz nazivayut MSO2 Cyu vlastivist mozhna viraziti yak poyednannya takih vlastivostej Graf pov yazanij rebrami z T Ce mozhna viraziti logichno yak tverdzhennya sho dlya bud yakoyi neporozhnoyi vlasnoyi pidmnozhini vershin grafa isnuye rebro v T sho maye rivno odnu kincevu tochku v cij pidmnozhini T aciklichna Ce mozhna viraziti logichno yak tverdzhennya sho ne isnuye neporozhnoyi pidmnozhini C mnozhini T dlya yakoyi kozhna vershina maye abo nul abo dva rebra z C Bud yake rebro e sho ne nalezhit T z yednuye paru predok nashadok vershin u T Ce istinne koli obidva kinci rebra e nalezhat shlyahu v T Ce mozhna visloviti logichno yak tverdzhennya sho dlya vsih reber e isnuye pidmnozhina P mnozhini T taka sho rivno dvi vershini odna z yakih r incidentni odnomu rebru v P i obidva kinci dugi e incidentni prinajmni odnomu rebru v P Yak tilki derevo Tremo identifikovano takim sposobom mozhna opisati oriyentaciyu danogo grafa v odnomisnij logici drugogo poryadku vkazavshi mnozhini reber yaki oriyentovani vid predka do nashadka Rebra sho ne nalezhat cij mnozhini mayut buti oriyentovani v zvorotnomu napryamku Cya tehnika dozvolyaye opisati vlastivosti grafa sho vikoristovuyut oriyentaciyu v odnomisnij logici drugogo poryadku sho dozvolyaye pereviriti ci vlastivosti efektivno na grafah iz obmezhenoyu derevnoyu shirinoyu za dopomogoyu teoremi Kurselya Pov yazani vlastivosti Yaksho graf maye gamiltoniv shlyah to cej shlyah z korenem yak odnim z jogo kinciv ye takozh derevom Tremo Mnozhina neoriyentovanih grafiv dlya yakih bud yake derevo Tremo maye takij viglyad skladayetsya z cikliv povnih grafiv i zbalansovanih povnih dvochastinnih grafiv Dereva Tremo tisno pov yazani z koncepciyeyu derevnoyi glibini Derevnu glibinu grafa G mozhna viznachiti yak najmenshe chislo d take sho G mozhna vklasti u viglyadi pidgrafa grafa H yakij maye derevo Tremo T glibini d Obmezhena glibina dereva v simejstvi grafiv ekvivalentna isnuvannyu shlyahu yakij ne mozhe z yavitisya yak minor grafa v simejstvi Bagato skladnih obchislyuvalnih zadach na grafah mayut en algoritmi yaksho parametrizuvati derevnoyu glibinoyu Dereva Tremo vidigrayut takozh klyuchovu rol u en dlya perevirki chi ye graf planarnim Za cim kriteriyem graf G planarnij yaksho dlya bud yakogo dereva Tremo T grafa G reshtu reber mozhna roztashuvati livoruch i pravoruch vid dereva sho zapobigaye peretinu reber z ciyeyi prichini inodi zastosovuyut nazvu LP algoritm z abreviaturoyu Livij Pravij U neskinchennih grafahIsnuvannya Ne bud yakij neskinchennij graf maye normalne kistyakove derevo Napriklad povnij graf na nezlichennij mnozhini vershin ne maye normalnogo kistyakovogo dereva take derevo v povnomu grafi mozhe buti tilki shlyahom ale shlyah maye lishe zlichenne chislo vershin Odnak bud yakij graf na zlichennij mnozhini vershin maye normalne kistyakove derevo Navit u zlichennih grafah poshuk u glibinu mozhe viyavitisya neuspishnim pri pereglyadi vsogo grafa i ne bud yake normalne kistyakove derevo mozhna utvoriti poshukom u glibinu shob buti derevom poshuku v glibinu zlichenne normalne kistyakove derevo povinne mati tilki odin neskinchennij shlyah abo odin vuzol z neskinchennim chislom susidiv ale ne obidva vipadki odnochasno Minor Yaksho neskinchennij graf G maye normalne kistyakove derevo to jogo maye i bud yakij zv yaznij minor grafa G Zvidsi viplivaye sho grafi yaki mayut normalni kistyakovi dereva mozhna opisati zaboronenimi minorami Odin iz dvoh klasiv zaboronenih minoriv skladayetsya z dvochastinnih grafiv u yakih odna chastina zlichenna a insha nezlichenna i bud yaka vershina maye neskinchennij stepin Inshij klas zaboronenih minoriv skladayetsya z pevnih grafiv otrimanih iz en Detali cogo opisu zalezhat vid viboru aksiomatiki teoriyi mnozhin vikoristovuvanoyiuv formalizaciyi matematiki Zokrema v modelyah teoriyi mnozhin u yakih istinna aksioma Martina a kontinuum gipoteza hibna klas dvochastinnih grafiv mozhna zaminiti odnim zaboronenim minorom Odnak dlya modelej u yakih kontinuum gipoteza istinna cej klas mistit grafi yaki neporivnyanni v uporyadkuvanni minoriv Promeni i metrizovanist Normalni kistyakovi dereva tisno pov yazani z kincyami neskinchennogo grafa klasami ekvivalentnosti neskinchennih shlyahiv yaki jdut v odnomu napryamku Yaksho graf maye normalne kistyakove derevo ce derevo povinne mati rivno odin neskinchennij shlyah dlya kozhnogo promenya grafa Neskinchennij graf mozhna vikoristati dlya utvorennya topologichnogo prostoru yaksho rozglyadati graf sam po sobi yak simplicijnij kompleks i dodati neskinchenno viddalenu tochku dlya kozhnogo promenya grafa Z takoyu topologiyeyu graf maye normalne kistyakove derevo todi j lishe todi koli jogo mnozhinu vershin mozhna rozbiti na zlichenne ob yednannya zamknutih mnozhin Krim togo cej topologichnij prostir mozhna podati metrichnim prostorom todi j lish todi koli graf maye normalne kistyakove derevo PrimitkiEven 2011 s 46 48 Sedgewick 2002 s 149 157 Soukup 2008 s 193 Theorem 3 Reif 1985 s 229 234 Aggarwal Anderson 1988 s 1 12 Karger Motwani 1997 s 255 272 Courcelle 1996 s 33 62 Chartrand Kronk 1968 s 696 700 Nesetril Ossona de Mendez 2012 s 115 144 de Fraysseix Rosenstiehl 1982 s 75 80 de Fraysseix Ossona de Mendez Rosenstiehl 2006 s 1017 1029 Diestel Leader 2001 s 16 32 Bowler Geschke Pitz 2016 Diestel 2006 s 846 854 LiteraturaShimon Even 1 2nd Cambridge University Press 2011 S 46 48 ISBN 978 0 521 73653 4 z dzherela 23 lyutogo 2017 Robert Sedgewick 2 3rd Pearson Education 2002 S 149 157 ISBN 978 0 201 36118 6 z dzherela 11 bereznya 2022 Robert Sedzhvik Chast 5 Algoritmy na grafah Fundamentalnye algoritmy na C Moskva Sankt Peterburg Kiev DiaSoft 2003 ISBN 5 93772 083 0 John H Reif Depth first search is inherently sequential 1985 T 20 S 229 234 DOI 10 1016 0020 0190 85 90024 9 Aggarwal A Anderson R J A random NC algorithm for depth first search 1988 T 8 vip 1 28 chervnya S 1 12 DOI 10 1007 BF02122548 David R Karger Rajeev Motwani An NC algorithm for minimum cuts 1997 T 26 S 255 272 DOI 10 1137 S0097539794273083 Bruno Courcelle On the expression of graph properties in some fragments of monadic second order logic 3 Neil Immerman Phokion G Kolaitis Amer Math Soc 1996 T 31 S 33 62 DIMACS z dzherela 21 veresnya 2017 Gary Chartrand Hudson V Kronk Randomly traceable graphs SIAM Journal on Applied Mathematics 1968 T 16 28 chervnya S 696 700 Jaroslav Nesetril Patrice Ossona de Mendez Chapter 6 Bounded height trees and tree depth Sparsity Graphs Structures and Algorithms Heidelberg Springer 2012 T 28 S 115 144 Algorithms and Combinatorics ISBN 978 3 642 27874 7 DOI 10 1007 978 3 642 27875 4 Hubert de Fraysseix Pierre Rosenstiehl A depth first search characterization of planarity Graph theory Cambridge 1981 Amsterdam North Holland 1982 T 13 S 75 80 Ann Discrete Math Hubert de Fraysseix Patrice Ossona de Mendez Pierre Rosenstiehl Tremaux trees and planarity International Journal of Foundations of Computer Science 2006 T 17 vip 5 28 chervnya S 1017 1029 DOI 10 1142 S0129054106004248 Lajos Soukup Infinite combinatorics from finite to infinite 4 Berlin Springer 2008 T 17 S 189 213 Bolyai Soc Math Stud ISBN 978 3 540 77199 9 DOI 10 1007 978 3 540 77200 2 10 z dzherela 11 bereznya 2022 Reinhard Diestel Imre Leader Normal spanning trees Aronszajn trees and excluded minors Journal of the London Mathematical Society 2001 T 63 vip 1 28 chervnya S 16 32 Second Series DOI 10 1112 S0024610700001708 z dzherela 10 chervnya 2007 Procitovano 11 bereznya 2022 Nathan Bowler Stefan Geschke Max Pitz Minimal obstructions for normal spanning trees 2016 28 chervnya arXiv 1609 01042 Reinhard Diestel End spaces and spanning trees 2006 T 96 vip 6 28 chervnya S 846 854 Series B DOI 10 1016 j jctb 2006 02 010
Топ