Independent Set

释义 Definition

（图论）独立集：在一个图中选取的一组顶点，使得这组顶点中任意两点之间都没有边相连。也常称为 stable set（稳定集）。在优化问题中常见“最大独立集”（maximum independent set）。

发音 Pronunciation (IPA)

/ˌɪndɪˈpɛndənt sɛt/

例句 Examples

Find an independent set in this graph.
在这个图中找一个独立集。

In any graph, a large clique in the complement graph corresponds to a large independent set in the original graph.
在任意图中，补图中的一个大团（clique）对应于原图中的一个大独立集。

词源 Etymology

independent 来自拉丁语系词根，含义是“不受支配的、彼此不依赖的”；set 表示“集合”。合在一起，independent set 字面意思是“彼此独立的一组元素”，在图论里具体化为“彼此之间没有边相连的一组顶点”。

相关词 Related Words

• Graph
• Vertex
• Edge
• Clique
• Stable Set
• Maximum Independent Set
• Complement Graph
• Matching
• NP-Complete
• Turán's Theorem

文学与经典著作 Literary Works

• Douglas B. West，《Introduction to Graph Theory》：以“independent set / stable set”系统介绍独立集及相关定理与例题。
• Reinhard Diestel，《Graph Theory》：在图的基本概念、补图关系、极值问题中多次使用“independent set”。
• Garey & Johnson，《Computers and Intractability》：将“Maximum Independent Set”作为经典 NP-Complete 问题之一讨论。
• Noga Alon & Joel H. Spencer，《The Probabilistic Method》：在随机图与存在性证明中涉及独立集的规模与界。