Independent Set
Two sets 👁 A
and 👁 B
are said to be independent if their intersection 👁 A intersection B=emptyset
, where 👁 emptyset
is the empty
set. For example, 👁 {A,B,C}
and 👁 {D,E}
are independent, but 👁 {A,B,C}
and 👁 {C,D,E}
are not. Independent sets are also called disjoint
or mutually exclusive.
An independent vertex set of a graph 👁 G
is a subset of the vertices such that
no two vertices in the subset represent an edge of 👁 G
. The figure above shows independent
vertex sets consisting of two subsets for a number of graphs (the wheel
graph 👁 W_8
,
utility graph 👁 K_(3,3)
, Petersen graph, and
Frucht graph).
An independent edge set can be defined similarly (Skiena 1990, p. 219).
A maximal independent set is an independent set which is a maximal set, i.e., an independent set that is not a subset of any other independent set.
See also
Clique, Disjoint Sets, Edge Cover, Empty Set, Independence Number, Independence Polynomial, Independent Edge Set, Independent Vertex Set, Intersection, Maximal Independent Edge Set, Maximal Independent Set, Maximal Independent Vertex Set, Maximum Independent Edge Set, Maximum Independent Set Problem, Maximum Independent Vertex Set, Venn Diagram, Vertex CoverExplore with Wolfram|Alpha
More things to try:
References
Hochbaum, D. S. (Ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing, p. 125, 1997.Skiena, S. "Maximum Independent Set" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.Referenced on Wolfram|Alpha
Independent SetCite this as:
Weisstein, Eric W. "Independent Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IndependentSet.html