Доминирующее множество в графе: определение и примеры

Доминирующее множество графа - это набор вершин, который покрывает весь граф: каждая вершина либо выбрана сама, либо соединена ребром хотя бы с одной выбранной. Например, если вершины обозначают устройства, а рёбра - прямые каналы связи, выбор нескольких узлов может обеспечить каждому устройству непосредственного соседа для наблюдения.
Таких наборов обычно много. Важны два разных вопроса: покрывает ли заданный набор все вершины и сколько вершин нужно для этого как минимум? На пути из шести вершин попробуйте включать и выключать узлы: инструмент покажет покрытие и точный минимум для этого конкретного графа.
Определение через окрестности
Пусть - конечный простой неориентированный граф. Множество называют доминирующим, если для каждой вершины выполнено хотя бы одно условие: или у есть сосед из . Рёбра учитываются только на расстоянии одного шага; путь через промежуточную вершину сам по себе не делает её конец соседом.
Открытая окрестность состоит из соседей , а замкнутая окрестность включает саму вершину. Поэтому условие можно записать компактно:
Выбранная вершина покрывает себя независимо от того, есть ли рядом другая выбранная. Для изолированной вершины это особенно важно: её замкнутая окрестность состоит только из неё самой, поэтому она обязательно входит в любое доминирующее множество. Разрозненный граф тоже допустим: каждую его компоненту нужно покрыть отдельно.
Пример: путь из шести вершин
Рассмотрим путь : его рёбра соединяют только соседние числа. Возьмём . У вершины 2 замкнутая окрестность равна , а у вершины 5 - . Объединение этих наборов даёт все шесть вершин, следовательно, доминирует граф.

Для доказательства минимума одной проверки недостаточно. Одна вершина этого пути покрывает не более трёх вершин: себя и максимум двух соседей. Значит, одной вершиной покрыть все шесть нельзя. Мы уже нашли решение из двух, поэтому минимум равен двум. Обозначают его .
Заметим, что для набора вершина 6 остаётся непокрытой: она соседствует с 5, но не с 4. Наличие пути от 4 до 6 не заменяет непосредственное ребро. Чтобы проверить свой вариант, перечислите замкнутую окрестность каждого выбранного узла и найдите их объединение.
Минимальное и наименьшее множество
Минимальное по включению доминирующее множество нельзя уменьшить удалением одной его вершины без потери покрытия. Это локальное условие: никакая выбранная вершина не лишняя. Наименьшее по мощности содержит как можно меньше вершин среди всех доминирующих множеств графа. Его размер и называют числом доминирования .
Наименьшее множество всегда минимально по включению: иначе удаление вершины дало бы меньший допустимый ответ. Обратное неверно. В звезде с центром и тремя листьями множество всех трёх листьев доминирует граф. Если удалить любой лист, он останется непокрытым, так что набор минимален по включению. Но тоже доминирует всю звезду и содержит одну вершину. Значит, минимум равен одному, а минимальное множество из листьев не является наименьшим.
Ту же разницу между локальной максимальностью и наибольшим размером полезно увидеть на примере независимых множеств. При этом независимость запрещает рёбра между выбранными вершинами, а доминирование требует покрыть все вершины: это разные свойства.
Как найти точный ответ перебором
На небольшом графе можно проверять подмножества в порядке увеличения размера:
- Запишите список вершин и соседей каждой вершины, включая саму вершину в её замкнутую окрестность.
- Проверьте пустое множество, затем все одноэлементные, двухэлементные и так далее.
- Для каждого кандидата объедините его замкнутые окрестности. Если объединение совпадает с , кандидат доминирует граф.
- Остановитесь на первом подходящем размере. Любое найденное множество этого размера наименьшее, потому что меньшие размеры уже проверены.
При вершинах всего существует кандидатов, включая пустое множество; подробнее о подсчёте - в статье о числе подмножеств. Для пути из шести вершин это 64 варианта, и инструмент может перебрать их все. Но рост экспоненциальный: такой способ подходит для маленьких примеров, а не для произвольной большой сети.
Если нужно лишь проверить уже заданный набор, перебор не нужен. Отметьте выбранные вершины и всех их соседей, затем проверьте, остались ли неотмеченные. При представлении графа списками смежности это можно сделать за время порядка , включая инициализацию и просмотр графа.
Нижние границы и особые графы
Чтобы доказать оптимальность без полного перебора, полезно отделять построение ответа от оценки снизу. Если максимальная степень графа равна , одна выбранная вершина покрывает не более вершин. Поэтому для графа из вершин необходимо хотя бы выбранных вершин. Перекрытие окрестностей может сделать эту оценку неточной, но опровергнуть её нельзя: даже без перекрытий меньшее количество не покроет все вершины.
Для пути из примера , , и оценка даёт не меньше двух. Найденное множество из двух достигает границы. Для полного графа с хотя бы одной вершиной достаточно любой одной вершины: она соседствует со всеми остальными. В графе без рёбер, напротив, приходится выбрать каждую вершину. Эти крайние случаи помогают проверить, правильно ли в решении учтена сама выбранная вершина.
Для несвязного графа доминирование нельзя перенести через отсутствующее ребро между компонентами. Поэтому число доминирования всего графа равно сумме чисел доминирования его компонент: каждую компоненту надо покрыть независимо, а объединение оптимальных решений компонент покрывает весь граф.
Жадный выбор и сложность задачи
Один практический подход строит покрытие постепенно. Пока есть непокрытые вершины, выберите вершину, чья замкнутая окрестность содержит больше всего ещё непокрытых вершин; добавьте её в ответ и отметьте новое покрытие. Правило выбирает большой текущий выигрыш, однако само по себе не доказывает, что итоговый набор наименьший. При равенстве выигрыш зависит от способа разрешения ничьей.
Идея связана с задачей покрытия множества: множество всех вершин нужно покрыть семейством замкнутых окрестностей. Для точного ответа можно использовать перебор с отсечениями или специализированные алгоритмы. Здесь важно различать две задачи: проверка готового набора быстрая, а поиск самого маленького в общем случае сложнее.
Решающее утверждение «существует ли доминирующее множество размера не больше ?» для произвольного графа NP-полно. Это не доказывает невозможность быстрого решения каждого отдельного графа. Оно означает, что общий полиномиальный алгоритм для всех входов повлёк бы равенство . Формальная постановка и сведение рассмотрены в учебном курсе по теории вычислений.
Связь с другими задачами и применение
В модели мониторинга выбранные узлы контролируют себя и непосредственных соседей. Но это именно модель: реальные ограничения мощности, надёжности и связи могут требовать весов, нескольких наблюдателей или других правил. Прежде чем применять найденный набор, нужно убедиться, что ребро действительно означает возможность прямого покрытия.
На связном невзвешенном графе есть связь с задачей о k центрах: набор не более чем из вершин доминирует граф тогда и только тогда, когда все вершины находятся на расстоянии не более одного ребра от одной из них. В задаче о центрах при фиксированном минимизируют максимальное расстояние; в задаче доминирования фиксируют радиус один и минимизируют число центров. В связном графе расстояния в рёбрах можно найти обходом в ширину.
Доминирующее множество не обязано быть связным: в примере вершины 2 и 5 не соединены ребром. Оно также не обязано быть независимым. Однако всякое максимальное по включению независимое множество доминирует граф: если бы вне него нашлась вершина без выбранных соседей, её можно было бы добавить, сохранив независимость.
Частые ошибки
- Покрывать только соседей. При обычном доминировании выбранная вершина покрывает и себя; требование выбранного соседа для каждой вершины относится к полному доминированию.
- Считать расстояние два соседством. В обычном определении достаточно только одного ребра или совпадения с выбранной вершиной.
- Объявлять первое решение наименьшим. Для минимума нужна нижняя граница или исчерпывающая проверка меньших наборов.
- Забывать изолированные вершины. Каждую такую вершину необходимо выбрать.
- Требовать связности выбранных узлов. Это дополнительное ограничение отдельной задачи, а не часть обычного определения.
FAQ
Может ли доминирующее множество содержать все вершины?
Да. всегда доминирует граф, поскольку каждая вершина уже выбрана. Но обычно интересует меньшее множество.
Всегда ли наименьшее множество единственно?
Нет. Несколько разных наборов могут иметь один и тот же наименьший размер. Достаточно проверить покрытие каждого и доказать, что меньшего набора нет.
Что происходит с изолированной вершиной?
Она входит в любое доминирующее множество: соседей у неё нет, поэтому покрыть её выбором другого узла нельзя.
Коротко
Доминирующее множество покрывает каждую вершину ею самой или её выбранным соседом. Для пути из шести вершин покрывает весь граф, а одной вершины недостаточно, поэтому число доминирования равно двум. Проверка покрытия и доказательство наименьшего размера - разные шаги решения.
Читайте также

Задача о клике: пример и поиск в графе
Задача о клике в графе: определение, пошаговый разбор на пяти вершинах, отличие максимальной клики от наибольшей и объяснение сложности точного поиска.

Гиперграф: что это такое и как его построить
Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

Лемма о рукопожатиях: формула, доказательство и примеры
Лемма о рукопожатиях связывает сумму степеней вершин и число рёбер графа. Разбираем доказательство, нечётные степени, петли и типовые задачи на примерах.

Рёберный граф: построение, свойства и примеры
Рёберный граф простыми словами: как построить его по исходному графу, подсчитать вершины и рёбра, связать паросочетания с независимыми множествами и избежать ошибок.

Алгоритм Хопкрофта-Карпа: паросочетание по фазам
Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе. Разбираем поиск кратчайших цепей, BFS и DFS, пример двух фаз и оценку сложности.

Список смежности: представление графа с примерами
Как построить список смежности графа по рёбрам и восстановить граф по спискам. Разбираем ориентированные и взвешенные графы, сложность операций и отличие от матрицы.