8.2 独立集与覆盖

文档摘要

8.2 独立集与覆盖 8.2 独立集与覆盖：图论中的隐秘盟友在图论的奇妙世界中，图的着色问题就像一位色彩斑斓的画家，用不同的颜色描绘着图的各个顶点，使得相邻的顶点颜色互异。而在着色问题的背后，隐藏着两个重要的概念——独立集与覆盖。它们就像是图论世界中的隐秘盟友，看似独立，却又相互关联，共同揭示着图的结构与性质。 8.2.1 独立集：孤立的美丽想象一下，在一个社交网络中，我们想要找到一群互不相识的人，他们之间没有任何直接的联系。这群人就可以看作是一个独立集。定义：在图 G = (V, E) 中，一个顶点集合 S ⊆ V 被称为独立集（Independent Set），如果 S 中的任意两个顶点之间都没有边相连。换句话说，对于任意的 u, v ∈ S，都有 (u, v) ∉ E。