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, представлена некореневим двійковим деревом T з ребрами з G як листками. Видалення будь-якого ребра з T поділяє ребра графа G на два підграфи, а шириною декомпозиції вважають найбільшу кількість спільних вершин у будь-якому підграфі, отриманому в такий спосіб. Ширина галуження графа G це найменша ширина будь-якої гілкової декомпозиції графа G.

image
Гілкова декомпозиція ґратки. Показано e-поділ. Поділ, декомпозиція і сам граф мають ширину три.

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

Визначення

Некореневе двійкове дерево — це зв'язний неорієнтований граф без циклів, у якому кожен нелистовий вузол має рівно три сусіди. Гілкову декомпозицію можна подати як некореневе двійкове дерево T разом з бієкцією між листками дерева T та ребрами даного графа G = (V, E). Якщо e — будь-яке ребро дерева T, то видалення e з T ділить його на два піддерева T1 і T2. Цей поділ дерева T на піддерева породжує поділ ребер, асоційованих з листками дерева T на два підграфи графа G, G1 і G2. Такий поділ графа G на два підграфи називають e-поділом.

Ширина e-поділу — це число вершин графа G, інцидентних як ребрам з E1, так і ребрам з E2. Тобто це множина вершин, спільних для підграфів G1 і G2. Ширина гілкової декомпозиції — це найбільша ширина будь-якого e-поділу. Ширина галуження графа G — це найменша ширина гілкових декомпозицій графа G.

Зв'язок із деревною шириною

Гілкова декомпозиція графа тісно пов'язана з деревною декомпозицією, а ширина галуження тісно пов'язана з деревною шириною. Дві ці величини відрізняються лише сталим множником. Зокрема, в статті, в якій вони запропонували ширину галуження, [en] і [ru] показали, що для графа G з деревною шириною k і шириною галуження b > 1

image

Ширина нарізки

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

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

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

Задача визначення, чи має граф G гілкову декомпозицію із шириною, що не перевищує k, є NP-повною, якщо G і k є вхідними даними задачі. Однак графи зі шириною галуження не більшою від k, утворюють сімейство графів, замкнене за мінорами, звідки випливає, що обчислення ширини галуження є [en] задачею: існує алгоритм для обчислення оптимальної гілкової декомпозиції, час роботи якого на графах із шириною галуження, що не перевищує k для деякого сталого k, лінійно залежить від розміру графа.

Для планарних графів ширину галуження можна обчислити за лінійний час. Це контрастує із деревною шириною, для якої складність обчислення на планарних графах є добре відомою відкритою проблемою. Початковий алгоритм Пола Сеймура і [en] для обчислення ширини галуження планарних графів розв'язував задачу за час O(n2) на графі з n вершинами, а їхній алгоритм для побудови гілкової декомпозиції працював за час O(n4). Пізніше останній покращено до O(n3).

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

Узагальнення для матроїдів

Поняття гілкової декомпозиції можна також визначити для матроїдів, що узагальнює гілкову декомпозицію графів. Гілкова декомпозиція матроїда є ієрархічною кластеризацією елементів матроїда, подана як некореневе двійкове дерево з елементами матроїда як листками. Для матроїдів e-поділ можна визначити в той самий спосіб, що й для графів, а результатом буде поділ множини M елементів матроїда на дві підмножини A і B. Якщо через ρ позначити (функцію рангу) матроїда, то ширина e-поділу визначається як ρ(A) + ρ(B) − ρ(M) + 1, а ширина декомпозиції та ширина галуження матроїда визначаються аналогічно до визначень для графа. Ширина галуження графа та ширина галуження відповідного [en] відрізняються. Наприклад, шлях із трьох ребер і зірка з трьох ребер мають різні ширини галуження, 2 і 1 відповідно, але графовий матроїд у них однаковий і має ширину галуження 1. Однак для графів, що не є деревами, ширина галуження графа дорівнює ширині галуження пов'язаного графового матроїда. Ширина галуження матроїда дорівнює ширині галуження його [en], і з цього випливає, що ширина галуження будь-якого планарного графа, який не є деревом, дорівнює ширині галуження його двоїстого графа.

Ширина галуження — важлива складова спроб розширити теорію мінорів графа на [en] — хоча деревну ширину можна також узагальнити на матроїди і її роль у теорії графів більша, ніж ширини галуження, ширина галуження має зручніші властивості. Робертсон і Сеймур висловили припущення, що матроїди, подані будь-яким конкретним скінченним полем, [en] , що є аналогією теореми Робертсона — Сеймура для графів, але гіпотезу доведено тільки для матроїдів із обмеженою шириною галуження. Крім того, якщо сімейство матроїдів, замкнене за мінорами і подане скінченним полем, не включає графових матроїдів усіх планарних графів, існує стала, яка обмежує ширину галуження в сімействі, що узагальнює відповідне твердження для сімейств графів, замкнутих за мінорами.

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

Заборонені мінори

image
Чотири заборонені мінори для графів із шириною галуження три.

За теоремою Робертсона — Сеймура графи з шириною галуження k можна схарактеризувати скінченною множиною заборонених мінорів. Графи з шириною галуження 0 — це парування, а найменші заборонені мінори в цьому випадку — це шлях із двох дуг та трикутний граф (а також цикл із двох дуг, якщо розглядаються мультиграфи). Графи з шириною галуження 1 — це графи, в яких кожна компонента зв'язності є зіркою, а найменші заборонені мінори для графів з шириною галуження 1 — це трикутний граф (або цикл із двох дуг, якщо розглядаються мультиграфи) і шляхи з трьох дуг. Графи з шириною галуження 2 — це графи, в яких кожна двозв'язна компонента є паралельно-послідовним графом, а єдиним найменшим забороненим мінором є повний граф K4 з чотирьох вершин. Граф має ширину галуження три тоді й лише тоді, коли його деревна ширина дорівнює трьом і він не має мінором графа гіперкубу. Таким чином, чотири заборонені мінори — це три з чотирьох заборонених мінорів графів з деревною шириною три (граф октаедра, повний граф K5 і граф Вагнера) разом із графом куба.

Заборонені мінори вивчаються також і для ширини галуження матроїда, попри відсутність повної аналогії теореми Робертсона — Сеймура у цьому разі. Матроїд має ширину галуження одиниця тоді й лише тоді, коли будь-який елемент є або петлею, або копетлею, так що єдиним найменшим забороненим мінором є [en] U(2,3), графовий матроїд трикутного графа. Матроїд має ширину галуження два тоді й лише тоді, коли він є графовим матроїдом графа з шириною галуження два, так що мінімальними забороненими мінорами є графові матроїди графа K4 і неграфовий матроїд U(2,4). Матроїди з шириною галуження три не цілком квазівпорядковані без додаткового припущення щодо подання над скінченним полем, але, тим не менш, матроїди з будь-якою обмеженою шириною галуження мають скінченне число найменших заборонених мінорів, які мають число елементів, що залежать від ширини галуження не більш ніж експоненційно.

Примітки

  1. Robertson, Seymour, 1991, с. 168, Theorem 5.1.
  2. Seymour, Thomas, 1994.
  3. Robertson, Seymour, 1991, с. 164, Theorem 4.1.
  4. Bodlaender, Thilikos, (1997). Фомін, Мацойт і Тодінка Fomin, Mazoit, Todinca, (2009) описують алгоритм із покращеною залежністю від k, (2√3)k, але залежність від числа вершин зростає від лінійної до квадратичної.
  5. Kao, Ming-Yang, ред. (2008), Treewidth of graphs, , Springer, с. 969, ISBN , архів оригіналу за 5 червня 2022, процитовано 5 червня 2022, Ще одна давня відкрита проблема: Чи існує алгоритм поліноміального часу обчислення деревної ширини планарного графа?
  6. Gu, Tamaki, 2008.
  7. Hicks, 2000.
  8. Hliněný, 2003.
  9. Cook, Seymour, 2003.
  10. Fomin, Thilikos, 2006.
  11. Robertson, Seymour, 1991, с. 188–190, Section 12, «Tangles and Matroids».
  12. Mazoit, Thomassé, 2007.
  13. Hicks, McMurray, 2007.
  14. Hliněný, Whittle, 2006.
  15. Geelen, Gerards, Whittle, 2006.
  16. Geelen, Gerards, Whittle, 2002.
  17. Geelen, Gerards, Whittle, 2007.
  18. Oum, Seymour, 2007.
  19. Robertson, Seymour, 1991, с. 165, Theorem 4.2.
  20. Bodlaender, Thilikos, (1999). Четвертий заборонений мінор для деревної ширини три, граф п'ятикутної призми, має граф куба як мінор, так що він не є найменшим для ширини галуження три.
  21. Hall, Oxley, Semple, Whittle, 2002.
  22. Geelen, Gerards, Robertson, Whittle, 2003.

Література

  • Hans L. Bodlaender, Dimitrios M. Thilikos. Proc. 24th International Colloquium on Automata, Languages and Programming (ICALP '97). — Springer-Verlag, 1997. — Т. 1256. — С. 627–637. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-63165-8_217.
  • Hans L. Bodlaender, Dimitrios M. Thilikos. Graphs with branchwidth at most three // Journal of Algorithms. — 1999. — Т. 32, вип. 2. — С. 167—194. — DOI:10.1006/jagm.1999.1011.
  • William, . Tour merging via branch-decomposition // INFORMS Journal on Computing. — 2003. — Т. 15, вип. 3. — С. 233—248. — DOI:10.1287/ijoc.15.3.233.16078. з джерела 31 липня 2010. Процитовано 5 червня 2022..
  • Fedor V. Fomin, Dimitrios M. Thilikos. Dominating sets in planar graphs: branch-width and exponential speed-up. — SIAM Journal on Computing. — 2006. — Т. 36. — С. 281. — DOI:10.1137/S0097539702419649.
  • Fedor V. Fomin, Frédéric Mazoit, Ioan Todinca. Computing branchwidth via efficient triangulations and blocks // Discrete Applied Mathematics. — 2009. — Т. 157, вип. 12. — С. 2726—2736. — DOI:10.1016/j.dam.2008.08.009. з джерела 5 червня 2022. Процитовано 5 червня 2022..
  • Jim Geelen, Bert Gerards, [en], Geoff Whittle. On the excluded minors for the matroids of branch-width k // Journal of Combinatorial Theory, Series B. — 2003. — Т. 88, вип. 2. — С. 261—265. — DOI:10.1016/S0095-8956(02)00046-1.
  • Jim Geelen, Bert Gerards, Geoff Whittle. Branch-width and well-quasi-ordering in matroids and graphs // Journal of Combinatorial Theory, Series B. — 2002. — Т. 84, вип. 2. — С. 270—290. — DOI:10.1006/jctb.2001.2082.
  • Jim Geelen, Bert Gerards, Geoff Whittle. Proc. International Congress of Mathematicians. — 2006. — Т. III. — С. 827–842. з джерела 11 серпня 2017
  • Jim Geelen, Bert Gerards, Geoff Whittle. Excluding a planar graph from GF(q)-representable matroids // Journal of Combinatorial Theory, Series B. — 2007. — Т. 97, вип. 6. — С. 971—998. — DOI:10.1016/j.jctb.2007.02.005..
  • Qian-Ping Gu, Hisao Tamaki. Optimal branch-decomposition of planar graphs in O(n3) time // ACM Transactions on Algorithms. — 2008. — Т. 4, вип. 3. — С. 30:1—30:13. — DOI:10.1145/1367064.1367070.
  • Rhiannon Hall, James Oxley, Charles Semple, Geoff Whittle. On matroids of branch-width three // Journal of Combinatorial Theory, Series B. — 2002. — Т. 86, вип. 1. — С. 148—171. — DOI:10.1006/jctb.2002.2120.
  • Illya V. Hicks. Branch Decompositions and their Applications. — Rice University, 2000. — (Ph.D. thesis) з джерела 16 липня 2011
  • Illya V. Hicks, Nolan B. McMurray, Jr. The branchwidth of graphs and their cycle matroids // Journal of Combinatorial Theory, Series B. — 2007. — Т. 97, вип. 5. — С. 681—692. — DOI:10.1016/j.jctb.2006.12.007..
  • Petr Hliněný. Proc. 28th International Symposium on Mathematical Foundations of Computer Science (MFCS '03). — Springer-Verlag, 2003. — Т. 2747. — С. 470–479. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-540-45138-9\_41.
  • Petr Hliněný, Geoff Whittle. Matroid tree-width // European Journal of Combinatorics. — 2006. — Т. 27, вип. 7. — С. 1117—1128. — DOI:10.1016/j.ejc.2006.06.005. з джерела 6 березня 2012. Процитовано 5 червня 2022.
    • Додатки й виправлення: Petr Hliněný, Geoff Whittle. Addendum to matroid tree-width // European Journal of Combinatorics. — 2009. — Т. 30, вип. 4. — С. 1036—1044. — DOI:10.1016/j.ejc.2008.09.028.
  • Frédéric Mazoit, Stéphan Thomassé. Surveys in Combinatorics 2007 / Anthony Hilton, John Talbot. — Cambridge University Press, 2007. — Т. 346. — С. 275. — (London Mathematical Society Lecture Note Series) з джерела 28 червня 2012
  • Sang-il Oum, . Testing branch-width // . — 2007. — Т. 97, вип. 3. — С. 385—393. — (Series B). — DOI:10.1016/j.jctb.2006.06.006.
  • [en], . Graph minors. X. Obstructions to tree-decomposition // Journal of Combinatorial Theory. — 1991. — Т. 52, вип. 2. — С. 153—190. — DOI:10.1016/0095-8956(91)90061-N.
  • . Call routing and the ratcatcher // Combinatorica. — 1994. — Т. 14, вип. 2. — С. 217—241. — DOI:10.1007/BF01215352.

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

U teoriyi grafiv gilkova dekompoziciya neoriyentovanogo grafa G ce iyerarhichna klasterizaciya reber grafa G predstavlena nekorenevim dvijkovim derevom T z rebrami z G yak listkami Vidalennya bud yakogo rebra z T podilyaye rebra grafa G na dva pidgrafi a shirinoyu dekompoziciyi vvazhayut najbilshu kilkist spilnih vershin u bud yakomu pidgrafi otrimanomu v takij sposib Shirina galuzhennya grafa G ce najmensha shirina bud yakoyi gilkovoyi dekompoziciyi grafa G Gilkova dekompoziciya gratki Pokazano e podil Podil dekompoziciya i sam graf mayut shirinu tri Shirina galuzhennya tisno pov yazana z derevnoyu shirinoyu dlya vsih grafiv voni lezhat u mezhah stalogo mnozhnika odna vid odnoyi i obidvi velichini mozhna opisati zaboronenimi minorami Yak i dlya derevnoyi shirini bagato zadach optimizaciyi na grafah mozhna efektivno rozv yazati na grafah iz maloyu shirinoyu galuzhennya Prote na vidminu derevnoyi shirini shirinu galuzhennya planarnogo grafa mozhna obchisliti tochno za polinomialnij chas Gilkovu dekompoziciyu ta shirinu galuzhennya mozhna uzagalniti z grafiv na matroyidi ViznachennyaNekoreneve dvijkove derevo ce zv yaznij neoriyentovanij graf bez cikliv u yakomu kozhen nelistovij vuzol maye rivno tri susidi Gilkovu dekompoziciyu mozhna podati yak nekoreneve dvijkove derevo T razom z biyekciyeyu mizh listkami dereva T ta rebrami danogo grafa G V E Yaksho e bud yake rebro dereva T to vidalennya e z T dilit jogo na dva piddereva T1 i T2 Cej podil dereva T na piddereva porodzhuye podil reber asocijovanih z listkami dereva T na dva pidgrafi grafa G G1 i G2 Takij podil grafa G na dva pidgrafi nazivayut e podilom Shirina e podilu ce chislo vershin grafa G incidentnih yak rebram z E1 tak i rebram z E2 Tobto ce mnozhina vershin spilnih dlya pidgrafiv G1 i G2 Shirina gilkovoyi dekompoziciyi ce najbilsha shirina bud yakogo e podilu Shirina galuzhennya grafa G ce najmensha shirina gilkovih dekompozicij grafa G Zv yazok iz derevnoyu shirinoyuGilkova dekompoziciya grafa tisno pov yazana z derevnoyu dekompoziciyeyu a shirina galuzhennya tisno pov yazana z derevnoyu shirinoyu Dvi ci velichini vidriznyayutsya lishe stalim mnozhnikom Zokrema v statti v yakij voni zaproponuvali shirinu galuzhennya en i ru pokazali sho dlya grafa G z derevnoyu shirinoyu k i shirinoyu galuzhennya b gt 1 b 1 k 3 2 b 1 displaystyle b 1 leq k leq left lfloor frac 3 2 b right rfloor 1 Shirina narizkiShirina narizki ce koncepciya viznachena analogichno shirini galuzhennya z tiyeyu rizniceyu sho u viznachennyah vershini ta rebra minyayut miscyami Dekompoziciya narizkoyu ce nekoreneve dvijkove derevo v yakomu kozhen listok predstavlyaye vershinu pochatkovogo grafa a shirina rozrizu ce chislo abo povna vaga u zvazhenih grafah reber incidentnih vershini v oboh pidderevah Algoritmi viznachennya shirini galuzhennya zazvichaj pracyuyut zvedennyam do ekvivalentnoyi zadachi viznachennya shirini narizki Zokrema shirina narizki seredinnogo grafa rivno vdvichi bilsha za shirinu galuzhennya vihidnogo grafa Algoritmi ta skladnistZadacha viznachennya chi maye graf G gilkovu dekompoziciyu iz shirinoyu sho ne perevishuye k ye NP povnoyu yaksho G i k ye vhidnimi danimi zadachi Odnak grafi zi shirinoyu galuzhennya ne bilshoyu vid k utvoryuyut simejstvo grafiv zamknene za minorami zvidki viplivaye sho obchislennya shirini galuzhennya ye en zadacheyu isnuye algoritm dlya obchislennya optimalnoyi gilkovoyi dekompoziciyi chas roboti yakogo na grafah iz shirinoyu galuzhennya sho ne perevishuye k dlya deyakogo stalogo k linijno zalezhit vid rozmiru grafa Dlya planarnih grafiv shirinu galuzhennya mozhna obchisliti za linijnij chas Ce kontrastuye iz derevnoyu shirinoyu dlya yakoyi skladnist obchislennya na planarnih grafah ye dobre vidomoyu vidkritoyu problemoyu Pochatkovij algoritm Pola Sejmura i en dlya obchislennya shirini galuzhennya planarnih grafiv rozv yazuvav zadachu za chas O n2 na grafi z n vershinami a yihnij algoritm dlya pobudovi gilkovoyi dekompoziciyi pracyuvav za chas O n4 Piznishe ostannij pokrasheno do O n3 Yak i v razi derevnoyi shirini shirinu galuzhennya mozhna vikoristati yak bazis algoritmiv dinamichnogo programuvannya dlya bagatoh NP skladnih zadach optimizaciyi i v cih algoritmah chas rozv yazuvannya bude eksponencialnim vid shirini vhidnogo grafa abo matroyida Napriklad Kuk i Sejmur zastosuvali zasnovanij na shirini galuzhennya metod dinamichnogo programuvannya do zadachi zlittya chastkovih rozv yazkiv zadachi komivoyazhera v odin globalnij rozv yazok shlyahom formuvannya rozridzhenogo grafa z ob yednannya chastkovih rozv yazkiv de vikoristali evristichne spektralne klasteruvannya dlya znahodzhennya horoshoyi gilkovoyi dekompoziciyi pislya chogo do neyi zastosuvali dinamichne programuvannya Fomin i Tilikos zapevnyayut sho pri rozrobci fiksovano parametrichno rozv yazuvanih algoritmiv na planarnih grafah shirina galuzhennya pracyuye krashe nizh derevna shirina z bagatoh prichin shirina galuzhennya mozhe buti tisnishe obmezhenoyu funkciyeyu parametra nizh obmezhennya derevnoyi shirini yiyi mozhna obchisliti za polinomialnij chas i algoritm obchislennya shirini galuzhennya ne maye velikih prihovanih konstant Uzagalnennya dlya matroyidivPonyattya gilkovoyi dekompoziciyi mozhna takozh viznachiti dlya matroyidiv sho uzagalnyuye gilkovu dekompoziciyu grafiv Gilkova dekompoziciya matroyida ye iyerarhichnoyu klasterizaciyeyu elementiv matroyida podana yak nekoreneve dvijkove derevo z elementami matroyida yak listkami Dlya matroyidiv e podil mozhna viznachiti v toj samij sposib sho j dlya grafiv a rezultatom bude podil mnozhini M elementiv matroyida na dvi pidmnozhini A i B Yaksho cherez r poznachiti funkciyu rangu matroyida to shirina e podilu viznachayetsya yak r A r B r M 1 a shirina dekompoziciyi ta shirina galuzhennya matroyida viznachayutsya analogichno do viznachen dlya grafa Shirina galuzhennya grafa ta shirina galuzhennya vidpovidnogo en vidriznyayutsya Napriklad shlyah iz troh reber i zirka z troh reber mayut rizni shirini galuzhennya 2 i 1 vidpovidno ale grafovij matroyid u nih odnakovij i maye shirinu galuzhennya 1 Odnak dlya grafiv sho ne ye derevami shirina galuzhennya grafa dorivnyuye shirini galuzhennya pov yazanogo grafovogo matroyida Shirina galuzhennya matroyida dorivnyuye shirini galuzhennya jogo en i z cogo viplivaye sho shirina galuzhennya bud yakogo planarnogo grafa yakij ne ye derevom dorivnyuye shirini galuzhennya jogo dvoyistogo grafa Shirina galuzhennya vazhliva skladova sprob rozshiriti teoriyu minoriv grafa na en hocha derevnu shirinu mozhna takozh uzagalniti na matroyidi i yiyi rol u teoriyi grafiv bilsha nizh shirini galuzhennya shirina galuzhennya maye zruchnishi vlastivosti Robertson i Sejmur vislovili pripushennya sho matroyidi podani bud yakim konkretnim skinchennim polem en sho ye analogiyeyu teoremi Robertsona Sejmura dlya grafiv ale gipotezu dovedeno tilki dlya matroyidiv iz obmezhenoyu shirinoyu galuzhennya Krim togo yaksho simejstvo matroyidiv zamknene za minorami i podane skinchennim polem ne vklyuchaye grafovih matroyidiv usih planarnih grafiv isnuye stala yaka obmezhuye shirinu galuzhennya v simejstvi sho uzagalnyuye vidpovidne tverdzhennya dlya simejstv grafiv zamknutih za minorami Dlya bud yakogo fiksovanogo k matroyidi z shirinoyu galuzhennya sho ne perevishuye k mozhna rozpiznati za polinomialnij chas algoritmom yakij otrimuye dostup do matroyida cherez en Zaboroneni minoriChotiri zaboroneni minori dlya grafiv iz shirinoyu galuzhennya tri Za teoremoyu Robertsona Sejmura grafi z shirinoyu galuzhennya k mozhna sharakterizuvati skinchennoyu mnozhinoyu zaboronenih minoriv Grafi z shirinoyu galuzhennya 0 ce paruvannya a najmenshi zaboroneni minori v comu vipadku ce shlyah iz dvoh dug ta trikutnij graf a takozh cikl iz dvoh dug yaksho rozglyadayutsya multigrafi Grafi z shirinoyu galuzhennya 1 ce grafi v yakih kozhna komponenta zv yaznosti ye zirkoyu a najmenshi zaboroneni minori dlya grafiv z shirinoyu galuzhennya 1 ce trikutnij graf abo cikl iz dvoh dug yaksho rozglyadayutsya multigrafi i shlyahi z troh dug Grafi z shirinoyu galuzhennya 2 ce grafi v yakih kozhna dvozv yazna komponenta ye paralelno poslidovnim grafom a yedinim najmenshim zaboronenim minorom ye povnij graf K4 z chotiroh vershin Graf maye shirinu galuzhennya tri todi j lishe todi koli jogo derevna shirina dorivnyuye trom i vin ne maye minorom grafa giperkubu Takim chinom chotiri zaboroneni minori ce tri z chotiroh zaboronenih minoriv grafiv z derevnoyu shirinoyu tri graf oktaedra povnij graf K5 i graf Vagnera razom iz grafom kuba Zaboroneni minori vivchayutsya takozh i dlya shirini galuzhennya matroyida popri vidsutnist povnoyi analogiyi teoremi Robertsona Sejmura u comu razi Matroyid maye shirinu galuzhennya odinicya todi j lishe todi koli bud yakij element ye abo petleyu abo kopetleyu tak sho yedinim najmenshim zaboronenim minorom ye en U 2 3 grafovij matroyid trikutnogo grafa Matroyid maye shirinu galuzhennya dva todi j lishe todi koli vin ye grafovim matroyidom grafa z shirinoyu galuzhennya dva tak sho minimalnimi zaboronenimi minorami ye grafovi matroyidi grafa K4 i negrafovij matroyid U 2 4 Matroyidi z shirinoyu galuzhennya tri ne cilkom kvazivporyadkovani bez dodatkovogo pripushennya shodo podannya nad skinchennim polem ale tim ne mensh matroyidi z bud yakoyu obmezhenoyu shirinoyu galuzhennya mayut skinchenne chislo najmenshih zaboronenih minoriv yaki mayut chislo elementiv sho zalezhat vid shirini galuzhennya ne bilsh nizh eksponencijno PrimitkiRobertson Seymour 1991 s 168 Theorem 5 1 Seymour Thomas 1994 Robertson Seymour 1991 s 164 Theorem 4 1 Bodlaender Thilikos 1997 Fomin Macojt i Todinka Fomin Mazoit Todinca 2009 opisuyut algoritm iz pokrashenoyu zalezhnistyu vid k 2 3 k ale zalezhnist vid chisla vershin zrostaye vid linijnoyi do kvadratichnoyi Kao Ming Yang red 2008 Treewidth of graphs Springer s 969 ISBN 9780387307701 arhiv originalu za 5 chervnya 2022 procitovano 5 chervnya 2022 She odna davnya vidkrita problema Chi isnuye algoritm polinomialnogo chasu obchislennya derevnoyi shirini planarnogo grafa Gu Tamaki 2008 Hicks 2000 Hlineny 2003 Cook Seymour 2003 Fomin Thilikos 2006 Robertson Seymour 1991 s 188 190 Section 12 Tangles and Matroids Mazoit Thomasse 2007 Hicks McMurray 2007 Hlineny Whittle 2006 Geelen Gerards Whittle 2006 Geelen Gerards Whittle 2002 Geelen Gerards Whittle 2007 Oum Seymour 2007 Robertson Seymour 1991 s 165 Theorem 4 2 Bodlaender Thilikos 1999 Chetvertij zaboronenij minor dlya derevnoyi shirini tri graf p yatikutnoyi prizmi maye graf kuba yak minor tak sho vin ne ye najmenshim dlya shirini galuzhennya tri Hall Oxley Semple Whittle 2002 Geelen Gerards Robertson Whittle 2003 LiteraturaHans L Bodlaender Dimitrios M Thilikos Proc 24th International Colloquium on Automata Languages and Programming ICALP 97 Springer Verlag 1997 T 1256 S 627 637 Lecture Notes in Computer Science DOI 10 1007 3 540 63165 8 217 Hans L Bodlaender Dimitrios M Thilikos Graphs with branchwidth at most three Journal of Algorithms 1999 T 32 vip 2 S 167 194 DOI 10 1006 jagm 1999 1011 William Tour merging via branch decomposition INFORMS Journal on Computing 2003 T 15 vip 3 S 233 248 DOI 10 1287 ijoc 15 3 233 16078 z dzherela 31 lipnya 2010 Procitovano 5 chervnya 2022 Fedor V Fomin Dimitrios M Thilikos Dominating sets in planar graphs branch width and exponential speed up SIAM Journal on Computing 2006 T 36 S 281 DOI 10 1137 S0097539702419649 Fedor V Fomin Frederic Mazoit Ioan Todinca Computing branchwidth via efficient triangulations and blocks Discrete Applied Mathematics 2009 T 157 vip 12 S 2726 2736 DOI 10 1016 j dam 2008 08 009 z dzherela 5 chervnya 2022 Procitovano 5 chervnya 2022 Jim Geelen Bert Gerards en Geoff Whittle On the excluded minors for the matroids of branch width k Journal of Combinatorial Theory Series B 2003 T 88 vip 2 S 261 265 DOI 10 1016 S0095 8956 02 00046 1 Jim Geelen Bert Gerards Geoff Whittle Branch width and well quasi ordering in matroids and graphs Journal of Combinatorial Theory Series B 2002 T 84 vip 2 S 270 290 DOI 10 1006 jctb 2001 2082 Jim Geelen Bert Gerards Geoff Whittle Proc International Congress of Mathematicians 2006 T III S 827 842 z dzherela 11 serpnya 2017 Jim Geelen Bert Gerards Geoff Whittle Excluding a planar graph from GF q representable matroids Journal of Combinatorial Theory Series B 2007 T 97 vip 6 S 971 998 DOI 10 1016 j jctb 2007 02 005 Qian Ping Gu Hisao Tamaki Optimal branch decomposition of planar graphs in O n3 time ACM Transactions on Algorithms 2008 T 4 vip 3 S 30 1 30 13 DOI 10 1145 1367064 1367070 Rhiannon Hall James Oxley Charles Semple Geoff Whittle On matroids of branch width three Journal of Combinatorial Theory Series B 2002 T 86 vip 1 S 148 171 DOI 10 1006 jctb 2002 2120 Illya V Hicks Branch Decompositions and their Applications Rice University 2000 Ph D thesis z dzherela 16 lipnya 2011 Illya V Hicks Nolan B McMurray Jr The branchwidth of graphs and their cycle matroids Journal of Combinatorial Theory Series B 2007 T 97 vip 5 S 681 692 DOI 10 1016 j jctb 2006 12 007 Petr Hlineny Proc 28th International Symposium on Mathematical Foundations of Computer Science MFCS 03 Springer Verlag 2003 T 2747 S 470 479 Lecture Notes in Computer Science DOI 10 1007 978 3 540 45138 9 41 Petr Hlineny Geoff Whittle Matroid tree width European Journal of Combinatorics 2006 T 27 vip 7 S 1117 1128 DOI 10 1016 j ejc 2006 06 005 z dzherela 6 bereznya 2012 Procitovano 5 chervnya 2022 Dodatki j vipravlennya Petr Hlineny Geoff Whittle Addendum to matroid tree width European Journal of Combinatorics 2009 T 30 vip 4 S 1036 1044 DOI 10 1016 j ejc 2008 09 028 Frederic Mazoit Stephan Thomasse Surveys in Combinatorics 2007 Anthony Hilton John Talbot Cambridge University Press 2007 T 346 S 275 London Mathematical Society Lecture Note Series z dzherela 28 chervnya 2012 Sang il Oum Testing branch width 2007 T 97 vip 3 S 385 393 Series B DOI 10 1016 j jctb 2006 06 006 en Graph minors X Obstructions to tree decomposition Journal of Combinatorial Theory 1991 T 52 vip 2 S 153 190 DOI 10 1016 0095 8956 91 90061 N Call routing and the ratcatcher Combinatorica 1994 T 14 vip 2 S 217 241 DOI 10 1007 BF01215352

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