独立集合
(最大独立集合 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/24 19:05 UTC 版)
グラフ理論における独立集合（どくりつしゅうごう、英: independent set）または安定集合（英: stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。
- ^ Godsil, Chris; Gordon Royle (2004) [1949]. Algebraic Graph Theory. New York: Springer. p. 3. 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.
[続きの解説]
独立集合と同じ種類の言葉
- 独立集合のページへのリンク
