Введение
В теории графов доматическое разбиение графа — это разбиение на непересекающиеся множества V₁, V₂, V₃, ..., таких что каждое Vᵢ является доминирующим множеством для G. На рисунке справа показано доматическое разбиение графа; здесь доминирующее множество V₁ состоит из жёлтых вершин, V₂ — из зелёных вершин, а V₃ — из синих вершин. Доматический номер — это максимальный размер доматического разбиения, то есть максимальное количество непересекающихся доминирующих множеств. Граф на рисунке имеет доматический номер 3. Легко видеть, что доматический номер не меньше 3, поскольку мы привели доматическое разбиение размера 3. Чтобы показать, что доматический номер не больше 3, мы сначала рассмотрим простую верхнюю оценку.
Верхние границы
Пусть δ будет минимальной степенью графа. Доматическое число графа не превосходит Δ+1. Чтобы увидеть это, рассмотрим вершину v степени δ. Пусть S состоит из v и его соседей. Мы знаем, что (1) каждое доминирующее множество должно содержать по крайней мере одну вершину из S (доминирование), и (2) каждая вершина из S содержится не более чем в одном доминирующем множестве (разъединение). Следовательно, существует не более |S| = δ+1 непересекающихся доминирующих множеств. Граф на рисунке имеет минимальную степень δ, и поэтому его доматическое число не превосходит δ+1. Таким образом, мы показали, что его доматическое число равно точно δ+1; на рисунке показано доматическое разбиение максимального размера.
Нижняя граница
Если в графе нет изолированной вершины (то есть, степень каждой вершины ≥ 1), то домтическое число не меньше 2. Это можно увидеть, заметив, что (1) слабое 2-раскрашивание является доматическим разбиением, если в графе нет изолированных вершин, и (2) любое граф имеет слабое 2-раскрашивание. Альтернативно, (1) максимальное независимое множество является доминирующим множеством, и (2) дополнение максимального независимого множества также является доминирующим множеством, если нет изолированных вершин. На рисунке справа показано слабое 2-раскрашивание, которое также является доматическим разбиением размера 2: темные вершины образуют доминирующее множество, а светлые вершины – другое доминирующее множество (светлые вершины образуют максимальное независимое множество). Подробнее о слабом раскрашивании можно узнать в соответствующем разделе.
Комплексность вычислений
Найти доматический раздел размера 1 тривиально: пусть Найти доматический раздел размера 2 (или определить, что он не существует) легко: проверьте, есть ли изолированные вершины, и если нет, найдите слабую 2-раскраску. Однако найти доматический раздел максимального размера вычислительно сложно. В частности, следующая задача принятия решения, известная как задача о доматическом числе, является NP-полной: задан граф и целое число , определите, является ли доматическое число не меньше . Следовательно, задача определения доматического числа данного графа является NP-трудной, и задача нахождения доматического раздела максимального размера также NP-трудна. Существует алгоритм приближения в полиномиальное время с логарифмической гарантией приближения, то есть можно найти доматический раздел, размер которого отличается от оптимального не более чем в раз. Однако, при правдоподобных предположениях теории сложности, не существует алгоритма приближения в полиномиальное время с сублогарифмическим коэффициентом приближения. Более конкретно, алгоритм приближения в полиномиальное время для доматического раздела с коэффициентом приближения для константы повлечет за собой, что все задачи в NP могут быть решены за немного сверхполиномиальное время.