图与其补图覆盖数间的关系

对图G(V,E),,使得V∪E中的任一元素或在A_T中,或与A_T中的元素相邻,或与A_T中的元素相关联,则称A_T为G的全覆盖;G中元素数最少的全覆盖,称为G的最小全覆盖;G的最小全覆盖中的元素数,称为G的全覆盖数,并简记作α_T(G)设α(G)、α′(G)分别表示图G的(点)覆盖数、边覆盖数,G~c表示G的补图,则