Русская Википедия:Кликовая ширина

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Clique-width construction.svg
Построение дистанционно-наследуемуего графа кликовой ширины 3 путём несвязного объединения, переименования вершин и объединения меток. Метки вершин показаны цветом.

В теории графов кликовая ширина графа <math>G</math> — это параметр, который описывает структурную сложность графа. Параметр тесно связан с древесной шириной, но, в отличие от древесной ширины, кликовая ширина может быть ограничена даже для плотных графов. Кликовая ширина определяется как минимальное число меток, необходимых для построения <math>G</math> с помощью следующих 4 операций

  1. Создание новой вершины v с меткой i (операция i(v))
  2. Несвязное объединение двух размеченных графов G и H (операция <math>G \oplus H</math>)
  3. Соединение ребром каждой вершины с меткой i с каждой вершиной с меткой j (операция η(i, j)), где <math>i \neq j</math>
  4. Переименование метки i в j (операция ρ(i,j))

В графы с ограниченной кликовой шириной входят кографы и дистанционно-наследуемые графы. Хотя вычисление кликовой ширины является NP-трудной задачей, при условии, что верхняя граница не известна, и неизвестно, можно ли её вычислить за полиномиальное время, когда верхняя граница известна, эффективные аппроксимационные алгоритмы вычисления кликовой ширины известны. Опираясь на эти алгоритмы и теорему Курселя, многие оптимизационные задачи на графах, NP-трудные для произвольных графов, могут быть решены или аппроксимированы быстро для графов с ограниченной кликовой шириной.

Последовательности построения, на которые опирается понятие кликовой ширины, сформулировали Курсель, Энгельфрид и Розенберг в 1990Шаблон:Sfn и ВанкеШаблон:Sfn. Название «кликовая ширина» использовала для другой концепции ХлебиковаШаблон:Sfn. С 1993 термин стал употребляться в современном значенииШаблон:Sfn.

Специальные классы графов

Кографы — это в точности графы с кликовой шириной, не превосходящей двухШаблон:Sfn. Любой дистанционно-наследуемый граф имеет кликовую ширину, не превосходящую 3. Однако кликовая ширина интервальных графов не ограничена (согласно структуре решётки)Шаблон:Sfn . Подобным же образом не ограничена кликовая ширина двудольных перестановочных графов (согласно подобной структуре решётки)Шаблон:Sfn. Основываясь на описании кографов как графов без порождённых подграфов, изоморфных путям без хорд, была классифицирована кликовая ширина многих классов графов, определённых запрещёнными порождёнными подграфамиШаблон:SfnШаблон:Sfn.

Другие графы с ограниченной кликовой шириной — Шаблон:Mvar-Шаблон:Не переведено 5 для ограниченных значений Шаблон:Mvar, то есть порождённые подграфы листьев дерева Шаблон:Mvar в степени графа Шаблон:Math. Однако степень листьев при неограниченном показателе степени не имеет ограниченной ширины листьевШаблон:SfnШаблон:Sfn.

Границы

Курсель и ОлариуШаблон:Sfn, а также Корнейл и РотиксШаблон:Sfn, дали следующие границы кликовой ширины некоторых графов:

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

Вычислительная сложность

Шаблон:Unsolved Многие задачи оптимизации, NP-трудные для более общих классов графов, могут быть решены эффективно с помощью динамического программирования на графах с ограниченной кликовой шириной, если последовательность построения этих графов известнаШаблон:SfnШаблон:Sfn. В частности, любой инвариант графа, который может быть выражен в MSO1 (Шаблон:Не переведено 5, вид логики второго порядка, позволяющая кванторы над множествами вершин) имеет алгоритм линейного времени для графов с ограниченной шириной по одной из формулировок теоремы КурселяШаблон:Sfn. Можно также найти оптимальные раскраски или гамильтоновы циклы графов с ограниченной кликовой шириной за полиномиальное время, если последовательность построения графа известна, но степень полинома увеличивается с увеличением кликовой ширины, и доводы из теории вычислительной сложности показывают, что такая зависимость, похоже, неизбежнаШаблон:Sfn.

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

Связь с древесной шириной

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Sfn0, Усиление — Шаблон:Sfn0, Theorem 5.5.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Кликовая_ширина&oldid=10129839