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

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

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

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

Чотири заборонених мінори для деревної ширини 3

Для будь-якого скінченного значення 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), що робить цю задачу параметрично складною з фіксованим параметром.

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

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

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

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

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