獨立集是指圖的頂點集的一個子集,該子集的導出子圖不含邊.如果一個獨立集不是任何一個獨立集的子集, 那么稱這個獨立集是一個極大獨立集.一個圖中包含頂點數目最多的獨立集稱為最大獨立集。最大獨立集 一定是極大獨立集，但是極大獨立集不一定是最大的獨立集。

支配集：

    與獨立集相對應的就是支配集，支配集也是圖頂點集的一個子集，設S 是圖G 的一個支配集，則對于圖中的任意一個頂點u，要么屬于集合s, 要么與s 中的頂點相鄰。 在s中除去任何元素后s不再是支配集，則支配集s是極小支配集。稱G的所有支配集中頂點個數最 少的支配集為最小支配集，最小支配集中的頂點個數成為支配數。

最小點的覆蓋：

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

最大團：

    圖G的頂點的子集，設D是最大團，則D中任意兩點相鄰。若u，v是最大團，則u,v有邊相連，其補圖u,v沒有邊相連，所以圖G的最大團=其補圖的最大獨立集。

一些性質：

最大獨立集+最小覆蓋集=V

最大團=補圖的最大獨立集

最小覆蓋集=最大匹配