In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets. A graph may have many maximal independent sets of widely varying sizes; a largest maximal independent set is called a maximum independent set.
For example, in the graph P3, a path with three vertices a, b, and c, and two edges ab and bc, the sets {b} and {a,c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a,c}. In this same graph, the maximal cliques are the sets {a,b} and {b,c}.
The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids.
Read more about Maximal Independent Set: Related Vertex Sets, Graph Family Characterizations, Bounding The Number of Sets, Set Listing Algorithms
Famous quotes containing the words independent and/or set:
“I’d like to come back as an independent woman who has more ambition than I have.”
—Jenny Bird (b. c. 1937)
“Come, thou long-expected Jesus,
born to set thy people free;
from our fears and sins release us,
let us find our rest in thee.”
—Charles Wesley (1707–1788)