В теорії графів клікова ширина графа — це параметр, який описує структурну складність графа. Параметр тісно пов'язаний з деревною шириною, але, на відміну від деревної ширини, клікова ширина може бути обмеженою навіть для щільних графів. Клікова ширина визначається як мінімальна кількість міток, необхідних для побудови за допомогою таких 4 операцій:
Створення нової вершини v з міткою i (операція i(v)) Незв'язне об'єднання двох розмічених графів G і H (операція ) З'єднання ребром кожної вершини з міткою i з кожною вершиною з міткою j (операція η(i, j)), де Перейменування мітки i на j (операція ρ(i,j))
До графів з обмеженою кліковою шириною належать кографи і дистанційно-успадковувані графи. Хоча обчислення клікової ширини є NP-складною задачею, за умови, що верхня межа не відома, і невідомо, чи можна її обчислити за поліноміальний час, коли верхня межа відома, ефективні апроксимаційні алгоритми обчислення клікової ширини відомі. Спираючись на ці алгоритми і теорему Курселя, багато оптимізаційних задач на графах, NP-складних для довільних графів, можна розв'язати або швидко апроксимувати для графів з обмеженою кліковою шириною.
Послідовності побудови, на які спирається поняття клікової ширини, сформулювали Курсель, Енгельфрід і Розенберг у 1990 і Ванке. Назву «клікова ширина» використала для іншої концепції Хлєбікова. Від 1993 термін став уживатися в сучасному значенні.
Особливі класи графів Кографи — це точно графи з кліковою шириною, що не перевищує двох. Будь-який дистанційно-успадковуваний граф має клікову ширину, що не перевищує 3. Однак клікова ширина інтервальних графів не обмежена (згідно зі структурою ґратки). Так само не обмежена клікова ширина двочасткових графів перестановок (згідно з подібною структурою ґратки). Ґрунтуючись на описі кографів як графів без породжених підграфів, ізоморфних шляхам без хорд, класифіковано клікову ширину багатьох класів графів, визначених забороненими породженими підграфами.
Інші графи з обмеженою кліковою шириною — - для обмежених значень , тобто породжені підграфи листків дерева у степені графа . Однак степінь листків за необмеженого показника степеня не має обмеженої ширини листків.
Межі Курсель і Олару, а також Корнейл і Ротікс, дали такі межі клікової ширини деяких графів:
Якщо граф має клікову ширину максимум , то те саме істинне для будь-якого породженого підграфа графа. Доповнення графа з кліковою шириною має клікову ширину, що не перевищує . Графи з деревною шириною мають клікову ширину, що не перевищує . Експоненційна залежність у межі необхідна — існують графи, клікова ширина яких експоненційно більша від їхньої деревної ширини, Усиление — , Theorem 5.5.. З іншого боку, графи з обмеженою кліковою шириною можуть мати необмежену деревну ширину. Наприклад, повні графи з вершинами мають клікову ширину 2, але деревну ширину . Однак, графи з кліковою шириною , які не містять повного двочасткового графа як підграфа, мають деревну ширину, що не перевищує . Таким чином, для будь-якого сімейства розріджених графів наявність обмеження деревної ширини еквівалентне наявності обмеження клікової ширини. Інший параметр графів, рангова ширина, обмежена в обох напрямках кліковою шириною: рангова ширина ≤ клікової ширини ≤ 2рангової ширини + 1 .
Крім того, якщо граф має клікову ширину , то степінь графа має клікову ширину, що не перевищує . Хоча в нерівностях для клікової ширини в порівняннях з деревною шириною та степенем графа присутня експонента, ці межі не дають суперпозиції — якщо граф має деревну ширину , то має клікову ширину, що не перевершує , лише проста експонента від деревної ширини.
Обчислювальна складність
Багато задачі оптимізації, NP-складні для більш загальних класів графів, можна ефективно розв'язати за допомогою динамічного програмування на графах з обмеженою кліковою шириною, якщо послідовність побудови цих графів відома. Зокрема, будь-який інваріант графа, який можна виразити в MSO1 (, вид логіки другого порядку, що дозволяє квантори над множинами вершин) має алгоритм лінійного часу для графів з обмеженою шириною за одним із формулювань теореми Курселя. Можна також знайти оптимальні розмальовки або гамільтонові цикли графів з обмеженою кліковою шириною за поліноміальний час, якщо послідовність побудови графа відома, але степінь полінома збільшується зі збільшенням клікової ширини, і доводи з теорії обчислювальної складності показують, що така залежність, схоже, неминуча.
Графи з кліковою шириною три можна розпізнати і послідовність їх побудови можна знайти за поліноміальний час за допомогою алгоритму, заснованого на . Для класів графів з необмеженою кліковою шириною точне обчислення клікової ширини є NP-складною задачею, а також NP-складно отримати апроксимацію з сублінійною адитивною помилкою. Однак, якщо верхня межа клікової ширини відома, можна отримати послідовність побудови графа з обмеженою шириною (експоненціально більшою від справжньої клікової ширини) за поліноміальний час. Залишається відкритим питання, чи можна точну клікову ширину або близьку апроксимацію обчислити за час, чи можна її обчислити за поліноміальний час для графів з будь-якою фіксованою межею клікової ширини, або, навіть, чи можна графи з кліковою шириною чотири розпізнати за поліноміальний час.
Зв'язок з деревною шириною Теорія графів з обмеженою кліковою шириною подібна до теорії графів з обмеженою деревною шириною, але, на відміну від деревної ширини, допускає щільні графи. Якщо сімейство графів має обмежену клікову ширину, то воно або має обмежену деревну ширину, або будь-який повний двочастковий граф є підграфом якогось графа в сімействі. Деревна ширина і клікова ширина також пов'язані теорією реберних графів — родина графів має обмежену деревну ширину тоді й лише тоді, коли їхні реберні графи мають обмежену клікову ширину.
Див. також Деревна ширина Шляхова ширина графа
Примітки
Література
.
.