Independent Set
المؤلف:
Hochbaum, D. S
المصدر:
Approximation Algorithms for NP-Hard Problems. PWS Publishing
الجزء والصفحة:
...
16-1-2022
1975
Independent Set
Two sets 
and 
are said to be independent if their intersection 
, where 
is the empty set. For example, ![<span style=]()
{A,B,C}" src="https://mathworld.wolfram.com/images/equations/IndependentSet/Inline5.svg" style="height:22px; width:72px" /> and ![<span style=]()
{D,E}" src="https://mathworld.wolfram.com/images/equations/IndependentSet/Inline6.svg" style="height:22px; width:49px" /> are independent, but ![<span style=]()
{A,B,C}" src="https://mathworld.wolfram.com/images/equations/IndependentSet/Inline7.svg" style="height:22px; width:72px" /> and ![<span style=]()
{C,D,E}" src="https://mathworld.wolfram.com/images/equations/IndependentSet/Inline8.svg" style="height:22px; width:73px" /> are not. Independent sets are also called disjoint or mutually exclusive.
An independent vertex set of a graph 
is a subset of the vertices such that no two vertices in the subset represent an edge of 
. The figure above shows independent vertex sets consisting of two subsets for a number of graphs (the wheel graph 
, utility graph 
, Petersen graph, and Frucht graph).
An independent edge set can be defined similarly (Skiena 1990, p. 219).
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.
الاكثر قراءة في نظرية المجموعات
اخر الاخبار
اخبار العتبة العباسية المقدسة
