注意：

支配集、覆盖集、独立集和匹配都是对无向简单图而言的，而点的着色和边着色是对无环图而言的

定义1

设无向简单图G=(V,E),V∗⊆V$G=(V,E),V^*/subseteq V$，若∀vi∈V−V∗,∃vj∈V∗$/forall v_i/in V-V^*,/exists v_j /in V^*$使得(vi,vj)∈E$(v_i,v_j)/in E$，则称V∗$V^*$为G的一个支配集。V∗$V^*$的任何真子集都不是支配集，则称V∗$V^*$为极小支配集，极小支配集V∗$V^*$的任何真子集都不是支配集，则称V∗$V^*$为极小支配集，G的顶点数最少的支配集称作G的最小支配集，最小支配集中顶点的个数称作G的支配数，记作γ0(G)$/gamma_0(G)$，简记为γ0$/gamma_0$

定义2

设无向简单图G=<V,E>,V∗⊆V$G=<V,E>,V^*/subseteq V$，若V∗$V^*$中任何两个顶点均不相邻，则称V∗$V^*$为G的点独立集，简称为独立集。若V∗$V^*$再加入任何其他的顶点都不是独立集，则称V∗$V^*$为极大点独立集，G的顶点数最多的点独立集称作G的最大点独立集，最大独立集的顶点数称作G的点独立集，记作β0(G)$/beta_0(G)$，简记作β0$/beta_0$

定理

无向简单图的极大点独立集都是极小支配集