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)
“it pleaseth me when I see through the meadows
The tents and pavilions set up, and great joy have I
When I see o’er the campana knights armed and horses arrayed.
And it pleaseth me when the scouts set in flight the folk with
their goods;
And it pleaseth me when I see coming together after them an host of
armed men.”
—Bertrans De Born (fl. 12th century)