У теорії графів шляхова декомпозиція графа G — це, неформально, подання графа G у вигляді «потовщеного» шляху, а шляхова ширина графа G — це число, що вимірює, наскільки граф G був потовщений. Формальніше, шляхова декомпозиція — це послідовності вершин підмножини графа G, такі, що кінцеві вершини кожного ребра з'являються в одній з підмножин і кожна вершина належить (хоча б) одній множині, а шляхова ширина на одиницю менша від розміру найбільшої множини в цій декомпозиції. Шляхова ширина відома також як інтервальна товщина (на одиницю менше від розміру найбільшої кліки інтервального суперграфа графа G), величина вершинного розділення, чи вершинно-пошукове числоБагато використаних у статті терминів можна знайти у вступі до дисертації Ф. В. Фоміна ().
Шляхова ширина і шляхова декомпозиція є тісною аналогією з деревною шириною і деревною декомпозицією. Вони відіграють ключову роль у теорії мінорів графа — сімейства графів, які замкнуті відносно мінорів графа і не включають усі дерева, можна схарактеризувати як такі, що мають обмежену шляхову ширину, і «вихори», що виникають у загальній структурній теорії сімейств графів, замкнутих за мінором, мають обмежену шляхову ширину. Шляхова ширина і графи з обмеженою шляховою шириною застосовуються в розробці НВІС, візуалізації графів та комп'ютерній лінгвістиці.
Задача знаходження шляхової ширини довільних графів є NP-складною. Більше того, NP-складною є навіть задача апроксимації шляхової ширини точно. Однак ця задача є фіксовано-параметрично розв'язною — перевірку, чи має граф шляхову ширину k, можна здійснити за час, який лінійно залежить від розміру графа, але суперекспоненціально від k. Крім того, для деяких особливих класів графів, таких як дерева, шляхову ширину можна обчислити за поліноміальний час, не залежний від k. Багато задач теорії графів можна ефективно розв'язати на графах з обмеженою шляховою шириною за допомогою динамічного програмування на шляховій декомпозиції графа. Деревну декомпозицію можна також використовувати для оцінювання ємнісної складності алгоритмів динамічного програмування на графах з обмеженою деревною шириною.
Визначення
У першій відомій серії статей про мінори графа Робертсон і Сеймур визначили шляхову декомпозицію графа G як послідовність підмножин Xi вершин графа G з двома властивостями: Для кожного ребра G існує i, таке, що обидві кінцеві точки ребра належать підмножині Xi. Для будь-яких трьох індексів i ≤ j ≤ k, Xi ∩ Xk ⊆ Xj. Друга з цих двох властивостей еквівалентна вимозі, що підмножини, які містять будь-яку вершину, утворюють неперервну підпослідовність усієї послідовності. Мовою пізнішої серії робіт Робертсона і Сеймура про мінори графа, шляхова декомпозиція — це деревна декомпозиція (X,T), в якій дерево T декомпозиції, що лежить нижче, є шляхом.
Ширина шляхової декомпозиції визначається так само, як і для деревної декомпозиції, як maxi |Xi| − 1, а шляхова ширина графа G дорівнює мінімальній ширині всіх шляхових декомпозицій графа G. Віднімання одиниці від розміру Xi в цьому визначенні мало впливає на більшість застосувань шляхової ширини, але зате робить шляхову ширину шляху рівною одиниці.
Альтернативні описи Як пише Бодлендер шляхову ширину можна описати багатьма еквівалентними способами.
Склеювання послідовностей Деревну декомпозицію можна описати як послідовність графів Gi, які склеєні шляхом ототожнення пар вершин у сусідніх графах послідовності, і результатом цього склеювання є граф G. Як графи Gi можна взяти породжені підграфи множин Xi у першому визначенні шляхової декомпозиції, зі склеюванням вершин у сусідніх породжених підграфах, якщо ці вершини породжені тією ж самою вершиною з G. З іншого боку можна відновити Xi як множини вершин графів Gi. Ширина деревної декомпозиції тоді на одиницю менша від максимального числа вершин в одному з графів Gi.
Інтервальна товщина
Шляхова ширина будь-якого графа G на одиницю менша від найменшого клікового числа інтервального графа, що містить G як підграф. Тобто для будь-якої деревної декомпозиції графа G можна знайти інтервальний суперграф, і для будь-якого інтервального суперграфа G можна знайти деревну декомпозицію графа G, ширина декомпозиції якої на одиницю менша від клікового числа інтервального графа.
З одного боку, припустимо, що деревна декомпозиція графа G задана. Тоді можна уявити вершини декомпозиції як точки на прямій (в тому порядку, в якому вони входять до шляху) і подати кожну вершину v як замкнутий інтервал, для якого ці точки є кінцевими. Наприклад, нехай (X1, …, Xr) — шляхова декомпозиція графа G, точки на прямій — [1, …, r], тоді подання вершини v — це інтервал . Тоді деревна декомпозиція вершин, що містять v, відповідає кінцевим точкам інтервалу для v. Граф перетинів інтервалів, утворений з вершин G, — це інтервальний граф, що містить G як підграф. Його максимальні кліки задаються множиною інтервалів, що містять точки представлення, і їх розмір найбільшої кліки на одиницю більший від шляхової ширини графа G.
З іншого боку, якщо G — підграф інтервального графа з кліковим числом p+1, то граф G має деревну декомпозицію ширини p, вершини якої задані максимальними кліками інтервального графа. Наприклад, інтервальний граф, показаний з його інтервальним поданням на рисунку, має деревну декомпозицію з п'ятьма вершинами, відповідними п'ятьом максимальним клікам ABC, ACD, CDE, CDF та FG. Розмір максимальної кліки дорівнює трьом, а ширина цієї деревної декомпозиції дорівнює двом.
Ця еквівалентність між шляховою шириною й інтервальною товщиною є тісною аналогією з еквівалентністю між деревною шириною і мінімальним кліковим числом (мінус одиниця) хордального графа, для якого даний граф є підграфом. Інтервальні графи є особливим випадком хордальних графів, а хордальні графи можна подати у вигляді графів перетинів піддерев спільних дерев, що узагальнює підхід, за якого інтервальні графи інтерпретуються як графи перетинів підшляхів шляху.
Величина вершинного поділу Припустимо, що вершини графа G лінійно впорядковані. Тоді величина вершинного поділу графа G — це найменше число s, таке, що для кожної вершини v максимум s вершин передують v в упорядкуванні, які мають v або одну з наступних за нею вершин в околі. Величина вершинного поділу графа G — це мінімальна величина вершинного поділу будь-якого лінійного впорядкування графа G. Величину вершинного поділу ввели Елліс, Садбороу та Тернер, і вона дорівнює шляховій ширині графа G. Це випливає з раніше згаданої еквівалентності інтервальних графів і клікових чисел — якщо G є підграфом інтервального графа I, поданого (як на рисунку) так, що всі кінці інтервалів різні, то порядок лівих кінців інтервалів графа I мають величину вершинного поділу на одиницю меншу за клікове число графа I. З іншого боку, з лінійного впорядкування графа G можна отримати інтервальне подання, в якому ліва кінцева точка інтервалу для вершини v є позицією в упорядкуванні, а права кінцева точка є позицією сусіда v, який в упорядкуванні останній.
Вершинно-пошукове число Гра «пошук вершини» на графі — це вид гри переслідування-ухилення, в якій множина переслідувачів спільно намагаються вистежити втікача, який сховався в графі. Переслідувачі розміщуються у вершинах графа, тоді як утікач може перебувати на будь-якому ребрі графа, його місце розташування і ходи переслідувачам не помітні. Під час чергового ходу деякі (або всі) переслідувачі можуть перейти (довільним чином, не обов'язково уздовж ребер) з однієї вершини в іншу, а втікач рухається потім уздовж будь-якого шляху на графі, але не може проходити через зайняті переслідувачами вершини. Втікач спійманий, коли обидва кінці дуги, на якій він перебуває, зайняті переслідувачами. Вершинно-пошукове число графа — це найменше число переслідувачів, необхідних для гарантованого впіймання втікача незалежно від його поведінки. Як показали Кіроузіс і Пападімітріу, вершинно-пошукове число графа дорівнює його інтервальній товщині. Оптимальною стратегією для переслідувачів є ходи, в яких переслідувачі послідовно утворюють розділювальні множини лінійного впорядкування з мінімальною величиною вершинного поділу.
Межі
Будь-який граф з n вершинами і шляховою шириною k має максимум k(n − k + (k − 1)/2)) ребер, і максимальні графи з шляховою шириною k (графи, до яких не можна додати ребро без збільшення шляхової ширини) мають точно таке число ребер. Максимальний граф з шляховою шириною k повинен бути або k-шляхом, або k-гусеницею, тобто одного з двох особливих видів k-дерева. k-дерево — це хордальный граф з точно n − k максимальними кліками, кожна з яких містить k + 1 вершину. В k-дереві, яке саме не є (k + 1)-клікою, кожна максимальна кліка або ділить граф на дві або більше компоненти, або містить одиничну листову вершину, вершину, яка належить тільки одній максимальній кліці. k-шлях — це k-дерево з максимум двома листками, а k-гусениця — це k-дерево, яке можна поділити на k-шлях і множину k-листків, кожен з яких суміжний з сепаратором k-кліки k-шляху. Зокрема, максимальні графи шляхової ширини одиниця — це точно графи-гусениці.
Оскільки шляхові декомпозиції є особливими випадками деревних декомпозицій, шляхова ширина будь-якого графа більша або дорівнює його деревній ширині. Шляхова ширина також менша або дорівнює ширині розрізу, мінімального числа ребер, які перетинають будь-який перетин між вершинами з меншим індексом і великим індексом в оптимальному лінійному впорядкуванні вершин графа. Це випливає з факту, що величина вершинного поділу, число вершин з меншим індексом з сусідами, що мають більший індекс, не більша від числа розрізаючих ребер. З цієї ж причини ширина розрізу не перевищує шляхової ширини, помноженої на максимальний степінь вершин у даному графі.
Будь-який ліс з n вершинами має шляхову ширину O(log n) Шеффлер () дає сильнішу межу log3(2n + 1) шляхової ширини лісу з n вершинами.. Для лісу можна завжди знайти стале число вершин, видалення яких приводить до лісу, який можна розбити на два менших ліси з максимум 2n/3 вершин у кожному з цих лісів. Лінійне впорядкування, утворене рекурсивним застосуванням такого розбиття, має логарифмічне пошукове число для вершин. Та сама техніка, застосована до деревної декомпозиції графа, показує, що якщо деревна ширина графа G з n вершинами дорівнює t, то шляхова ширина графа G дорівнює O(t log n). Оскільки зовніпланарні графи, паралельно-послідовні графи та графи Халіна всі мають обмежену деревну ширину, всі вони мають максимум логарифмічну шляхову ширину.
Крім того, що шляхова ширина пов'язана з деревною шириною, вона пов'язана з кліковою шириною і шириною розрізу через реберні графи. Реберний граф L(G) графа G має вершину для кожного ребра графа G і дві вершини в L(G) суміжні, якщо відповідні два ребра G мають спільні кінцеві точки. Будь-яке сімейство графів має обмежену шляхову ширину тоді й лише тоді, коли його реберні графи мають обмежену лінійну клікову ширину, де лінійна клікова ширина замінює операцію об'єднання у визначенні клікової ширини на операцію приєднання окремої нової вершини. Якщо зв'язний граф з трьома або більше вершинами має максимальний степінь 3, його ширина розрізу дорівнює величині вершинного поділу його реберного графа.