Перегляд вихідного коду сторінки Деревна ширина (теорія графів)

В [[Теорія графів|теорії графів]] '''деревна ширина''' неорієнтованого графу&nbsp;— це число, асоційоване з графом. Деревну ширину можна визначити декількома еквівалентними способами: як розмір найбільшої множини вершин у [[Деревна декомпозиція|деревному розкладі]], як розмір найбільшої [[Кліка (теорія графів)|кліки]] в [[хордальний граф|хордальному]] доповненні графу, як найбільший порядок [[Укриття (теорія графів)|укриття]] під час опису стратегії гри [[Переслідування-ухилення|переслідування]] на графі або як найбільший порядок [[Ожина (теорія графів)|ожини]], набору зв'язних підграфів, які дотикаються один з одним. Деревна ширина часто використовується як параметр в аналізі {{Не перекладено|Параметрична складність|параметричної складності|en|parameterized complexity}} [[алгоритм]]ів на графах. Графи з шириною дерева, що не перевищує ''k,'' називаються [[Часткове k-дерево|частковими k-деревами]]. Багато інших добре вивчених сімейств графів також мають обмежену ширину дерева.

Поняття ширини дерева ввів Халін {{Harvard citation|Halin|1976}} ґрунтуючись на іншому параметрі, [[число Хадвігера|числі Хадвігера]], з яким деревна ширина має низку спільних властивостей. Пізніше деревну ширину перевідкрили Робертсон і Сеймур<ref>{{Harvnb|Robertson, Seymour|1984}}</ref>, і відтоді її вивчали багато авторів.<ref>{{Harvnb|Diestel|2005}} стр.354–355</ref>

== Визначення ==
[[Файл:Tree_decomposition.svg|міні|319x319пкс|Граф з вісьмома вершинами і його [[деревна декомпозиція]], яка має шість вершин. Кожне ребро графу з'єднує дві вершини, і ці вершини входять у список деякої вершини дерева разом, а кожна вершина входить до списку кожної вершини піддерева. Кожна вершина дерева містить список максимум трьох вершини, так що ширина цієї декомпозиції дорівнює двом.]]
[[Деревна декомпозиція]] графу ''G'' = (''V'', ''E'')&nbsp;— дерево ''T'', вершинами ''X''<sub>1</sub>, …, ''X''<sub>''n''</sub> якого є підмножини ''V'', які задовольняють таким властивостям<ref>{{Harvnb|Diestel|2005}}, секция 12.3</ref>:

# Об'єднання всіх множин ''X''<sub>''i''</sub> дорівнює ''V''. Таким чином, будь-яка вершина графу міститься хоча б в одній множині.
# Якщо ''X''<sub>''i''</sub> і ''X''<sub>''j''</sub> обидва містять вершину ''v'', то всі інші вершини дерева ''X''<sub>''k''</sub> на (єдиному) шляху з ''X''<sub>''i''</sub> в ''X''<sub>''j''</sub> також містять ''v''. Це еквівалентно твердженню, що вершини дерева, які містять ''v'', утворюють зв'язне піддерево ''T''.
# Для будь-якого ребра (''v'', ''w'') графу ''G'' існує підмножина ''X''<sub>''i''</sub>, що містить і ''v,'' і ''w''. Тобто вершини суміжні в графі якщо тільки відповідні піддерева мають спільну вершину в дереві ''T''.

''Ширина'' деревної декомпозиції&nbsp;— це розмір її найбільшої множини ''X''<sub>''i''</sub> мінус одиниця.

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

Так само, деревна ширина ''G'' на одиницю менша від розміру найбільшої [[Кліка (теорія графів)|кліки]] в [[Хордальний граф|хордальному графі]] з мінімальним [[Кліка (теорія графів)|кліковим числом]], який містить ''G''. Хордальний граф з цим кліковим числом можна отримати, якщо додати в ''G'' ребра між будь-якими двома вершинами, якщо обидва належать одній і тій самій (хоча б одній) множини ''X<sub>i</sub>''.

Деревну ширину можна також описати в термінах [[Укриття (теорія графів)|укриттів]], функцій, що описують стратегії ухилення для деяких ігор [[Переслідування-ухилення|переслідування]] на графі. Граф ''G'' має деревну ширину ''k'' в тому і тільки в тому випадку, коли в ньому є укриття порядку ''k'' + 1, але немає укриття з більшим порядком. Тут укриття порядку ''k'' + 1&nbsp;— це функція ''β'', яка відображає кожну множина ''X'' із максимум ''k'' вершинами в ''G'' в одну зі зв'язних компонент графу ''G'' \ ''X'' і для якої виконується властивість [[Монотонна функція|монотонності]]

<math>\beta(Y) \subseteq \beta(X) </math> при <math>X \subseteq Y</math>.
[[Файл:3x3_grid_graph_haven.svg|міні|[[Ожина (теорія графів)|Ожина]] порядку чотири на 3×3 графі-ґратці, існування якої показує, що граф має деревну ширину принаймні &nbsp;3]]
Схожий опис можна також зробити з використанням [[Ожина (теорія графів)|ожин]], сімейства зв'язних графів, які дотикаються між собою (що означає, що вони або мають спільну вершину, або з'єднані ребром){{Sfn|Seymour, Thomas|1993}}. Будемо говорити, що підмножина G покриває ожину (або є її покриттям), якщо вона перетинається з кожним елементом ожини. Порядок ожини&nbsp;— це найменше [[Задача про покриття множини|покриття]], і деревна ширина графу на одиницю менша від найбільшого порядку ожин.

== Приклади ==
Будь-який [[повний граф]] ''K<sub>n</sub>'' має деревну ширину ''n''&nbsp;−&nbsp;1. Це легко побачити, якщо використати визначення деревної ширини в термінах хордальних графів&nbsp;— повний граф вже хордальний, і додавання ребер не може зменшити розміру найбільшої кліки.

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

== Обмежена деревна ширина ==

=== Сімейства графів дерев обмеженої ширини ===
Для будь-якої фіксованої константи ''k'' графи з деревною шириною, що не перевищує ''k,'' називаються [[Часткове k-дерево|частковими k-деревами]]. Інші сімейства графів з обмеженою деревною шириною включають [[Кактус (теорія графів)|кактуси]], [[псевдоліс]]и, [[Паралельно-послідовний граф|паралельно-послідовні графи]], [[Зовніпланарний граф|зовніпланарні графи]], [[Граф Халіна|графи Халіна]] і [[Граф Аполлонія|мережі Аполлонія]]<ref name="b98">{{Harvnb|Bodlaender|1998}}</ref>. [[Граф потоку керування|Графи потоку керування]], що з'являються під час [[Транслятор|трансляції]] [[Структурне програмування|структурних програм]], також мають обмежену деревну ширину, що дозволяє ефективно виконувати деякі завдання, такі як [[розподіл регістрів]]{{Sfn|Thorup|1998}}.

[[Планарний граф|Планарні графи]] не мають обмеженої деревної ширини, оскільки ''''n'''' × ''n'' [[Решітка (теорія графів)|ґратка]]&nbsp;— це планарний граф, який має деревну ширину рівно ''n.'' Таким чином, якщо ''F''&nbsp;— це сімейство мінорно-замкнутих графів з обмеженою деревною шириною, воно не може включати всіх планарних графів. Навпаки, якщо деякий планарний граф не може бути мінором графів у сімействі ''F,'' то існує константа ''k,'' така що всі графи в ''F'' мають деревну ширину не більшу від ''k.'' Таким чином, наступні три умови еквівалентні між собою:{{Sfn|Robertson, Seymour|1986}}

# ''F''&nbsp;— сімейство мінорно-замкнутих графів обмеженої деревної ширини;
# Один зі скінченного числа заборонених мінорів для ''F'' планарний;
# ''F'' є сімейством мінорно-замкнутих графів, що включає не планарні графи.

=== Заборонені мінори ===
{{Докладніше|Характеризація забороненими графами}}
[[Файл:Partial_3-tree_forbidden_minors.svg|міні|300x300пкс| Чотири заборонених мінори для деревної ширини 3]]
Для будь-якого скінченного значення ''k'' графи з деревною шириною, що не перевищує ''k,'' можна описати скінченним числом [[Характеризація забороненими графами|заборонених мінорів]], кожен з яких включає щонайменше один планарний граф.

* Для ''k'' = 1 єдиним забороненим мінором є [[Циклічний граф|цикл]] із 3 вершинами.<ref name="b88">{{Harvnb|Bodlaender|1988}}.</ref>
* Для ''k'' = 2 єдиним забороненим мінором є [[повний граф]] ''K''<sub>4</sub> з 4 вершинами.
* Для ''k'' = 3 існує чотири заборонених мінори&nbsp;— ''K''<sub>5,</sub> граф [[октаедр]]а, [[Граф призми|граф]] [[П'ятикутна призма|п'ятикутної призми]] і [[граф Вагнера]]. Два з перелічених [[Багатогранний граф|поліедральних графів]] є планарними.<ref>{{Harvnb|Arnborg, Proskurowski, Corneil|1990}}; {{Harvnb|Satyanarayana, Tung|1990}}.</ref>

Для великих значень ''k'' число заборонених мінорів зростає принаймні як експонента від ''k.''{{Sfn|Ramachandramurthi|1997}} Однак відомі верхні границі розміру й числа заборонених мінорів значно вищі від цієї нижньої межі.{{Sfn|Lagergren|1993}}

== Алгоритми ==

=== Обчислення ширини дерева ===
Визначення, чи має заданий граф ''G'' деревну ширину, яка не перевищує ''k,'' є [[NP-повна задача|NP-повною]] задачею.{{Sfn|Arnborg, Corneil, Proskurowski|1987}} Однак, якщо ''k'' фіксоване, графи з деревною шириною ''k'' можна знайти і відповідний [[деревний розклад]] побудувати за лінійний час.<ref name="b96">{{Harvnb|Bodlaender|1996}}.</ref> Час виконання алгоритму залежить від ''k'' експоненціально.

На практиці алгоритм Шойхета і Гайгера {{Harvard citation|Shoikhet, Geiger|1997}} може знайти деревну ширину графів, що мають розмір до 100 вершин і деревну ширину аж до 11, знаходженням хордального доповнення цих графів з оптимальною деревною шириною.

=== Розв'язання інших задач на графах з малою шириною дерева ===
На початку сімдесятих років двадцятого століття помічено, що великий клас комбінаторних задач оптимізації на графах можна ефективно розв'язувати за допомогою несеріального{{Прояснити}} [[Динамічне програмування|динамічного програмування]], якщо граф має обмежену ''розмірність,''{{Sfn|Bertelé, Brioschi|1972}} параметр, пов'язаний з деревною шириною. Пізніше, в кінці 1980-х<ref>{{Harvnb|Arnborg, Proskurowski|1989}}; {{Harvnb|Bern, Lawler, Wong|1987}}; {{Harvnb|Bodlaender|1988}}.</ref>, ряд математиків незалежно виявили, що багато алгоритмічних задач, [[NP-повна задача|NP-повних]] для довільних графів, можна ефективно розв'язати [[Динамічне програмування|динамічним програмуванням]] для графів обмеженої деревної ширини, якщо використовувати деревне розкладання цих графів.

Наприклад, задачу [[Розфарбовування графів|розфарбовування графу]] деревної ширини ''k'' можна розв'язати за допомогою [[Динамічне програмування|динамічного програмування]] на деревному розкладі графу. Для кожної множини ''X<sub>i</sub>'' деревного розкладу і кожного розбиття вершин ''X<sub>i</sub>'' на кольори алгоритм визначає, чи припустима отримана розмальовка і чи можна її розширити на всі похідні вершини розкладу шляхом комбінування інформації однакового типу і запам'ятовування в цих вершинах. Результуючий алгоритм знаходить оптимальну розмальовку графу з ''n'' вершинами за час O(''k<sup>k</sup>''<sup>&nbsp;+&nbsp;O(1)</sup>''n'')'','' що робить цю задачу {{Не перекладено|Параметрична складність|параметрично складною з фіксованим параметром|en|parameterized complexity}}.

== Пов'язані параметри ==

=== Шляхова ширина ===
{{Докладніше|Шляхова ширина графу}}
[[Шляхова ширина графу]] має дуже схоже на деревну ширину визначення через деревне розкладення, але обмежується тільки тими розкладеннями, в яких кінцеве дерево є [[Шлях (граф)|шляхом]]. Іншим способом можна визначити шляхову ширину виходячи з [[Інтервальний граф|інтервального графу]] подібно до визначення деревної ширини за допомогою хордальних графів. Як наслідок, шляхова ширина графу як мінімум не менша від його деревної ширини, але може бути більшою тільки на логарифмічний множник.<ref name="b98"/> Ще один параметр, {{Не перекладено|смугова ширина графу||en|graph bandwidth}}, має схоже визначення, що спирається на [[Інтервальний граф|правильні інтервальні графи]], і значення параметра не менше від шляхової ширини. Крім цього, є [[Деревна глибина (теорія графів)|деревна глибина]], число, обмежене для мінорно-замкнутих графів тоді й лише тоді, коли сімейство не включає всіх графів-шляхів, і [[Виродження (теорія графів)|виродження]], міра розрідженості графу, яка не перевищує деревної ширини.

=== Розмір мінора ґратки ===
Оскільки деревна ширина [[Решітка (теорія графів)|ґратки]] ''n''&nbsp;×&nbsp;''n'' дорівнює ''n'', деревна ширина графу ''G'' завжди більша або дорівнює розміру найбільшої квадратної ґратки-[[Мінор графу|мінора]] графу ''G''. З іншого боку, існує функція ''f'' така, що деревна ширина не перевищує ''f''(''r''), де ''r''&nbsp;— розмір найбільшої квадратної ґратки-мінора. Однак відомі межі ''f'' не малі: ''f'' повинна бути не менше Ω(''r''<sup>2</sup>&nbsp;log&nbsp;''r'') і не більше 20<sup>2''r''<sup>5</sup></sup>.<ref>{{Harvnb|Robertson, Seymour, Thomas|1994}}. Об Ω в нижней оценке смотрите [[Нотація Ландау|«O» большое и «o» малое]].</ref> Строгіші кордони відомі для обмежених сімейств графів, що дає ефективні алгоритми для багатьох задач оптимізації на цих сімействах графів за теорією {{Не перекладено|Двовимірність|двовимірності|en|bidimensionality}}.{{Sfn|Demaine, Hajiaghayi|2008}} {{Не перекладено|Теорема Халіна про ґратки||en|Halin's grid theorem}} дає аналог зв'язку між деревною шириною та розміром мінора ґратки для необмежених графів.{{Sfn|Diestel|2004}}

=== Діаметр і локальна деревна ширина ===
Кажуть, що сімейство ''F'' графів має '''обмежену локальну деревну ширину''', якщо деревна ширина графів сімейства [[Верхня і нижня границі|обмежена зверху]] функцією від [[Відстань (теорія графів)|діаметра]]. Якщо будь-який [[Мінор графу|мінор]] члена сімейства ''F'' також входить до ''F'', то ''F'' має обмежену локальну деревну ширину тоді й лише тоді, коли один із [[Характеризація забороненими графами|заборонених мінорів]] ''F''&nbsp;— [[верхівковий граф]].{{Sfn|Eppstein|2000}} Початкове доведення цього результату показувало, що деревна ширина колекції графів без мінорів, які є верхівковими графами, зростає не швидше подвоєної експоненти від діаметра.<ref>{{Harvnb|Eppstein|2000}}; {{Harvnb|Demaine, Hajiaghayi|2004a}}.</ref> Пізніше це було зведено просто до експоненти{{Sfn|Demaine, Hajiaghayi|2008}} і, нарешті, до лінійної межі.{{Sfn|Demaine, Hajiaghayi|2004b}} Обмежена локальна деревна ширина тісно пов'язана з алгоритмічною теорією {{Не перекладено|Двовимірність|двовимірності|en|bidimensionality}}<ref>{{Harvnb|Demaine, Fomin, Hajiaghayi, Thilikos|2004}}; {{Harvnb|Demaine, Hajiaghayi|2008}}.</ref>, і будь-яку властивість графу, яку можна визначити в рамках [[Логіка першого порядку|логіки першого порядку]], можна обчислити для графів сімейства, які не містять мінорів-вершинних графів, за трохи більше ніж лінійний час.{{Sfn|Frick, Grohe|2001}}

Деякі класи графів, не замкнуті відносно мінорів, все ж мають обмежену локальну деревну ширину. Зокрема, це [[1-планарний граф|1-планарні графи]], тобто графи, які можна намалювати на площині з максимум одним перетином одного ребра, і загальніші графи, які можна намалювати на поверхні обмеженого роду з обмеженим числом перетинів ребер. Як і у випадку сімейств мінорно-замкнутих графів з обмеженою локальною деревною шириною, ця властивість прокладає шлях до ефективних апроксимаційних алгоритмів для таких графів.{{Sfn|Grigoriev, Bodlaender|2007}}

=== Число Хадвігера і ''S''-функції ===
Халін {{Harvard citation|Halin|1976}} визначає клас параметрів графів, який він називає ''S''-функціями, і цей клас включає деревну ширину. Ці функції мають за область визначення графи, за область значень&nbsp;— цілі числа, і вони повинні набувати значення нуль на графах без ребер і повинні бути [[Мінор графу|монотонними відносно мінорів]], тобто збільшуватися на одиницю при додаванні нової вершини, яка суміжна всім попереднім вершинам. Потрібно також, щоб значення функції від графу було рівне більшому зі значень на двох підмножинах, перетин яких є [[Вершинний сепаратор (теорія графів)|вершинним сепаратором]] і [[Кліка (теорія графів)|клікою]] одночасно. Множина всіх таких функцій утворює [[Повна решітка|повну ґратку]] відносно операцій поелементної мінімізації й максимізації. Верхній елемент у цій ґратці&nbsp;— деревна ширина, а нижній&nbsp;— [[число Хадвігера]], розмір максимального [[Повний граф|повного]] мінора в заданому графі.

== Див. також ==
* [[Клікова ширина]]
* [[Шляхова ширина графу]]
* [[Деревна глибина (теорія графів)]]
* [[Теорема Курселя]]

== Примітки ==
{{примітки|2}}

== Посилання ==
{{Refbegin|colwidth=30em}}
* {{Стаття|author=S. Arnborg, D. Corneil, A. Proskurowski|title=Complexity of finding embeddings in a ''k''-tree|видання=SIAM Journal on Matrix Analysis and Applications|том=8|issue=2|date=1987|pages=277–284|doi=10.1137/0608024|ref=Arnborg, Corneil, Proskurowski}}.
* {{Стаття|author=Stefan Arnborg, Andrzej Proskurowski, Derek G. Corneil|doi=10.1016/0012-365X(90)90292-P|issue=1|видання=Discrete Mathematics|pages=1–19|title=Forbidden minors characterization of partial 3-trees|том=80|date=1990|ref=Arnborg, Proskurowski, Corneil}}.
* {{Стаття|author=S. Arnborg, A. Proskurowski|title=Linear time algorithms for NP-hard problems restricted to partial ''k''-trees|видання=Discrete Applied Mathematics|том=23|issue=1|date=1989|pages=11–24|doi=10.1016/0166-218X(89)90031-0|ref=Arnborg, Proskurowski}}.
* {{Стаття|author=M. W. Bern, E. L. Lawler, A. L. Wong|title=Linear-time computation of optimal subgraphs of decomposable graphs|видання=Journal of Algorithms|том=8|issue=2|date=1987|pages=216–235|doi=10.1016/0196-6774(87)90039-3|ref=Bern, Lawler, Wong}}.
* {{Стаття|author=Umberto Bertelé, Francesco Brioschi|title=Nonserial Dynamic Programming|date=1972|publisher=Academic Press|isbn=0-12-093450-7|ref=Bertelé, Brioschi}}.
* {{Стаття|author=Hans L. Bodlaender|title=Proc. 15th International Colloquium on Automata, Languages and Programming|publisher=Springer-Verlag|серія=Lecture Notes in Computer Science|том=317|date=1988|pages=105–118|doi=10.1007/3-540-19488-6_110|ref=Bodlaender}}.
* {{Стаття|author=Hans L. Bodlaender|title=A linear time algorithm for finding tree-decompositions of small treewidth|видання=SIAM Journal on Computing|том=25|issue=6|date=1996|pages=1305–1317|doi=10.1137/S0097539793251219|ref=Bodlaender}}.
* {{Стаття|author=Hans L. Bodlaender|title=A partial ''k''-arboretum of graphs with bounded treewidth|видання=Theoretical Computer Science|том=209|issue=1–2|pages=1–45|date=1998|doi=10.1016/S0304-3975(97)00228-4|ref=Bodlaender}}.
* {{Стаття|author=Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, Dimitrios M. Thilikos|date=2004|doi=10.1137/S0895480103433410|issue=3|видання=SIAM Journal on Discrete Mathematics|pages=501–511|title=Bidimensional parameters and local treewidth|том=18|ref=Demaine, Fomin, Hajiaghayi, Thilikos}}.
* {{Стаття|author=Erik D. Demaine, MohammadTaghi Hajiaghayi|doi=10.1007/s00453-004-1106-1|issue=3|видання=Algorithmica|pages=211–215|title=Diameter and treewidth in minor-closed graph families, revisited|том=40|date=2004a|ref=Demaine, Hajiaghayi}}.
* {{Стаття|author=Erik D. Demaine, MohammadTaghi Hajiaghayi|place=New York|pages=840–849|publisher=ACM|title=Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms|date=2004b|ref=Demaine, Hajiaghayi}}.
* {{Стаття|author=Erik D. Demaine, Mohammad Taghi Hajiaghayi|doi=10.1007/s00493-008-2140-4|issue=1|видання=[[Combinatorica]]|pages=19–36|title=Linearity of grid minors in treewidth with applications through bidimensionality|url=http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf|том=28|date=2008|ref=Demaine, Hajiaghayi|accessdate=1 грудня 2020|archivedate=11 жовтня 2020|archiveurl=https://web.archive.org/web/20201011115400/http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf}}.
* {{Стаття|author=Reinhard Diestel|doi=10.1007/BF02941538|видання=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|pages=237–242|title=A short proof of Halin's grid theorem|том=74|date=2004|ref=Diestel}}.
* {{Стаття|author=Reinhard Diestel|title=Graph Theory|publisher=[[Springer Science+Business Media|Springer]]|date=2005|видання=3rd|isbn=3-540-26182-6|url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/|ref=Diestel|accessdate=1 грудня 2020|archivedate=28 липня 2011|archiveurl=https://web.archive.org/web/20110728103939/http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/}}.
* {{Стаття|author=D. Eppstein|doi=10.1007/s004530010020|issue=3-4|видання=Algorithmica|pages=275–291|title=Diameter and treewidth in minor-closed graph families|том=27|date=2000|ref=Eppstein}}.
* {{Стаття|author=Markus Frick, Martin Grohe|doi=10.1145/504794.504798|issue=6|видання=Journal of the ACM|pages=1184–1206|title=Deciding first-order properties of locally tree-decomposable structures|том=48|date=2001|ref=Frick, Grohe}}.
* {{Стаття|author=Alexander Grigoriev, Hans L. Bodlaender|doi=10.1007/s00453-007-0010-x|issue=1|видання=Algorithmica|pages=1–11|title=Algorithms for graphs embeddable with few crossings per edge|том=49|date=2007|ref=Grigoriev, Bodlaender}}.
* {{Стаття|title=''S''-functions for graphs|date=1976|author=Rudolf Halin|видання=Journal of Geometry|pages=171–186|том=8|doi=10.1007/BF01917434|ref=Halin}}.
* {{Стаття|author=Jens Lagergren|doi=10.1090/conm/147/01202|place=Providence, RI|pages=601–621|publisher=American Mathematical Society|серія=Contemporary Mathematics|title=Graph structure theory (Seattle, WA, 1991)|том=147|date=1993|ref=Lagergren}}.
* {{Стаття|author=Siddharthan Ramachandramurthi|doi=10.1137/S0895480195280010|issue=1|видання=SIAM Journal on Discrete Mathematics|pages=146–157|title=The structure and number of obstructions to treewidth|том=10|date=1997|ref=Ramachandramurthi}}.
* {{Стаття|author=Neil Robertson, Paul D. Seymour|title=Graph minors III: Planar tree-width|видання=Journal of Combinatorial Theory, Series B|том=36|issue=1|date=1984|pages=49–64|doi=10.1016/0095-8956(84)90013-3|ref=Robertson, Seymour}}.
* {{Стаття|author=Neil Robertson, Paul D. Seymour|title=Graph minors V: Excluding a planar graph|видання=Journal of Combinatorial Theory, Series B|том=41|issue=1|date=1986|pages=92–114|doi=10.1016/0095-8956(86)90030-4|ref=Robertson, Seymour}}.
* {{Стаття|author=Neil Robertson, Paul Seymour, Robin Thomas|doi=10.1006/jctb.1994.1073|issue=2|видання=[[Journal of Combinatorial Theory]]|серія=Series B|pages=323–348|title=Quickly excluding a planar graph|том=62|date=1994|ref=Robertson, Seymour, Thomas}}.
* {{Стаття|author=A. Satyanarayana, L. Tung|doi=10.1002/net.3230200304|issue=3|видання=Networks|pages=299–322|title=A characterization of partial 3-trees|том=20|date=1990|ref=Satyanarayana, Tung}}.
* {{Стаття|author=Paul D. Seymour, Robin Thomas|title=Graph Searching and a Min-Max Theorem for Tree-Width.|видання=Journal of Combinatorial Theory, Series B|том=58|issue=1|pages=22–33|doi=10.1006/jctb.1993.1027|date=1993|ref=Seymour, Thomas}}.
* {{Стаття|author=Kirill Shoikhet, Dan Geiger|pages=185–190|title=Proc. AAAI '97|url=http://www.aaai.org/Papers/AAAI/1997/AAAI97-029.pdf|date=1997|ref=Shoikhet, Geiger|accessdate=1 грудня 2020|archivedate=2 лютого 2021|archiveurl=https://web.archive.org/web/20210202124226/https://www.aaai.org/Papers/AAAI/1997/AAAI97-029.pdf}}.
* {{Стаття|author=Mikkel Thorup|title=All structured programs have small tree width and good register allocation|видання=Information and Computation|том=142|issue=2|date=1998|pages=159–181|doi=10.1006/inco.1997.2697|ref=Thorup}}.
{{Refend}}
[[Категорія:Теорія мінорів графів]]
[[Категорія:Дерева (теорія графів)]]