Деревна ширина (теорія графів)

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

Поняття ширини дерева ввів Халін (Halin, 1976) ґрунтуючись на іншому параметрі, числі Хадвігера, з яким деревна ширина має низку спільних властивостей. Пізніше деревну ширину перевідкрили Робертсон і Сеймур^[1], і відтоді її вивчали багато авторів.^[2]

Деревна декомпозиція графу G = (V, E) — дерево T, вершинами X₁, …, X_n якого є підмножини V, які задовольняють таким властивостям^[3]:

1. Об'єднання всіх множин X_i дорівнює V. Таким чином, будь-яка вершина графу міститься хоча б в одній множині.
2. Якщо X_i і X_j обидва містять вершину v, то всі інші вершини дерева X_k на (єдиному) шляху з X_i в X_j також містять v. Це еквівалентно твердженню, що вершини дерева, які містять v, утворюють зв'язне піддерево T.
3. Для будь-якого ребра (v, w) графу G існує підмножина X_i, що містить і v, і w. Тобто вершини суміжні в графі якщо тільки відповідні піддерева мають спільну вершину в дереві T.

Ширина деревної декомпозиції — це розмір її найбільшої множини X_i мінус одиниця.

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

Так само, деревна ширина G на одиницю менша від розміру найбільшої кліки в хордальному графі з мінімальним кліковим числом, який містить G. Хордальний граф з цим кліковим числом можна отримати, якщо додати в G ребра між будь-якими двома вершинами, якщо обидва належать одній і тій самій (хоча б одній) множини X_i.

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

${\displaystyle \beta (Y)\subseteq \beta (X)}$ при ${\displaystyle X\subseteq Y}$.

Схожий опис можна також зробити з використанням ожин, сімейства зв'язних графів, які дотикаються між собою (що означає, що вони або мають спільну вершину, або з'єднані ребром)^[4]. Будемо говорити, що підмножина G покриває ожину (або є її покриттям), якщо вона перетинається з кожним елементом ожини. Порядок ожини — це найменше покриття, і деревна ширина графу на одиницю менша від найбільшого порядку ожин.

Будь-який повний граф K_n має деревну ширину n − 1. Це легко побачити, якщо використати визначення деревної ширини в термінах хордальних графів — повний граф вже хордальний, і додавання ребер не може зменшити розміру найбільшої кліки.

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

Для будь-якої фіксованої константи k графи з деревною шириною, що не перевищує k, називаються частковими k-деревами. Інші сімейства графів з обмеженою деревною шириною включають кактуси, псевдоліси, паралельно-послідовні графи, зовніпланарні графи, графи Халіна і мережі Аполлонія^[5]. Графи потоку керування, що з'являються під час трансляції структурних програм, також мають обмежену деревну ширину, що дозволяє ефективно виконувати деякі завдання, такі як розподіл регістрів^[6].

Планарні графи не мають обмеженої деревної ширини, оскільки 'n' × n ґратка — це планарний граф, який має деревну ширину рівно n. Таким чином, якщо F — це сімейство мінорно-замкнутих графів з обмеженою деревною шириною, воно не може включати всіх планарних графів. Навпаки, якщо деякий планарний граф не може бути мінором графів у сімействі F, то існує константа k, така що всі графи в F мають деревну ширину не більшу від k. Таким чином, наступні три умови еквівалентні між собою:^[7]

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

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

• Для k = 1 єдиним забороненим мінором є цикл із 3 вершинами.^[8]
• Для k = 2 єдиним забороненим мінором є повний граф K₄ з 4 вершинами.
• Для k = 3 існує чотири заборонених мінори — K_5, граф октаедра, граф п'ятикутної призми і граф Вагнера. Два з перелічених поліедральних графів є планарними.^[9]

Для великих значень k число заборонених мінорів зростає принаймні як експонента від k.^[10] Однак відомі верхні границі розміру й числа заборонених мінорів значно вищі від цієї нижньої межі.^[11]

Визначення, чи має заданий граф G деревну ширину, яка не перевищує k, є NP-повною задачею.^[12] Однак, якщо k фіксоване, графи з деревною шириною k можна знайти і відповідний деревний розклад побудувати за лінійний час.^[13] Час виконання алгоритму залежить від k експоненціально.

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

На початку сімдесятих років двадцятого століття помічено, що великий клас комбінаторних задач оптимізації на графах можна ефективно розв'язувати за допомогою несеріального^{[прояснити]} динамічного програмування, якщо граф має обмежену розмірність,^[14] параметр, пов'язаний з деревною шириною. Пізніше, в кінці 1980-х^[15], ряд математиків незалежно виявили, що багато алгоритмічних задач, NP-повних для довільних графів, можна ефективно розв'язати динамічним програмуванням для графів обмеженої деревної ширини, якщо використовувати деревне розкладання цих графів.

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

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

Оскільки деревна ширина ґратки n × n дорівнює n, деревна ширина графу G завжди більша або дорівнює розміру найбільшої квадратної ґратки-мінора графу G. З іншого боку, існує функція f така, що деревна ширина не перевищує f(r), де r — розмір найбільшої квадратної ґратки-мінора. Однак відомі межі f не малі: f повинна бути не менше Ω(r² log r) і не більше 20^2r5.^[16] Строгіші кордони відомі для обмежених сімейств графів, що дає ефективні алгоритми для багатьох задач оптимізації на цих сімействах графів за теорією двовимірності^[en].^[17] Теорема Халіна про ґратки^[en] дає аналог зв'язку між деревною шириною та розміром мінора ґратки для необмежених графів.^[18]

Кажуть, що сімейство F графів має обмежену локальну деревну ширину, якщо деревна ширина графів сімейства обмежена зверху функцією від діаметра. Якщо будь-який мінор члена сімейства F також входить до F, то F має обмежену локальну деревну ширину тоді й лише тоді, коли один із заборонених мінорів F — верхівковий граф.^[19] Початкове доведення цього результату показувало, що деревна ширина колекції графів без мінорів, які є верхівковими графами, зростає не швидше подвоєної експоненти від діаметра.^[20] Пізніше це було зведено просто до експоненти^[17] і, нарешті, до лінійної межі.^[21] Обмежена локальна деревна ширина тісно пов'язана з алгоритмічною теорією двовимірності^[en][22], і будь-яку властивість графу, яку можна визначити в рамках логіки першого порядку, можна обчислити для графів сімейства, які не містять мінорів-вершинних графів, за трохи більше ніж лінійний час.^[23]

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

Халін (Halin, 1976) визначає клас параметрів графів, який він називає S-функціями, і цей клас включає деревну ширину. Ці функції мають за область визначення графи, за область значень — цілі числа, і вони повинні набувати значення нуль на графах без ребер і повинні бути монотонними відносно мінорів, тобто збільшуватися на одиницю при додаванні нової вершини, яка суміжна всім попереднім вершинам. Потрібно також, щоб значення функції від графу було рівне більшому зі значень на двох підмножинах, перетин яких є вершинним сепаратором і клікою одночасно. Множина всіх таких функцій утворює повну ґратку відносно операцій поелементної мінімізації й максимізації. Верхній елемент у цій ґратці — деревна ширина, а нижній — число Хадвігера, розмір максимального повного мінора в заданому графі.

• Клікова ширина
• Шляхова ширина графу
• Деревна глибина (теорія графів)
• Теорема Курселя