獨立集（圖理論）
在圖理論中，獨立的集合，穩定的集合， Coclique或antlique是圖中的一組頂點，其中兩個都相鄰。也就是說，這是一套
最大獨立集是給定圖的最大尺寸的獨立集
每個最大獨立集也是最大的，但是相反的含義不一定保持。
特性
與其他圖參數的關係
當且僅當它是圖表補充中的一個集團時，一組是獨立的，因此兩個概念是互補的。實際上，沒有大集團的足夠大圖具有很大的獨立集，這是拉姆西理論中探討的主題。
當它的補充是頂點蓋時，一組是獨立的。因此，最大獨立集的大小的總和
圖的頂點著色
在沒有隔離頂點的兩分圖中，最大獨立集中的頂點數等於最小邊覆蓋中的邊數。這是kőnig的定理。
最大獨立集
不是另一個獨立集的適當子集的獨立集稱為最大值。這樣的集合主要是集合。每個圖最多都包含3 N /3最大獨立集，但是許多圖的含量都少得多。 N -Vertex循環圖中最大獨立集的數量由Perrin數字給出， N -Vertex Path圖中的最大獨立集數量由Padovan序列給出。因此，這兩個數字與1.324718 ...（塑料比率）成正比。
查找獨立集
- 在最大獨立集問題中，輸入是一個無向圖，並且輸出是圖中的最大獨立集。如果有多個最大獨立集，則只需要輸出一個。這個問題有時稱為“頂點包裝”。
- 在最大重量獨立集問題中，輸入是一個無方向的圖表，其頂點上的權重是一個具有最大總重量的獨立集。最大獨立集問題是所有權重的特殊情況。
- 在最大的獨立集列表問題中，輸入是一個無方向的圖，並且輸出是其所有最大獨立集的列表。最大獨立集問題可以用作最大獨立集列表問題的子例程算法解決，因為最大獨立集必須包括在所有最大獨立集中。
- 在獨立的設置決策問題中，輸入是一個無向圖和數字k ，輸出是一個布爾值：如果該圖包含一個獨立的大小k ，則否則為false。
這些問題中的前三個在實際應用中都很重要。獨立的集合決策問題不是，而是必須將NP完整性理論應用於與獨立集有關的問題所必需的。
最大獨立集和最大集團
獨立集問題和集團問題是互補的： G中的集團是G的補充圖中的獨立集，反之亦然。因此，許多計算結果可以很好地應用於任何一個問題。例如，與集團問題有關的結果具有以下合流：
儘管在任意圖中的最大集團和最大獨立集之間存在密切的關係，但在限於特殊類圖的特殊類別時，獨立集和集團問題可能會大不相同。例如，對於稀疏圖（邊緣數量最多是任何子圖中的頂點數的圖），最大集合的大小為界面，並且可以在線性時間中完全找到；但是，對於相同類別的圖形，甚至對於更受限制的有限度圖表，找到最大獨立集是maxsnp commente找到一個近似最佳C因子的近似解決方案。
確切的算法
最大獨立集問題是NP-HARD。但是，可以比O（ n 2 2 n ）時間更有效地求解，而O（n 2 2 n）時間由幼稚的蠻力算法給出，該算法檢查每個頂點子集並檢查它是否是獨立的集合。
截至2017年，它可以在時間O（1.1996 N ）中使用多項式空間解決。當限於最高度3的圖表時，可以在時間O（1.0836 N ）中求解。
對於許多類圖，可以在多項式時間中找到最大獨立的集合。著名的例子是無爪圖，無P 5的圖形和完美的圖。對於弦圖，可以在線性時間中找到最大重量獨立的集合。
模塊化分解是解決最大重量獨立集問題的好工具； Cographs上的線性時間算法是基本示例。另一個重要的工具是Tarjan所述的集團分離器。
kőnig的定理意味著在兩部分圖中可以使用雙分部分匹配算法在多項式時間內找到最大獨立集。
近似算法
通常，在多項式時間中，最大獨立集問題不能近似於恆定因素（除非p = np）。實際上，最大獨立集通常是poly-apx算法，這意味著任何可以近似於多項式因素的問題都很難。但是，對於限制的圖形，存在有效的近似算法。
在平面圖中
在平面圖中，最大獨立集可以在多項式時間內的任何近似值率C <1之內近似。在未成年人中關閉的任何圖表中都存在類似的多項式時間近似方案。
在有限程度的圖中
在有界度圖中，有效近似算法的近似值比為恆定，固定值的最大程度為最大。例如，一種貪婪的算法，在每個步驟中，在每個步驟中選擇了最大獨立的算法，在圖形中選擇最小度頂點並刪除其鄰居，在圖形上達到了（δ+2）/3的近似值，該圖具有最大度δ的圖。 Berman＆Karpinski（1999）證明了此類實例的近似硬度界限。實際上，即使是在3台式3 edge-colorable圖上的最大獨立設置也是apx complete 。
在間隔交點圖中
間隔圖是一個圖形，其中節點是1維間隔（例如時間間隔），並且僅當它們相交時兩個間隔之間存在邊緣。間隔圖中的獨立集只是一組非重疊的間隔。例如，在作業計劃的背景下，研究了在間隔圖中查找最大獨立集的問題：給定一組作業，必須在計算機上執行，找到一組最大的作業，可以執行，而無需干涉而可以執行彼此。可以使用最早的截止日期安排在多項式時間內準確解決此問題。
在幾何相交圖中
幾何相交圖是一個圖形，其中節點是幾何形狀，並且僅當它們相交時兩個形狀之間存在邊緣。幾何相交圖中的獨立集只是一組不相交的（非重疊）形狀。例如，在自動標籤放置的背景下，研究了在幾何相交圖中找到最大獨立集的問題：在地圖中給定一組位置，在這些位置附近找到一組最大的分離矩形標籤。
在交叉圖中找到最大獨立集仍然是NP完整的，但是比一般的最大獨立集問題更容易近似。最近的調查可以在Chan＆Har-Peled的引入（2012年）中找到。
在無D-Claw圖中
圖中的d-claw是一組D +1頂點，其中一個（“中心”）連接到其他D頂點，但其他D頂點沒有相互連接。 D -d -Claw圖形是沒有D -Claw子圖的圖。考慮從一個空集開始的算法，只要它與任何現有頂點相鄰，就會逐步添加一個任意頂點。在D -Claw圖形中，每個添加的頂點在最大獨立集中最多是D -1頂點的無效；因此，該微不足道的算法達到了最大獨立集的A（ d -1） - 附件算法。實際上，有可能獲得更好的近似比：
- Neuwohner提出了一種多項式時間算法，對於任何常數ε> 0，都可以找到A（ D /2-1 /63,700,992+ε） - 最大重量獨立於D -claw Free Graph中的最大重量獨立集。
- Cygan提出了一種準多項式時間算法，對於任何ε> 0，它都達到了A（D+ε）/3近似值。
查找最大獨立集
找到最大獨立集的問題可以通過微不足道的平行貪婪算法在多項式時間內解決。所有最大獨立集可以在時間O（3 N /3 ）= O（1.4423 N ）中找到。
計數獨立集
計數問題＃is詢問，給定圖形，其中包含多少個獨立集。這個問題是棘手的，即，它是♯P的complete，已經在最大程度的第三級圖表上。進一步眾所周知，假設NP與RP不同，則無法仔細估算問題，因為它沒有隨機化的完全多項式近似方案（FPRA），即使在具有最大程度的最高學位的圖上也是如此。但是，如果最大程度為五個，它確實具有完全多項式的近似方案（FPTA）。在兩分圖上計數獨立集的問題#bis也是♯P的complete，已經在最大程度的三個圖形上。 #BIS是否承認FPRAS尚不清楚。
還研究了計數最大獨立集的問題。
申請
最大獨立集及其補充，最小頂點覆蓋問題，參與證明許多理論問題的計算複雜性。它們還可以作為現實世界優化問題的有用模型，例如，最大獨立集是發現設計工程遺傳系統的穩定遺傳成分的有用模型。