В теории графов доматическое разбиение графа — это разбиение на непересекающиеся множества , ,..., такое, что каждое V i является доминирующим множеством для G. На рисунке справа показано доматическое разбиение графа; здесь доминирующее множество состоит из желтых вершин, состоит из зеленых вершин и состоит из синих вершин.
Число доматика — это максимальный размер доматического разбиения, то есть максимальное количество непересекающихся доминирующих множеств. Граф на рисунке имеет число доматика 3. Легко видеть, что число доматика не менее 3, поскольку мы представили разбиение доматика размером 3. Чтобы увидеть, что число доматика не более 3, мы сначала рассмотрим простую верхнюю границу.
Пусть будет минимальной степенью графа . Доматическое число не более . Чтобы увидеть это, рассмотрим вершину степени . Пусть состоит из и ее соседей. Мы знаем, что (1) каждое доминирующее множество должно содержать по крайней мере одну вершину из (доминирование), и (2) каждая вершина из содержится не более чем в одном доминирующем множестве (непересекаемость). Следовательно, существует не более чем непересекающиеся доминирующие множества.
Граф на рисунке имеет минимальную степень , и поэтому его доматическое число не превышает 3. Таким образом, мы показали, что его доматическое число равно ровно 3; на рисунке показано домашнее разбиение максимального размера.
Если в графе нет изолированных вершин (то есть ≥ 1), то доматическое число не менее 2. Чтобы увидеть это, обратите внимание, что (1) слабая 2-раскраска является доматической разбивкой, если нет изолированных вершин, и (2) любой граф имеет слабую 2-раскраску. Альтернативно, (1) максимальное независимое множество является доминирующим множеством, и (2) дополнение максимального независимого множества также является доминирующим множеством, если нет изолированных вершин.
На рисунке справа показана слабая 2-раскраска, которая также является домашним разбиением размера 2: темные узлы являются доминирующим набором, а светлые узлы являются другим доминирующим набором (светлые узлы образуют максимальный независимый набор). См. слабую раскраску для получения дополнительной информации.
Найти доматическое разбиение размера 1 тривиально: пусть . Найти доматическое разбиение размера 2 (или определить, что его не существует) легко: проверьте, есть ли изолированные узлы, и если нет, найдите слабую 2-раскраску.
Однако нахождение домашнего разбиения максимального размера является вычислительно сложным. В частности, следующая задача принятия решений , известная как задача домашнего числа , является NP-полной : для заданного графа и целого числа определить, является ли домашнее число не менее . Таким образом, задача определения домашнего числа заданного графа является NP-сложной , и задача нахождения домашнего разбиения максимального размера также является NP-сложной.
Существует полиномиальный алгоритм аппроксимации с гарантией логарифмической аппроксимации [1] , то есть можно найти доматическое разбиение, размер которого находится в пределах множителя от оптимального.
Однако при правдоподобных предположениях теории сложности не существует полиномиального алгоритма аппроксимации с сублогарифмическим фактором аппроксимации. [1] Более конкретно, полиномиальный алгоритм аппроксимации для домашнего разбиения с константным фактором аппроксимации означал бы, что все задачи в NP могут быть решены за слегка сверхполиномиальное время .
Пусть G = ( U ∪ V , E ) — двудольный граф без изолированных узлов; все ребра имеют вид { u , v } ∈ E с u ∈ U и v ∈ V . Тогда { U , V } является как вершинной 2-раскраской, так и доматическим разбиением размера 2; множества U и V являются независимыми доминирующими множествами. Хроматическое число графа G равно ровно 2; вершинной 1-раскраски не существует. Доматическое число графа G равно по крайней мере 2. Возможно, что существует большее доматическое разбиение; например, полный двудольный граф K n , n для любого n ≥ 2 имеет доматическое число n .
