В теории графов кликовая ширина графа — это параметр, который описывает структурную сложность графа. Параметр тесно связан с древовидной шириной, но, в отличие от древовидной ширины, кликовая ширина может быть ограничена даже для плотных графов. Кликовая ширина определяется как минимальное число меток, необходимых для построения с помощью следующих 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-трудно получить аппроксимацию с сублинейной аддитивной ошибкой. Однако, если верхняя граница кликовой ширины известна, можно получить последовательность построения графа с ограниченной шириной (экспоненциально большей настоящей кликовой ширины) за полиномиальное время. Остаётся открытым вопрос, может ли быть точная кликовая ширина или близкая аппроксимация вычислена за время, может ли быть она вычислена за полиномиальное время для графов с любой фиксированной границей кликовой ширины, или, даже, могут ли графы с кликовой шириной четыре распознаны за полиномиальное время.
Связь с древовидной шириной Теория графов с ограниченной кликовой шириной имеет сходство с теорией графов с ограниченной древовидной шириной, но, в отличие от древовидной ширины, допускает плотные графы. Если семейство графов имеет ограниченную кликовую ширину, то оно либо имеет ограниченную древовидную ширину, либо любой полный двудольный граф является подграфом какого-либо графа в семействе. Древовидная ширина и кликовая ширина также связаны теорией рёберных графов — семейство графов имеет ограниченную древовидную ширину тогда и только тогда, когда их рёберные графы имеют ограниченную кликовую ширину.
Примечания
Литература
.
.
Категория:Инварианты графов