獨立集是指圖 G 中兩兩互不相鄰的頂點構成的集合。任意有關圖中團的性質都能很自然的轉述成獨立集的性質。一般而言，尋找圖的最大團是 NP 困難的，從而尋找圖的最大獨立集也是 NP 困難的。但是，對於二部圖的情形，有多項式時間算法找出圖的最大獨立集。
基本介紹
- 中文名：獨立集
- 外文名：Independent Set
- 定義：兩兩互不相鄰的頂點構成的集合。
- 簡介： 圖的頂點集的子集，
- 吸收率：：a+ab = a
- 最大獨立集：是NP hard
定義,團,舉例,
定義
圖的一一個頂點子集稱為獨立集，如果該子集中的任意兩個項點在圖中不相鄰。圖 G 的最大獨立集所包含頂點的個數稱作 G 的獨立數(independence number)記作 
。
團
在圖論中，還有一個與獨立集密切相關的概念——團。圖的頂點子集稱為團(clique)，如果該子集中的任意兩個頂點在圖中相鄰。圖 G 的最大團所包含頂點的個數稱作 G 的團數(clique number)，記作 
。不難看出，一個圖的團是其補圖的獨立集。因此，圖的團數等於其補圖的獨立數，即 
。
任意有關圖中團的性質都能很自然的轉述成獨立集的性質。一般而言，尋找圖的最大團是 NP困難的,從而尋找圖的最大獨立集也是NP 困難的。但是，對於二部圖的情形，有多項式時間算法找出圖的最大獨立集。
舉例
有個圖有n個結點，y條邊，任選圖中一個頂點，把它染成黑色，則和它相連的頂點必須都被染成白色，但與被染成白色的頂點相連的頂點可以被染成白色也可以被染成黑色，問：這個圖最多有多少個頂點能被染成黑色？
解：相當於求圖的最大獨立集。求一般圖的最大獨立集是NP hard。
具體程式實現可以通過求最小覆蓋集來求最大獨立集。
圖G(V,E)的覆蓋集D是頂點集的一個子集，並滿足：任意 <vi,vj>屬於E，vi屬於D或vj屬於D。
定義 *，+ 滿足交換率，結合率，且 * 對 + 分配 (a+b)*c = a*c + b*c
吸收率：a+ab = a，a*a = a，a+a = a
這樣，求極小覆蓋集：
M(連乘)(v[i] + M(所有與v[i]相鄰的點))，i=0 to n
結果化簡後的每個因子項即對應一個極小覆蓋集。
