В теории графов максимальным независимым множеством, максимальным устойчивым множеством, или максимальным стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Максимальное независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть максимальным независимым, поэтому максимальные независимые множества также называют независимыми доминирующими множествами. Граф может иметь много максимальных независимых множеств в широком диапазоне размеров.[1]
Самое большое по размеру максимальное независимое множество называется наибольшим независимым множеством.
Например, в графе P3, пути с тремя вершинами a, b и c и двумя рёбрами ab и bc, множества {b} и {a,c} оба являются максимальными независимыми, из них только {a,c} является наибольшим независимым. Множество {a} независимо, но не максимальное, поскольку является подмножеством {a,c}. В этом же графе максимальными кликами являются множества {a,b} и {b,c}.
Словосочетание «максимальное независимое множество» употребляется также для описания максимальных подмножеств независимых элементов в математических структурах, отличных от графов, в частности, в векторных пространствах и матроидах.
Если S — максимальное независимое множество в некотором графе, то оно является максимальной кликой в дополнении графа. Максимальная клика — это множество вершин, которые порождают полный подграф, и оно не содержится в большем полном подграфе. Таким образом, это множество вершин S, таких, что любая пара вершин в S соединена ребром, а для любой вершины не из S отсутствует ребро, соединяющее её с хотя бы одной вершиной в S. Граф может иметь несколько максимальных клик различного размера. Поиск максимальной клики максимального размера — это задача о максимальной клике.
Некоторые авторы в определении требуют, чтобы клика была максимальной, и употребляют термин клика вместо максимальная клика.