頂點獨立集

1 基礎性

定

義

獨立集

（英語：Independent set）是

圖論

中的概念。

一個獨立集是一個圖中一些兩兩不相鄰的頂點所形成的集合。

換句話說它是由頂點組成的集合

，使得

中任兩個頂點之間沒有邊。等價地，圖中的每條邊至多有一個端點屬於

。

一個獨立集的

基數

是它包含頂點的數目。

極大獨立集

是在圖中無法再增加頂點的獨立集，新增圖中任一其它頂點得到的新集合都不再是獨立集。

給定一個圖

，它的一個

最大獨立集

是

的一個基數最大的獨立集。這個基數稱為

的

獨立數

，記為

。

尋找一個最大獨立集的問題被稱為最大獨立集問題，且已知是

NP困難

的最最佳化問題。因此不存在尋找圖中一個最大獨立集的高效演算法。

在圖論中，還有一個與獨立集密切相關的概念——團。圖的頂點子集稱為

團

（clique），如果該子集中的任意兩個頂點在圖中相鄰。任意有關圖中團的性質都能很自然的轉述成獨立集的性質。一般而言，尋找圖的最大團是 NP 困難的，從而尋找圖的最大獨立集也是 NP 困難的。但是，對於二部圖的情形，有多項式時間演算法找出圖的最大獨立集。

例子：

九個藍色頂點構成了廣義Petersen圖 ）GP（12，4）的最大獨立集。

2

習題

2。1 所有度至多為

的圖滿足

。