Наибольшее независимое множество

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

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

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

Источник: Википедия