獨(dú)立集是指圖的頂點(diǎn)集的一個(gè)子集,該子集的導(dǎo)出子圖不含邊.如果一個(gè)獨(dú)立集不是任何一個(gè)獨(dú)立集的子集, 那么稱這個(gè)獨(dú)立集是一個(gè)極大獨(dú)立集.一個(gè)圖中包含頂點(diǎn)數(shù)目最多的獨(dú)立集稱為最大獨(dú)立集。最大獨(dú)立集 一定是極大獨(dú)立集，但是極大獨(dú)立集不一定是最大的獨(dú)立集。

支配集：

    與獨(dú)立集相對(duì)應(yīng)的就是支配集，支配集也是圖頂點(diǎn)集的一個(gè)子集，設(shè)S 是圖G 的一個(gè)支配集，則對(duì)于圖中的任意一個(gè)頂點(diǎn)u，要么屬于集合s, 要么與s 中的頂點(diǎn)相鄰。 在s中除去任何元素后s不再是支配集，則支配集s是極小支配集。稱G的所有支配集中頂點(diǎn)個(gè)數(shù)最 少的支配集為最小支配集，最小支配集中的頂點(diǎn)個(gè)數(shù)成為支配數(shù)。

最小點(diǎn)的覆蓋：

    最小點(diǎn)的覆蓋也是圖的頂點(diǎn)集的一個(gè)子集，如果我們選中一個(gè)點(diǎn)，則稱這個(gè)點(diǎn)將以他為端點(diǎn)的所有邊都覆蓋了。將圖中所有的邊都覆蓋所用頂點(diǎn)數(shù)最少，這個(gè)集合就是最小的點(diǎn)的覆蓋。

最大團(tuán)：

    圖G的頂點(diǎn)的子集，設(shè)D是最大團(tuán)，則D中任意兩點(diǎn)相鄰。若u，v是最大團(tuán)，則u,v有邊相連，其補(bǔ)圖u,v沒(méi)有邊相連，所以圖G的最大團(tuán)=其補(bǔ)圖的最大獨(dú)立集。

一些性質(zhì)：

最大獨(dú)立集+最小覆蓋集=V

最大團(tuán)=補(bǔ)圖的最大獨(dú)立集

最小覆蓋集=最大匹配