图论及其应用读书笔记 id: graph_reading_notes 支配集 定义: 对于无向图 G=(V,E)G=(V,E)G=(V,E)，若 V′⊆VV'\subseteq VV′⊆V 且 ∀v∈(V∖V′)\forall v\in(V\setminus V')∀v∈(V∖V′) 存在边 (u,v)∈E(u, v)\in E(u,v)∈E 满足 u∈V′u\in V'u∈V′，则 V′V'V′ 是图 GGG 的一个 支配集 (dominating set)。 人话：从图 GGG 里选出一批点，使得图中任意一个没被选中的点，都至少与一个被选中的点相邻。这些被选中的点组成的集合就是一个支配集。