Максимальное независимое множество в графе: разбор

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

Что такое независимое множество вершин

Пусть дан неориентированный граф $G = (V, E)$. Множество вершин $S \subseteq V$ называется независимым (или внутренне устойчивым), если никакие две вершины из $S$ не соединены ребром:

$\forall\, u, v \in S \colon \{u, v\} \notin E.$

Иными словами, $S$ - это набор попарно несмежных вершин. Пустое множество и любая одиночная вершина всегда независимы, поэтому интерес представляют максимально возможные по размеру такие наборы. Содержательно независимое множество моделирует «совместимый» выбор: если ребро означает конфликт, то независимое множество - это объекты, которые можно взять одновременно без противоречий.

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

Максимальное и наибольшее: в чём разница

Это место, где чаще всего возникает путаница, потому что в русской терминологии два разных понятия звучат похоже.

Максимальное (по включению) независимое множество - такое $S$, к которому нельзя добавить ни одной вершины, не нарушив независимости. То есть каждая вершина вне $S$ смежна хотя бы с одной вершиной из $S$. Это локальное свойство: множество «насыщено».

Наибольшее независимое множество - такое $S$, размер которого максимален среди всех независимых множеств графа. Его мощность называют числом независимости и обозначают $\alpha(G)$:

$\alpha(G) = \max\{\,|S| : S \subseteq V,\ S \text{ независимо}\,\}.$

Любое наибольшее множество автоматически максимально по включению, но обратное неверно. Классический пример - путь $P_4$ из четырёх вершин $a - b - c - d$. Множество $\{b\}$ дополнить нельзя ($b$ смежна с $a$ и $c$, а $d$… здесь нюанс: $\{b\}$ как раз не максимально, его можно расширить до $\{b, d\}$). А вот $\{a, c\}$ - максимально по включению и наибольшее, $\alpha(P_4) = 2$. Зато в звезде «коготь» $K_{1,3}$ центр $\{c\}$ образует максимальное по включению множество размера $1$, тогда как наибольшее - это три листа, $\alpha = 3$. Локально насыщенное множество может быть в разы меньше глобального оптимума.

Число независимости, клика и вершинное покрытие

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

Клика. Множество вершин, попарно соединённых рёбрами, называется кликой. Независимое множество в графе $G$ - это в точности клика в его дополнении $\overline{G}$ (граф на тех же вершинах, где рёбра ровно там, где их не было в $G$). Отсюда фундаментальное равенство для кликового числа $\omega$:

$\alpha(G) = \omega(\overline{G}).$

Вершинное покрытие. Множество $C \subseteq V$ - вершинное покрытие, если каждое ребро имеет хотя бы один конец в $C$. Дополнение независимого множества всегда является вершинным покрытием, и наоборот. Это даёт теорему Галлаи:

$\alpha(G) + \tau(G) = |V|,$

где $\tau(G)$ - размер наименьшего вершинного покрытия. Поэтому, найдя наибольшее независимое множество, вы бесплатно получаете и минимальное покрытие как $V \setminus S$. Подробнее метрики структуры графа разбираются в материале про эксцентриситет вершины графа.

Как искать множество вручную

Для небольших графов работает прямой перебор с отсечениями.

1. Постройте список смежности: для каждой вершины - её соседи.
2. Жадно соберите одно максимальное по включению множество: берите вершину, удаляйте её и всех соседей, повторяйте. Это даст нижнюю оценку для $\alpha(G)$.
3. Чтобы убедиться, что найдено именно наибольшее, переберите подмножества убывающего размера или используйте ветвление: выберите вершину $v$ - либо она в множестве (тогда соседи исключаются), либо нет (тогда обязана войти хотя бы одна из её соседей или сама $v$ покрывается покрытием).

Например, в цикле $C_5$ (пятиугольник $1{-}2{-}3{-}4{-}5{-}1$) жадность из вершины $1$ даёт $\{1, 3\}$, добавить нечего - это максимальное по включению множество размера $2$. И действительно $\alpha(C_5) = 2$: три попарно несмежные вершины в пятиугольнике не помещаются. А в цикле $C_6$ ответ уже $\{1, 3, 5\}$, то есть $\alpha(C_6) = 3$.

Сложность задачи и точные алгоритмы

Поиск наибольшего независимого множества - NP-трудная задача; соответствующая задача распознавания «есть ли независимое множество размера $\ge k$» NP-полна. Поэтому полиномиального алгоритма для произвольных графов не известно, и точные методы экспоненциальны в худшем случае.

Базовый точный подход - ветвление по вершине: выбираем вершину $v$ максимальной степени и рассматриваем два случая - $v$ входит в множество (удаляем $v$ и всех её соседей) либо не входит (удаляем только $v$). Рекурсия с такими отсечениями работает заметно быстрее наивного перебора $2^n$ подмножеств; лучшие известные алгоритмы дают порядка $O(1{,}19^n)$. Для разреженных графов и графов с малой шириной дерева существуют полиномиальные методы.

Приближённые и жадные методы

Поскольку точное решение дорого, на больших графах применяют эвристики:

• Жадный по минимальной степени: на каждом шаге берём вершину с наименьшим числом соседей, добавляем в $S$, удаляем её вместе с соседями. Часто даёт хороший результат на разреженных графах.
• Локальный поиск (2-improvement): пытаемся заменить одну вершину множества на две несмежные снаружи - увеличивая $|S|$.
• Для планарных графов существует схема приближения с любой точностью; для общего случая задача плохо приближается - гарантированное приближение лучше $n^{1-\varepsilon}$ невозможно (при $\text{P} \ne \text{NP}$).

Где это применяется

Модель «вершины - объекты, рёбра - конфликты» встречается повсеместно. Планирование непересекающихся событий сводится к независимому множеству в графе пересечений интервалов (там, кстати, задача решается жадно за полиномиальное время). Распределение частот в беспроводных сетях, выбор несоседних клеток, отбор признаков без сильной корреляции, упаковка в комбинаторике - всё это варианты одной задачи.

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

• Путают «максимальное» и «наибольшее». Жадно собранное насыщенное множество максимально по включению, но почти никогда не равно $\alpha(G)$.
• Считают одиночную вершину независимым множеством «по умолчанию максимальным». Максимальность нужно проверять: либо нельзя добавить вершину (по включению), либо доказать оптимальность размера.
• Забывают про изолированные вершины. Вершина без рёбер обязана входить в любое наибольшее независимое множество - её всегда выгодно взять.
• Применяют жадный алгоритм и считают результат точным. Жадность даёт лишь оценку снизу для $\alpha(G)$, а не гарантированный оптимум.
• Игнорируют связь с покрытием. Проверить ответ легко: $V \setminus S$ должно быть вершинным покрытием, и $|S| + |C| = n$.

FAQ

Чем отличается независимое множество от вершинного покрытия? Это дополняющие понятия. $S$ независимо тогда и только тогда, когда $V \setminus S$ - вершинное покрытие. Наибольшему независимому множеству соответствует наименьшее покрытие, и их размеры в сумме дают число вершин: $\alpha(G) + \tau(G) = n$.

Как число независимости связано с кликой? Независимое множество в $G$ - это клика в дополнении $\overline{G}$, поэтому $\alpha(G) = \omega(\overline{G})$. Любой алгоритм поиска клики работает и для независимого множества, если запустить его на дополнении графа.

Всегда ли наибольшее множество единственно? Нет. Граф может иметь несколько разных наибольших независимых множеств одного размера $\alpha(G)$. Например, в полном двудольном графе $K_{n,n}$ обе доли - наибольшие множества размера $n$.

Коротко

Независимое множество - набор попарно несмежных вершин; максимальное по включению нельзя расширить, наибольшее имеет максимальный размер $\alpha(G)$ (число независимости). Оно дополняет минимальное вершинное покрытие ($\alpha + \tau = n$) и равно клике в дополнении графа ($\alpha(G) = \omega(\overline{G})$). Поиск наибольшего множества NP-труден: на малых графах решается ветвлением и перебором, на больших - жадными эвристиками и локальным поиском, дающими лишь оценку снизу.