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

Самое большое по размеру максимальное независимое множество называется наибольшим независимым множеством .

Например, в графе P ₃ , пути с тремя вершинами a , b и c и двумя рёбрами ab и bc , множества { b } и { a , c } оба являются максимальными независимыми, из них только { a , c } является наибольшим независимым. Множество { a } независимо, но не максимальное, поскольку является подмножеством { a , c }. В этом же графе максимальными кликами являются множества { a , b } и { b , c }.

Словосочетание «максимальное независимое множество» употребляется также для описания максимальных подмножеств независимых элементов в математических структурах, отличных от графов, в частности, в векторных пространствах и матроидах .

Связь с другими множествами вершин

Если S — максимальное независимое множество в некотором графе, то оно является максимальной кликой в дополнении графа . Максимальная клика — это множество вершин, которые порождают полный подграф , и оно не содержится в большем полном подграфе. Таким образом, это множество вершин S , таких, что любая пара вершин в S соединена ребром, а для любой вершины не из S отсутствует ребро, соединяющее её с хотя бы одной вершиной в S . Граф может иметь несколько максимальных клик различного размера. Поиск максимальной клики максимального размера — это задача о максимальной клике .

Некоторые авторы в определении требуют, чтобы клика была максимальной, и употребляют термин клика вместо максимальная клика.

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

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

Использование в характеристиках семейств графов

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

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

Оценки числа множеств

Мун и Мозер ( ) показали, что любой граф с n вершинами имеет не более 3 ^{n /3} максимальных клик. Также граф с n вершинами имеет не более 3 ^{n /3} максимальных независимых множеств. Граф, имеющий ровно 3 ^{n /3} максимальных независимых множеств, легко построить, просто взяв несвязный набор n /3 треугольных графов . Любое максимальное независимое множество в этом графе образуется выбором одной вершины из каждого треугольника. Дополнительный граф с 3 ^{n /3} максимальными кликами — это графы Турана специального вида. Ввиду связи этого графа с границей Муна и Мозера эти графы иногда называют графами Муна-Мозера. Более сильные границы возможны, если ограничен размер максимальных независимых множеств — число максимальных независимых множеств размера k в любом графе с n вершинами не превосходит

${\displaystyle \lfloor n/k\rfloor ^{k-(n{\bmod {k}})}\lfloor n/k+1\rfloor ^{n{\bmod {k}}}.}$

Графы, достигающие этой границы — это снова графы Турана.

Некоторые семейства графов могут, однако, иметь существенно более сильные границы на число максимальных независимых множеств или максимальных клик. Например, если графы в семействе имеют O(n) рёбер, и семейство замкнуто относительно подграфов, то все максимальные клики имеют постоянный размер и число максимальных клик почти линейно.

Ясно, что любой граф с несводимыми максимальными кликами имеет максимальных клик не больше, чем рёбер. Более сильная граница возможна для интервальных графов и хордальных графов — в этих графах не может быть более n максимальных клик.

Число максимальных независимых множеств в циклах с n вершинами задаётся числами Перрина , а число максимальных независимых множеств в пути с n вершинами задаётся последовательностью Падована . Таким образом, обе эти последовательности пропорциональны степени 1.324718 (то есть пластического числа ).

Алгоритмы перечисления множеств

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

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

Другие более сложные задачи можно свести к поиску клики или независимого множества специального вида. Это даёт мотивацию для поиска алгоритмов, эффективно перечисляющих все максимальные независимые множества (или, что эквивалентно, максимальные клики).

Возможно напрямую превратить доказательство Муна и Мозера границы 3 ^{n /3} числа максимальных независимых множеств в алгоритм, который перечисляет все такие множества за время O(3 ^{n /3} ). Для графов, имеющих максимально возможное число максимальных независимых множеств, этот алгоритм даёт постоянное время на одно найденное множество. Однако алгоритм с этой временной границей может быть крайне неэффективен для графов с более ограниченными количествами независимых множеств. По этой причине многие исследоватили ищут алгоритмы перечисления всех максимальных независимых множеств с полиномиальным временем на одно найденное множество. Время нахождения одного максимального независимого множества пропорционально времени умножения матриц в плотных графах или быстрее в различных классах разреженных графов.

Замечания

Ссылки