Число диссоциации — характеристика заданного графа , равная наибольшему числу вершин в его диссоциациях — подмножествах вершин, порождающих подграф с максимальной степенью 1. Стандартное обозначение — .
Задачу вычисления числа диссоциации исследовал Яннакакис в 1981—1982 годы, установив её NP-трудность даже в классе двудольных и планарных графов. В 2022 году опубликован алгоритм вычисления 4/3-аппроксимации числа диссоциации двудольного графа.
Определение числа диссоциации является специальным случаем (для ) более общей задачи о максимальном -зависимом множестве: определить размер наибольшего подмножества вершин графа , такого, что порождённый граф имеет максимальную степень .
Примечания
Литература
Категория:Инварианты графов