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 was more independent than any farmer in Concord, for I was not anchored to a house or farm, but could follow the bent of my genius, which is a very crooked one, every moment.”
—Henry David Thoreau (1817–1862)
“There are twenty ways of going to a point, and one is the shortest; but set out at once on one. A man who has that presence of mind which can bring to him on the instant all he knows, is worth for action a dozen men who know as much, but can only bring it to light slowly.”
—Ralph Waldo Emerson (1803–1882)