注意：

支配集、覆蓋集、獨立集和匹配都是對無向簡單圖而言的，而點的著色和邊著色是對無環圖而言的

定義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$

定理

無向簡單圖的極大點獨立集都是極小支配集