動機
邊密度不等式可以迫使大團出現,卻無法對每個圖判定團是否存在。要確定精確閾值,我們需要一個達到該界的圖,以及一個證明:沒有任何無團圖的邊數更多。當階數不能被部分數整除時,構造中的有限取整就變得至關重要。
完全多部圖提供了候選者。它們的團至多能從每個部分中選取一個頂點,而讓各部分大小均衡會使跨部分的邊數最大。一個刪團歸納法證明了該候選者在所有圖中是最優的,而等號情形則揭示了整個多部結構。
這一結果把未取整的密度估計加強為精確的計數與分類。
定義
定義 10.6.1
(完全多部圖與均衡邊數)
設 與 為整數。完全 部圖是指其頂點被劃分為 個部分,所有跨部分的邊都存在,而部分內部沒有邊。允許空部分,這包含 的情形。當任意兩個部分的大小至多相差一時,稱其為均衡的。
寫 ,其中 。均衡的大小為: 個大小為 的部分,以及 個大小為 的部分。它們的邊數為
該表達式是整數,因為它計數的是位於不同部分的無序點對。本章中的圖均為有限簡單無向圖。
團是指由兩兩相鄰的頂點構成的集合。若一個圖沒有該大小的團,則稱其為 -free(不含 )。其獨立數是不含任何邊的頂點集的最大大小。這裏的極值圖是指在給定階數下邊數盡可能多的無團圖。
圖同構允許對頂點重新標號。等號情形的分類只在這種重新標號的意義下確定圖,並不強制已有頂點集上存在某個特定的帶標號劃分。
定理/命題
定理 10.6.2
(均衡化唯一地使多部圖的邊數最大)
在 個頂點的完全 部圖中,最大邊數為 ,且恰好在各部分大小均衡時取到。對 ,
對 且 ,還有 。
定理 10.6.3
(精確的無團閾值及全部等號情形)
每個 個頂點的 -free 圖至多有 條邊。等號成立當且僅當該圖是均衡完全 部圖(在頂點重新標號及允許空部分的意義下)。
因此,邊數多於 就必然含有大小為 的團。反向的判定命題是錯誤的:低於閾值的圖仍可能含有該團。
定理 10.6.4
(互補的獨立集問題有精確的最小值)
一個 個頂點且獨立數至多為 的圖至少有 條邊。等號成立當且僅當該圖是 個均衡團的不交併(允許空團)。
因此,同一個極值計數既度量了避免大團的最大邊集,也度量了禁止大獨立集的最小邊集,圖的補運算在兩個問題之間互相交換。
證明思路或證明
證明
(均衡化與多部圖遞推)
對於和為 的各部分大小 ,跨部分邊數為 。設有兩個大小滿足 。把一個頂點從較大的部分移到較小的部分,它們的平方和由 變為 ,減少了 ,從而邊數增加。
重複這一有限的均衡化操作。每個不均衡的大小模式都可以被改進;每個均衡的模式都具有所示的 大小,因而邊數相同。這就證明了最大值以及所有多部圖的等號模式。展開其平方和即得公式的兩種形式。
當 時,每個均衡的部分都非空。從每個部分中各刪去一個頂點,剩餘部分在 個頂點上仍是均衡的。被刪去的頂點構成一個 團,而每個留存的頂點恰與其中 個頂點相鄰。計數被刪去的邊即證明了定理中的遞推式。
關於部分參數的嚴格遞增:從 個頂點上的均衡 部圖出發。至少有一個部分的大小不小於二。把該部分拆成兩個非空部分,便得到它們之間乘積那麼多的正數條新邊,且至多使用 個部分。繼續均衡化只會使結果進一步增大。因此,其原有最優邊數嚴格小於 。
用兩個相互關聯的歸納證明極值上界
證明
(刪團歸納)
的情形是顯然的:不含二團的圖沒有邊,恰是單部構造。對於更大的 ,假設定理的上界已對參數 在每個階數上得證,並對 用歸納法證明當前的 。
若 ,則頂點數不足以容納被禁止的團,最大的圖是完全圖,有 條邊。現設 。若圖中不含 團,則參數 的界給出邊數至多為 。這一分支以嚴格不等式得到解決。
否則取一個大小為 的團 。 之外的任一頂點在 中至多有 個鄰點,因為若與它們全部相鄰就會產生一個 團。其餘 個頂點上的圖仍是 -free 的。於是對階數的歸納將總邊數界定為
每次調用要麼使用更小的部分參數,要麼在同一參數下使用更小的階數。因此這兩重歸納是良基的,並在每個階數上證明了上界。均衡構造是無團的,因為團在每個獨立部分中至多使用一個頂點,所以它達到了這個界。
等號迫使圖本身是均衡多部圖
證明
(等號重構各部分)
對於 ,等號情形是無邊圖。若 ,等號要求所有可能的邊都存在,即由 個單點部分及其餘空部分表示的完全圖。考慮剩下的情形 。
無 團的分支嚴格低於該界,所以等號圖含有這樣的團 。邊數取等迫使每個 外的頂點在 中恰有 個鄰點,因此它恰好漏掉其中一個頂點。
把每個外部頂點劃入其唯一未相鄰頂點 所在的部分,同時也把 放入該部分。被劃入同一部分的兩個外部頂點不能相鄰。若它們相鄰,這兩個頂點連同 中其餘 個頂點就會構成一個 團。按定義,二者都不與各自被指派的 相鄰,所以得到的每個部分都是獨立的。
因此原圖是這些部分上的完全 部圖的子圖。由均衡化定理,該完全圖至多有 條邊,而原圖已恰有這麼多條邊。所以每條允許的跨部分邊都必須存在,且各部分必須是均衡的。這就證明了完整的等號分類,而無須假設較小的導出子圖的分類會自動控制被刪去的團如何連接。
證明透視
刪團歸納如何緊到足以完成分類
兩個歸納同時進行:對沒有 團的分支,對部分參數 歸納;對有 團的分支,對階數 歸納。第一個分支需要均衡化定理中的嚴格不等式 ,正是這種嚴格性日後把它排除在所有等號情形之外。在第二個分支中,圖無 這一假設對每個外部頂點各用一次:它把連向 的邊數限制為至多 。恆等式 於是使三部分計數恰好相加為 。
等號需要的不止數值歸納。在所選團處取等,使每個外部頂點恰好缺失 的一個頂點,而這種模式命名了各部分。禁止團的條件第二次被用到,是在每個擬定的部分內部,使它成為獨立集。只有這樣,均衡化定理才把「包含於完全 部圖中」提升為「等於均衡的完全 部圖」;毋須用較小導出子圖的分類去控制 如何連接。
將精確結論轉移到獨立集
證明
(補圖轉換)
一個集合在圖中是獨立的,當且僅當它在簡單補圖中是團。因此,獨立數至多為 意味著補圖是 -free 的。對補圖的 條邊應用上界並整理,即得 的下界。
對等號圖取補,會去掉所有跨部分的邊並把每個部分內部補滿,得到不交的均衡團。反過來,該併集的獨立數至多等於其非空團的個數,因而至多為 ,且它達到所述的邊數。這就證明了互補等號命題的兩個方向,包括 時極值圖為無邊圖的情形。
該閾值能判定甚麼,不能判定甚麼
由整數除法計算 是直接的,而邊數更多的圖必定含有可證明存在的大團。該定理並沒有說邊數更少的圖都是無團的。要檢測實際的團,或解釋密度檢驗的失敗,還需要其他論證。
對固定的 ,枚舉所有 個頂點的集合並檢查其點對,是關於 的多項式時間的有限搜尋,指數依賴於 。這一觀察並不是對以二進制編碼的可變閾值一致成立的多項式界。該極值定理是一個精確的結構性陳述,其存在性證明並不能消除一般團算法中輸入模型的區別。
例題詳解
例題 10.6.5
(八個頂點且禁止四團時,邊數至多二十一)
取 。均衡大小為三、三、二。其跨部分邊數為 。每個不含四團的圖至多有二十一條邊,而等號恰好要求這種完全三部圖的形狀。
因此二十二條邊就迫使出現四團。在互補的獨立集問題中,要迫使獨立數至多為三,至少需要 條邊;大小為三、三、二的均衡團併集的邊數為 。
例題 10.6.6
(奇數階的無三角形界保留了取整)
對於七個頂點且 ,均衡部分的大小為四和三,得到十二條邊。未取整的密度項是 ,而修正量為四分之一,從而整數最優值為十二。
每個有十二條邊的無三角形圖,在重新標號意義下都是完全二部圖 。十三條邊就迫使出現三角形。精確的分類給出的資訊,多於在忘記其等號條件之後對粗略估計簡單地向下取整。
例題 10.6.7
(可用部分數多於頂點數時不會出現例外公式)
對於三個頂點且 ,取三個單點部分和兩個空部分。均衡圖是 ,有三條邊,且不可能含有被禁止的六團。
公式中商為零、餘數為三,同樣給出三。其補圖是三個孤立點,可表示為大小為一、一、一、零、零的五個均衡團部分。其獨立數為三,確實至多為五。允許空部分使兩個等號命題在這一邊界處保持一致。
概念視角組合
最大化允許的邊數同時也揭示了禁團的邊界
均衡多部構造把邊花在部分之間,同時阻止團在同一部分內取兩個頂點。歸納證明了沒有任何其他排布能花費更多的邊。在取等時,每個外部頂點在所選 團中唯一缺失的鄰點重構了這些部分,使得極值形狀成為一個結論,而不是一幅憑空猜測的圖。
常見錯誤
反例模式
低於閾值並不意味著圖是無團的
一個三角形加上三個孤立點只有三條邊,遠低於 ,但它仍含有三角形。該定理說的是無三角形圖的邊數不能超過九,或等價地說,多於九條邊就迫使出現三角形。它並沒有把每個更小的邊數都變成不存在三角形的證明。
常見錯誤
(恰好等於閾值並不迫使團出現)
在迫使性陳述中要保持嚴格不等號,在極值上界中要保持非嚴格不等號。 恰有 條邊而沒有三角形,所以「七個頂點上的十二條邊迫使三角形出現」是錯的;要十三條或以上才行。
常見錯誤
(單憑邊數不能確定圖)
等號分類只有在已知圖無團之後才適用。一個三角形加一條懸掛邊有四個頂點和 條邊,卻不是 ,因為它含有三角形。
常見錯誤
(多部圖與團的不交並回答不同的問題)
均衡完全多部圖與不交團並並不相同;補運算在這兩種結構之間互相交換。在四個頂點、 時, 有四條邊,是最大的無三角形圖;兩條不相交的邊則是獨立數至多為二的最小圖,有 條邊。把兩個答案互換,得到的圖對兩個問題都不是極值圖。
總結
均衡化各部分大小給出了精確的整數候選者及其修正項。刪團歸納法證明了全局極值上界,而與所選團的緊密連接迫使每個等號圖都是均衡多部圖。取補得到精確的最少邊獨立集對應結論,而否定性的密度檢驗仍然是不確定的。
練習
快速檢查
(求十個頂點的無四團圖的精確邊數上界。寫出等號情形的形狀,以及獨立數至多為三時的互補最小值。)
把十均衡地分成三部分。
解答 · 答案
該界為 。等號要求具有這些大小的完全三部圖。三十四條邊就迫使出現四團。
互補最小值為 ,恰好由大小為四、三、三的不交團取到。它們的內部邊數分別為六、三、三,總計十二,而任何獨立集在每個團中至多使用一個頂點。
快速檢查
(透過從每個均衡部分中各刪去一個頂點,解釋 的遞推式,並對 、 驗證之。)
計數被刪去的團及其與留存頂點之間的所有邊。
解答 · 答案
被刪去的 個頂點構成一個團,有 條邊。其餘 個頂點中的每一個,都與除自己所在部分對應的那個以外的所有被刪頂點相鄰,貢獻 條跨部分邊。剩餘部分仍是均衡的,於是得到遞推式。
在 時,,,差為十三。按所計數的類別得 ,符合要求。
快速檢查
(在等號證明中,為甚麼缺失同一個團頂點的兩個外部頂點必然不相鄰?為甚麼最終的邊數迫使所有跨部分邊都存在?)
在調用均衡化之前,先使用團中其餘 個頂點。
解答 · 答案
若兩個這樣的外部頂點相鄰,它們與團中其餘 個頂點就會兩兩相鄰,產生大小為 的被禁團。因此,它們被指派的部分(包括其缺失的那一個團頂點)是獨立的。
該圖包含於這些部分上的完全多部圖中。它的邊數已經等於任何此類部分大小下所能達到的最大邊數。若缺少某條允許的跨部分邊,則包含它的多部圖的邊數就會嚴格大於該最大值。因此一條也不缺,而均衡化結果中的等號迫使各部分大小至多相差一。