Доматическое число

В теории графов доматическое разбиение графа G = ( V , E ) {displaystyle G=(V,E)} — это разбиение множества вершин V {displaystyle V} на непересекающиеся множества V 1 {displaystyle V_{1}} , V 2 {displaystyle V_{2}} ,..., V K {displaystyle V_{K}} , такие, что каждое множество Vi является доминирующим множеством графа G. Рисунок справа показывает доматическое разбиение графа. На рисунке доминирующее множество V 1 {displaystyle V_{1}} состоит из жёлтых вершин, V 2 {displaystyle V_{2}} состоит из зелёных вершин, а V 3 {displaystyle V_{3}} состоит из синих вершин.

Доматическое число — это максимальный размер доматического разбиения, то есть максимальное число непересекающихся доминирующих множеств. Граф на рисунке имеет доматическое число 3. Легко видеть, что доматическое число не меньше 3, поскольку мы представили доматическое разбиение размером 3. Чтобы понять, что доматическое число не превосходит 3, сначала рассмотрим верхние границы.

Верхние границы

Пусть δ {displaystyle delta } — минимальная степень графа G {displaystyle G} . Доматическое число графа G {displaystyle G} не превосходит δ + 1 {displaystyle delta +1} . Чтобы это понять, рассмотрим вершину v {displaystyle v} степени δ {displaystyle delta } . Пусть N {displaystyle N} состоит из вершины v {displaystyle v} и её соседей. Мы знаем, что (1) каждое доминирующее множество V i {displaystyle V_{i}} должно содержать по меньшей мере одну вершину из N {displaystyle N} (доминирование), и (2) каждая вершина из N {displaystyle N} содержится максимум в одном доминирующем множестве V i {displaystyle V_{i}} (отсутствие пересечений). Таким образом, имеется максимум | N | = δ + 1 {displaystyle |N|=delta +1} непересекающихся доминирующих множеств.

Граф на рисунке имеет минимальную степень δ = 2 {displaystyle delta =2} , а потому его доминирующее число не превосходит 3. Тем самым мы показали, что доматическое число в точности равно 3. Рисунок показывает доматическое разбиение максимального размера.

Нижние границы

Если в графе нет изолированных вершин (то есть, δ {displaystyle delta } ≥ 1), то доматическое число не меньше 2. Чтобы это понять, заметим, что (1) слабая 2-раскраска является доматическим разбиением, если нет изолированных вершин, и (2) любой граф имеет слабую 2-раскраску. Альтернативно, (1) наибольшее независимое множество является доминирующим множеством и (2) дополнение максимального независимого множества также является доминирующим множеством, если нет изолированных вершин.

На рисунке справа показана слабая 2-раскраска, которая является доматическим разбиением размера 2 — тёмные вершины являются доминирующим множеством, а светлые вершины — другим доминирующим множеством (светлые вершины образуют наибольшее независимое множество). См. статью «Слабая раскраска» для дополнительной информации.

Вычислительная сложность

Поиск доматического разбиения размера 1 тривиален — это V 1 = V {displaystyle V_{1}=V} . Найти доматического разбиения размера 2 (или выяснить, что такого разбиения не существует) просто — проверяем, что нет изолированных вершин, и если нет, находим слабую 2-раскраску.

Однако найти доматическое разбиение максимального размера трудно. В частности, следующая задача разрешимости, известная как задача о доматическом числе, является NP-полной: для заданного графа G {displaystyle G} и целого числа K {displaystyle K} определить, меньше или нет доматическое число графа G {displaystyle G} значения K {displaystyle K} . Таким образом, задача определения доматического числа заданного графа является NP-трудной задачей, так что задача нахождения доматического разбиения максимального размера также NP-трудна.

Существует аппроксимационный алгоритм полиномиального времени с логарифмической гарантией аппроксимации, то есть можно найти доматическое разбиение, размер которого находится не далее чем на множитель O ( log ⁡ | V | ) {displaystyle O(log |V|)} от оптимума.

Однако, при имеющих веские основания предположениях, не имеется аппроксимационного алгоритма полиномиального времени с подлогарифмическим аппроксимационным множителем. Конкретнее — аппроксимационный алгоритм полиномиального времени для доматического разбиения с аппроксимационным коэффициентом ( 1 − ϵ ) ln ⁡ | V | {displaystyle (1-epsilon )ln |V|} для константы ϵ > 0 {displaystyle epsilon >0} подразумевает, что все задачи класса NP могут быть решены за слегка суперполиномиальное время n O ( log ⁡ log ⁡ n ) {displaystyle n^{O(log log n)}} .

Сравнение с похожими понятиями

Доматическое разбиение Разбиение вершин на непересекающиеся доминантные множества. Доматическое число — это максимальное число таких множеств. Раскраска вершин Разбиение вершин на непересекающиеся независимые множества. Хроматическое число является минимальным числом таких множеств. Разбиение на клики Разбиение вершин на непересекающиеся клики. Эквивалентно раскраске вершин дополнения графа. Рёберная раскраска Разбиение рёбер на непересекающиеся паросочетания. Рёберное хроматическое число — это минимальное число таких множеств.

Пусть G = (U ∪ V, E) — двудольный граф без изолированных вершин. Все рёбра имеют вид {u, v} ∈ E, где u ∈ U и v ∈ V. Тогда {U, V} является 2-раскраской вершин и доминантным разбиением размера 2. Множества U и V являются независимыми доминирующими множествами. Хроматическое число графа G в точности равно 2. Не существует 1-раскраски вершин. Доминантное число графа G не меньше 2. Может существовать большее доматическое разбиение. Например, полный двудольный граф Kn,n для любого n ≥ 2 имеет доматическое число n.