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

Матеріал з testwiki
Версія від 12:40, 8 листопада 2022, створена imported>Lxlalexlxl (→Сімейства графів дерев обмеженої ширини)
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)
Перейти до навігації Перейти до пошуку

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

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

Визначення

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

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

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

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

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

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

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

β(Y)⊆β(X) при X⊆Y.

Ожина порядку чотири на 3×3 графі-ґратці, існування якої показує, що граф має деревну ширину принаймні  3

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

Приклади

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

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

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

Сімейства графів дерев обмеженої ширини

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

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

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

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

Шаблон:Докладніше

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

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

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

Алгоритми

Обчислення ширини дерева

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

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

Розв'язання інших задач на графах з малою шириною дерева

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

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

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

Шляхова ширина

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

Розмір мінора ґратки

Оскільки деревна ширина ґратки n × n дорівнює n, деревна ширина графу G завжди більша або дорівнює розміру найбільшої квадратної ґратки-мінора графу G. З іншого боку, існує функція f така, що деревна ширина не перевищує f(r), де r — розмір найбільшої квадратної ґратки-мінора. Однак відомі межі f не малі: f повинна бути не менше Ω(r2 log r) і не більше 202r5.[9] Строгіші кордони відомі для обмежених сімейств графів, що дає ефективні алгоритми для багатьох задач оптимізації на цих сімействах графів за теорією Шаблон:Не перекладено.Шаблон:Sfn Шаблон:Не перекладено дає аналог зв'язку між деревною шириною та розміром мінора ґратки для необмежених графів.Шаблон:Sfn

Діаметр і локальна деревна ширина

Кажуть, що сімейство F графів має обмежену локальну деревну ширину, якщо деревна ширина графів сімейства обмежена зверху функцією від діаметра. Якщо будь-який мінор члена сімейства F також входить до F, то F має обмежену локальну деревну ширину тоді й лише тоді, коли один із заборонених мінорів F — верхівковий граф.Шаблон:Sfn Початкове доведення цього результату показувало, що деревна ширина колекції графів без мінорів, які є верхівковими графами, зростає не швидше подвоєної експоненти від діаметра.[10] Пізніше це було зведено просто до експонентиШаблон:Sfn і, нарешті, до лінійної межі.Шаблон:Sfn Обмежена локальна деревна ширина тісно пов'язана з алгоритмічною теорією Шаблон:Не перекладено[11], і будь-яку властивість графу, яку можна визначити в рамках логіки першого порядку, можна обчислити для графів сімейства, які не містять мінорів-вершинних графів, за трохи більше ніж лінійний час.Шаблон:Sfn

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

Число Хадвігера і S-функції

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

Див. також

Примітки

Шаблон:Примітки

Посилання

Шаблон:Refbegin

Шаблон:Refend

  1. ↑ Шаблон:Harvnb
  2. ↑ Шаблон:Harvnb стр.354–355
  3. ↑ Шаблон:Harvnb, секция 12.3
  4. ↑ 4,0 4,1 Шаблон:Harvnb
  5. ↑ Шаблон:Harvnb.
  6. ↑ Шаблон:Harvnb; Шаблон:Harvnb.
  7. ↑ Шаблон:Harvnb.
  8. ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.
  9. ↑ Шаблон:Harvnb. Об Ω в нижней оценке смотрите «O» большое и «o» малое.
  10. ↑ Шаблон:Harvnb; Шаблон:Harvnb.
  11. ↑ Шаблон:Harvnb; Шаблон:Harvnb.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Деревна_ширина_(теорія_графів)&oldid=8712