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

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

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

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

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

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

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

Мун и Мозер (Moon, Moser 1965) показали, что любой граф с 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}}}.}$

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

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

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

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

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

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

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

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