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

В теории графов кликовая ширина графа — это параметр, который описывает структурную сложность графа. Параметр тесно связан с древесной шириной, но, в отличие от древесной ширины, кликовая ширина может быть ограничена даже для плотных графов.Кликовая ширина определяется как минимальное число меток, необходимых для построения с помощью следующих 4 операций 1. * Создание новой вершины v с меткой i (операция i(v)) 2. * Несвязное объединение двух размеченных графов G и H (операция ) 3. * Соединение ребром каждой вершины с меткой i с каждой вершиной с меткой j (операция η(i, j)), где 4. * Переименование метки i в j (операция ρ(i,j)) В графы с ограниченной кликовой шириной входят кографы и дистанционно-наследуемые графы. Хотя вычисление кликовой ширины является NP-трудной задачей, при условии, что верхняя граница не известна, и неизвестно, можно ли её вычислить за полиномиальное время, когда верхняя граница известна, эффективные аппроксимационные алгоритмы вычисления кликовой ширины известны.Опираясь на эти алгоритмы и теорему Курселя, многие оптимизационные задачи на графах, NP-трудные для произвольных графов, могут быть решены или аппроксимированы быстро для графов с ограниченной кликовой шириной. Последовательности построения, на которые опирается понятие кликовой ширины, сформулировали Курсель, Энгельфрид и Розенберг в 1990 и Ванке. Название «кликовая ширина» использовала для другой концепции Хлебикова. С 1993 термин стал употребляться в современном значении.