EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#теория графов#доминирующее множество#дискретная математика#алгоритмы#покрытие
Доминирующее множество в графе: определение и примеры

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

Таких наборов обычно много. Важны два разных вопроса: покрывает ли заданный набор все вершины и сколько вершин нужно для этого как минимум? На пути из шести вершин попробуйте включать и выключать узлы: инструмент покажет покрытие и точный минимум для этого конкретного графа.

Определение через окрестности

Пусть G=(V,E)G=(V,E) - конечный простой неориентированный граф. Множество D⊆VD\subseteq V называют доминирующим, если для каждой вершины v∈Vv\in V выполнено хотя бы одно условие: v∈Dv\in D или у vv есть сосед из DD. Рёбра учитываются только на расстоянии одного шага; путь через промежуточную вершину сам по себе не делает её конец соседом.

Открытая окрестность N(v)N(v) состоит из соседей vv, а замкнутая окрестность N[v]=N(v)∪{v}N[v]=N(v)\cup\{v\} включает саму вершину. Поэтому условие можно записать компактно:

⋃v∈DN[v]=V.\bigcup_{v\in D}N[v]=V.

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

На пути сначала выбирается вершина 2, затем вершина 5: обратите внимание, как покрытие растёт с трёх вершин до всех шести.

Пример: путь из шести вершин

Рассмотрим путь 1−2−3−4−5−61-2-3-4-5-6: его рёбра соединяют только соседние числа. Возьмём D={2,5}D=\{2,5\}. У вершины 2 замкнутая окрестность равна {1,2,3}\{1,2,3\}, а у вершины 5 - {4,5,6}\{4,5,6\}. Объединение этих наборов даёт все шесть вершин, следовательно, DD доминирует граф.

Путь из шести вершин: выбранные 2 и 5 покрывают соответственно вершины 1–3 и 4–6
Путь из шести вершин: выбранные 2 и 5 покрывают соответственно вершины 1–3 и 4–6

Для доказательства минимума одной проверки недостаточно. Одна вершина этого пути покрывает не более трёх вершин: себя и максимум двух соседей. Значит, одной вершиной покрыть все шесть нельзя. Мы уже нашли решение из двух, поэтому минимум равен двум. Обозначают его γ(G)=2\gamma(G)=2.

Заметим, что для набора {2,4}\{2,4\} вершина 6 остаётся непокрытой: она соседствует с 5, но не с 4. Наличие пути от 4 до 6 не заменяет непосредственное ребро. Чтобы проверить свой вариант, перечислите замкнутую окрестность каждого выбранного узла и найдите их объединение.

Минимальное и наименьшее множество

Минимальное по включению доминирующее множество нельзя уменьшить удалением одной его вершины без потери покрытия. Это локальное условие: никакая выбранная вершина не лишняя. Наименьшее по мощности содержит как можно меньше вершин среди всех доминирующих множеств графа. Его размер и называют числом доминирования γ(G)\gamma(G).

Наименьшее множество всегда минимально по включению: иначе удаление вершины дало бы меньший допустимый ответ. Обратное неверно. В звезде с центром cc и тремя листьями a,b,da,b,d множество всех трёх листьев доминирует граф. Если удалить любой лист, он останется непокрытым, так что набор минимален по включению. Но {c}\{c\} тоже доминирует всю звезду и содержит одну вершину. Значит, минимум равен одному, а минимальное множество из листьев не является наименьшим.

Ту же разницу между локальной максимальностью и наибольшим размером полезно увидеть на примере независимых множеств. При этом независимость запрещает рёбра между выбранными вершинами, а доминирование требует покрыть все вершины: это разные свойства.

Как найти точный ответ перебором

На небольшом графе можно проверять подмножества в порядке увеличения размера:

  1. Запишите список вершин и соседей каждой вершины, включая саму вершину в её замкнутую окрестность.
  2. Проверьте пустое множество, затем все одноэлементные, двухэлементные и так далее.
  3. Для каждого кандидата объедините его замкнутые окрестности. Если объединение совпадает с VV, кандидат доминирует граф.
  4. Остановитесь на первом подходящем размере. Любое найденное множество этого размера наименьшее, потому что меньшие размеры уже проверены.

При nn вершинах всего существует 2n2^n кандидатов, включая пустое множество; подробнее о подсчёте - в статье о числе подмножеств. Для пути из шести вершин это 64 варианта, и инструмент может перебрать их все. Но рост экспоненциальный: такой способ подходит для маленьких примеров, а не для произвольной большой сети.

Если нужно лишь проверить уже заданный набор, перебор не нужен. Отметьте выбранные вершины и всех их соседей, затем проверьте, остались ли неотмеченные. При представлении графа списками смежности это можно сделать за время порядка O(∣V∣+∣E∣)O(|V|+|E|), включая инициализацию и просмотр графа.

Нижние границы и особые графы

Чтобы доказать оптимальность без полного перебора, полезно отделять построение ответа от оценки снизу. Если максимальная степень графа равна Δ\Delta, одна выбранная вершина покрывает не более Δ+1\Delta+1 вершин. Поэтому для графа из nn вершин необходимо хотя бы ⌈n/(Δ+1)⌉\lceil n/(\Delta+1)\rceil выбранных вершин. Перекрытие окрестностей может сделать эту оценку неточной, но опровергнуть её нельзя: даже без перекрытий меньшее количество не покроет все вершины.

Для пути из примера n=6n=6, Δ=2\Delta=2, и оценка даёт не меньше двух. Найденное множество из двух достигает границы. Для полного графа с хотя бы одной вершиной достаточно любой одной вершины: она соседствует со всеми остальными. В графе без рёбер, напротив, приходится выбрать каждую вершину. Эти крайние случаи помогают проверить, правильно ли в решении учтена сама выбранная вершина.

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

Жадный выбор и сложность задачи

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

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

Решающее утверждение «существует ли доминирующее множество размера не больше kk?» для произвольного графа NP-полно. Это не доказывает невозможность быстрого решения каждого отдельного графа. Оно означает, что общий полиномиальный алгоритм для всех входов повлёк бы равенство P=NPP=NP. Формальная постановка и сведение рассмотрены в учебном курсе по теории вычислений.

Связь с другими задачами и применение

В модели мониторинга выбранные узлы контролируют себя и непосредственных соседей. Но это именно модель: реальные ограничения мощности, надёжности и связи могут требовать весов, нескольких наблюдателей или других правил. Прежде чем применять найденный набор, нужно убедиться, что ребро действительно означает возможность прямого покрытия.

На связном невзвешенном графе есть связь с задачей о k центрах: набор не более чем из kk вершин доминирует граф тогда и только тогда, когда все вершины находятся на расстоянии не более одного ребра от одной из них. В задаче о центрах при фиксированном kk минимизируют максимальное расстояние; в задаче доминирования фиксируют радиус один и минимизируют число центров. В связном графе расстояния в рёбрах можно найти обходом в ширину.

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

Частые ошибки

  • Покрывать только соседей. При обычном доминировании выбранная вершина покрывает и себя; требование выбранного соседа для каждой вершины относится к полному доминированию.
  • Считать расстояние два соседством. В обычном определении достаточно только одного ребра или совпадения с выбранной вершиной.
  • Объявлять первое решение наименьшим. Для минимума нужна нижняя граница или исчерпывающая проверка меньших наборов.
  • Забывать изолированные вершины. Каждую такую вершину необходимо выбрать.
  • Требовать связности выбранных узлов. Это дополнительное ограничение отдельной задачи, а не часть обычного определения.

FAQ

Может ли доминирующее множество содержать все вершины?

Да. D=VD=V всегда доминирует граф, поскольку каждая вершина уже выбрана. Но обычно интересует меньшее множество.

Всегда ли наименьшее множество единственно?

Нет. Несколько разных наборов могут иметь один и тот же наименьший размер. Достаточно проверить покрытие каждого и доказать, что меньшего набора нет.

Что происходит с изолированной вершиной?

Она входит в любое доминирующее множество: соседей у неё нет, поэтому покрыть её выбором другого узла нельзя.

Коротко

Доминирующее множество покрывает каждую вершину ею самой или её выбранным соседом. Для пути из шести вершин {2,5}\{2,5\} покрывает весь граф, а одной вершины недостаточно, поэтому число доминирования равно двум. Проверка покрытия и доказательство наименьшего размера - разные шаги решения.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Задача о клике: пример и поиск в графе

Задача о клике: пример и поиск в графе

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

8 ноября 20268 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

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

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

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

8 ноября 20267 минут
Рёберный граф: построение, свойства и примеры

Рёберный граф: построение, свойства и примеры

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

8 ноября 20268 минут
Алгоритм Хопкрофта-Карпа: паросочетание по фазам

Алгоритм Хопкрофта-Карпа: паросочетание по фазам

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

8 ноября 20268 минут
Список смежности: представление графа с примерами

Список смежности: представление графа с примерами

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

8 ноября 20268 минут