Maximal independent set

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

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