跳至內容

獨立集

維基百科,自由的百科全書
圖中九個藍色的頂點是延伸佩特森圖英語Generalized Petersen graphGP(12,4)中的一個最大獨立集

獨立集(英語:Independent set)是圖論中的概念。一個獨立集(也稱為穩定集)是一個中一些兩兩不相鄰的頂點所形成的集合。換句話說,獨立集由圖中若干頂點組成,且中任兩個頂點之間沒有。等價地,圖中的每條邊至多有一個端點屬於。一個獨立集的基數是它包含頂點的數目。

如果往圖的獨立集中添加任一個頂點都會使獨立性喪失(亦即造成某兩點間有邊),那麼稱極大獨立集。如果是圖中所有獨立集之中基數最大的,那麼稱最大獨立集,且將該基數稱為的獨立數,記為[1]。一般來講,圖中可能存在多個極大獨立集;最大獨立集亦如是。最大獨立集一定是極大獨立集,但反之未必。

給定一張圖,尋找其中一個最大獨立集的問題被稱為最大獨立集問題。該問題已知是NP困難最優化問題,且即便試圖以常數倍近似也是NP困難的。因此,計算機科學家普遍相信不存在解決該問題的高效算法,無論是精確求解還是以常數倍近似求解。

數學定義

對於圖,如果頂點子集滿足,則稱的一個獨立集,稱為該獨立集的基數。

對於獨立集,如果,則稱是極大獨立集。直觀而言,極大意味着不能單純通過加入頂點來擴充。

如果是所有獨立集中最大的,那麼稱是最大獨立集,並將稱作的獨立數(independence number),記作。最大獨立集一定是極大獨立集;若不然,我們總能加入頂點來擴充之,從而與最大的定義矛盾。

整數規劃形式

計算獨立數的問題可以等價表達成如下的整數規劃

其中,變量取1代表把頂點放入獨立集,取0則反之。第一條線性約束表達了每條邊的兩個端點不能同時放入獨立集中。

與其它圖論對象的聯繫

與頂點覆蓋的關係

圖的一個頂點覆蓋(vertex cover)是頂點集的一個子集,使得圖中每條邊都與其中某點相鄰。基數最小的頂點覆蓋稱為圖的最小頂點覆蓋。獨立集與頂點覆蓋的定義互補,因此不難看出,是圖的獨立集當且僅當的頂點覆蓋。於是,就等於的頂點數減去的最小頂點覆蓋的基數。

與團的關係

在圖論中,(clique)是一個與獨立集密切相關的概念。圖的一個團指的是一個頂點子集,使得中頂點兩兩相鄰。用圖論的語言,團即一個完全子圖的最大團的基數稱作的團數(clique number),記作 。 如果說獨立集是一種水火不容的頂點集,那麼團就是一種息息相關的頂點集。不難看出,一個圖的團是其補圖的獨立集,反之亦然。這個一一對應關係使得二者性質能夠相互轉述,而與二者相關的問題往往等價。例如,圖的團數等於其補圖的獨立數,即 。類似地,圖中團的總數等於補圖中獨立集的總數。

對於一般的圖而言,尋找最大團是NP困難的,從而尋找最大獨立集也是NP困難的。計算機科學家普遍相信沒有算法能在確定性多項式時間解決之。但是,對於二分圖這一特殊情形,則有多種方法可以高效地求解。例如,可以求解鬆弛後的線性規劃並對結果作整數化處理,也可以使用匈牙利算法求出最小頂點覆蓋後再轉化為最大獨立集。

與點連通度的關係

圖的點連通度定義為:最少需要刪除個頂點方能使得圖不復連通。獨立數與點連通度有着簡單關係

原因是:設是一個最大獨立集,把的頂點全部刪掉以後,殘餘下來的正是獨立集,而它自然是不連通的。

與着色數的關係

圖的着色(proper colouring)即為每個頂點染上一種顏色,使得任意相鄰頂點顏色均不同(但不相鄰頂點顏色可以相同)。對圖進行着色所需的最少顏色數被稱為着色數,記作。獨立數和着色數之間存在以下關係:

其中中的頂點數。

證明

左側不等式:設着色是一個使用顏色最少的方案,我們構造個集合如下。。也就是說,把顏色相同的節點放入同一個集合。這些集合構成了頂點集的一個劃分,所以。注意到每個集合都各是一個獨立集(因為相同顏色的頂點之間不允許有邊),所以對它們均成立。代入先前等式便有

右側不等式:設是一個最大獨立集,我們據此構造一種着色。首先,中所有頂點均染上顏色1(這必定不會造成衝突)。其次,給其餘頂點分配互異且非1的顏色。容易看出僅僅使用了種顏色,因此着色數必定不少於該數。

計算複雜性

求最大獨立集是計算機科學中的重要問題,因為許多現實場景可以抽象成該問題。例如,人們希望組織一場會議,候選的某些演講者之間或有嫌隙,不願同時出席。可以將這種候選人之間敵意關係抽象成一張圖,兩個候選人間有邊當且僅當二者不和。那麼,最終的演講者名單就應當是這張圖的一個獨立集。會議組織者希望邀請儘可能多的演講者以充實內容,也就相當於尋找圖中的最大獨立集。

然而,計算複雜性理論在以下兩方面的進展暗示該問題難以求解。

判定版本的NP完備性

考慮最大獨立集問題的判定版本:給定一張圖和一個目標,圖中是否存在一個獨立集的基數不小於?在先前的例子中,相當於:會議組織者預先設定了一個目標邀請人數,問這個目標能否實現?其實,判定版本並不比原始版本簡單。假設我們能夠高效解決判定版本,那麼也可以藉助自歸約性質(self-reducibility),相對高效地解決原始版本。

最大獨立集問題的判定版本是NP完備的,這意味着,除非(而人們普遍相信這是不可能的),否則不存在確定性多項式時間算法解決之。其完備性的證明可以參見[2]

優化版本的不可近似性

考慮最大獨立集問題的優化版本:給定一張圖,計算。該問題是MAXSNP完備的,這意味着,除非,否則不存在確定性多項式時間算法能以任意精度近似之(PTAS)。

還可以證明:假若存在某個高效算法能以某常數近似比計算該問題,那麼就能據此構造出一個以任意精度近似計算該問題的高效算法(PTAS)。結合前面的結論可知:除非,否則不存在高效算法能以常數倍近似計算該問題。[3]

參考資料

  1. ^ Chris Godsil and Gordon Royle. Algebraic Graph Theory. New York: Springer. 2001: p. 3. ISBN 0-387-95220-9. 
  2. ^ Sipser, Michael. Introduction to the Theory of Computation, Third Edition. Cengage Learning. 2013: pp. 311–313. ISBN 978-1-133-18779-0. 
  3. ^ Papadimitriou, Christos H. Computationaly Complexity. Addison Wesley Longman. 1994: pp. 309–322. ISBN 0-201-53082-1.