來源：互聯網
獨立集是指圖 G 中兩兩互不相鄰的頂點構成的集合。任意有關圖中團的性質都能很自然的轉述成獨立集的性質。一般而言，尋找圖的最大團是 NP 困難的，從而尋找圖的最大獨立集也是 NP 困難的。但是，對于二部圖的情形，有多項式時間算法找出圖的最大獨立集。
定義
圖的一一個頂點子集稱為獨立集，如果該子集中的任意兩個項點在圖中不相鄰。圖 G 的最大獨立集所包含頂點的個數稱作 G 的獨立數(independence number)記作。
團
在圖論中，還有一個與獨立集密切相關的概念——團。圖的頂點子集稱為團(clique)，如果該子集中的任意兩個頂點在圖中相鄰。圖 G 的最大團所包含頂點的個數稱作 G 的團數(clique number)，記作。不難看出，一個圖的團是其補圖的獨立集。因此，圖的團數等于其補圖的獨立數，即。
任意有關圖中團的性質都能很自然的轉述成獨立集的性質。一般而言，尋找圖的最大團是 NP困難的，從而尋找圖的最大獨立集也是NP 困難的。但是，對于二部圖的情形，有多項式時間算法找出圖的最大獨立集。
舉例
有個圖有n個結點，y條邊，任選圖中一個頂點，把它染成黑色，則和它相連的頂點必須都被染成白色，但與被染成白色的頂點相連的頂點可以被染成白色也可以被染成黑色，問：這個圖最多有多少個頂點能被染成黑色？
解：相當于求圖的最大獨立集。求一般圖的最大獨立集是NP hard。
具體程序實現可以通過求最小覆蓋集來求最大獨立集。
圖的覆蓋集D是頂點集的一個子集，并滿足：，屬于D或屬于D。
定義 *，+ 滿足交換率，結合率，
吸收率：，，
這樣，求極小覆蓋集：
，
結果化簡后的每個因子項即對應一個極小覆蓋集。
參考資料 >