獨立集
獨立集(英語: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]
參考資料
[編輯]- ^ Chris Godsil and Gordon Royle. Algebraic Graph Theory. New York: Springer. 2001: p. 3. ISBN 0-387-95220-9.
- ^ Sipser, Michael. Introduction to the Theory of Computation, Third Edition. Cengage Learning. 2013: pp. 311–313. ISBN 978-1-133-18779-0.
- ^ Papadimitriou, Christos H. Computationaly Complexity. Addison Wesley Longman. 1994: pp. 309–322. ISBN 0-201-53082-1.