Клікова ширина

Матеріал з testwiki
Перейти до навігації Перейти до пошуку
Побудова дистанційно-успадковуваного графа клікової ширини 3 незв'язним об'єднанням, перейменуванням вершин і об'єднанням міток. Мітки вершин показано кольорами.

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

  1. Створення нової вершини v з міткою i (операція i(v))
  2. Незв'язне об'єднання двох розмічених графів G і H (операція G⊕H)
  3. З'єднання ребром кожної вершини з міткою i з кожною вершиною з міткою j (операція η(i, j)), де i≠j
  4. Перейменування мітки i на j (операція ρ(i,j))

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

Послідовності побудови, на які спирається поняття клікової ширини, сформулювали Курсель, Енгельфрід і Розенберг у 1990Шаблон:Sfn і ВанкеШаблон:Sfn. Назву «клікова ширина» використала для іншої концепції ХлєбіковаШаблон:Sfn. Від 1993 термін став уживатися в сучасному значенніШаблон:Sfn.

Особливі класи графів

Кографи — це точно графи з кліковою шириною, що не перевищує двохШаблон:Sfn. Будь-який дистанційно-успадковуваний граф має клікову ширину, що не перевищує 3. Однак клікова ширина інтервальних графів не обмежена (згідно зі структурою ґратки)Шаблон:Sfn. Так само не обмежена клікова ширина двочасткових графів перестановок (згідно з подібною структурою ґратки)Шаблон:Sfn. Ґрунтуючись на описі кографів як графів без породжених підграфів, ізоморфних шляхам без хорд, класифіковано клікову ширину багатьох класів графів, визначених забороненими породженими підграфамиШаблон:SfnШаблон:Sfn.

Інші графи з обмеженою кліковою шириною — Шаблон:Mvar-Шаблон:Не перекладено для обмежених значень Шаблон:Mvar, тобто породжені підграфи листків дерева Шаблон:Mvar у степені графа Шаблон:Math. Однак степінь листків за необмеженого показника степеня не має обмеженої ширини листківШаблон:SfnШаблон:Sfn.

Межі

Курсель і ОларуШаблон:Sfn, а також Корнейл і РотіксШаблон:Sfn, дали такі межі клікової ширини деяких графів:

Крім того, якщо граф Шаблон:Mvar має клікову ширину Шаблон:Mvar, то степінь графа Шаблон:Math має клікову ширину, що не перевищує Шаблон:MathШаблон:Sfn. Хоча в нерівностях для клікової ширини в порівняннях з деревною шириною та степенем графа присутня експонента, ці межі не дають суперпозиції — якщо граф Шаблон:Mvar має деревну ширину Шаблон:Mvar, то Шаблон:Math має клікову ширину, що не перевершує Шаблон:Math, лише проста експонента від деревної шириниШаблон:Sfn.

Обчислювальна складність

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

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

Зв'язок з деревною шириною

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

Див. також

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

  1. ↑ Шаблон:Sfn0, Усиление — Шаблон:Sfn0, Theorem 5.5.
Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Клікова_ширина&oldid=8754