独立集合
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2010/05/12 13:54 UTC 版)
グラフ理論における独立集合(どくりつしゅうごう、英: independent set)または安定集合(英: stable set)は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。
- ^ Godsil, Chris; Gordon Royle [1949年] (2004年). Algebraic Graph Theory. New York: Springer. ISBN 0-387-95220-9.
- ^ Füredi, Z. (1987). “The number of maximal independent sets in connected graphs”. Journal of Graph Theory 11 (4): 463–470. DOI: 10.1002/jgt.3190110403.
- 1 独立集合とは
- 2 独立集合の概要
独立集合と同じ種類の言葉
- 独立集合のページへのリンク