複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/完美圖/19138146
複製
複製成功

完美圖

鎖定
完美圖(perfect graph)是一種特殊的簡單圖，若圖G的任意一個節點導出圖H的色數χ(H)等於H的團數，則稱G是χ完美圖。若圖G的任意一個節點導出子圖H的獨立數α(H)等於H的團劃分數，則稱G是α完美圖，弱完美圖猜想：G是χ完美圖的充分必要條件是G為α完美圖；或等價地，完美圖的補圖是完美圖。由於它已獲證，並稱為完美圖定理，這就允許不必區別χ完美圖和α完美圖，而統稱為完美圖，強完美圖猜想：G是完美圖當且僅當G和G的補圖GC都不含長大於3的奇圈作為節點導出子圖，這個猜想至今尚未得到證明 [1]  。
中文名
完美圖
外文名
perfect graph
所屬學科
數學
所屬問題
組合學(圖與超圖)
簡    介
一種特殊的簡單圖

目錄

  1. 1 基本介紹
  2. 2 相關性質定理

完美圖基本介紹

我們已經知道，對任一個圖
，有如下一些基本參數：
點無關數
，即最大點無關集的點數；
團數
，即最大團的點數；
點色數
；
還有另一個參數：
團覆蓋數
，即這樣的最小的k，使G中存在k個團
，有
。
如果我們給了一個集合S的一個子集族
，使
，則稱
覆蓋了S，利用“覆蓋”的語言，那麼點色數就是覆蓋
所需要的點無關集的最小個數；而團覆蓋數就是覆蓋
所需要的團的最小個數。
以上這些參數之間有着緊密的聯繫。若Gc是G的補圖，則有
這是因為在G與Gc中，點無關集和團是一一對應的．。此外，顯然有
這是因為任一個團和任一個點無關集最多有一個公共點。
1960年Berge引進了完美圖的概念。
稱圖G是x完美圖，如果
稱圖G是
完美圖，如果
若圖G既是x完美圖，又是
完美圖，則稱G是完美圖 [2]  。

完美圖相關性質定理

1961年，Berge提出瞭如下猜想 [2]  ：
一個圖是完美的充分必要條件是它為x完美圖(或
完美圖)，即
。
1972年，Lovász，Fulkerson相繼獨立地證明了這個猜想。
因為對任意的
，有
所以當G滿足(P1)或(P2)時，顯然也滿足
由(1)推知：
G滿足(P1)
Gc滿足(P2)；
G滿足(P3)
Gc滿足(Ps)，
所以假如我們能夠證明
，則G滿足
滿足
滿足
滿足
滿足
，從而就證明了。
因已知
，所以證明上述Berge猜想的關鍵是去證明
。
現在我們給出
的證明。
首先引入圖上的一種運算——倍點運算。
對任意的
，用
表示這樣的一個圖：在G中增加一個新點v'，並且
當且僅當
，我們説
是由G通過倍點運算得到的。
設
，設
是任一非負整數向量，以
表示這樣的一個圖： 用點無關集
代替vi，對任意的
當且僅當
，當某個
時，則意味着從G中丟去
，因此，對任意的(0，1)向量h，
與G的生成子圖對應。
引理1 設
，則
(1)若G滿足(P1)，則H滿足(P1)；
(2)若G滿足(P2)，則H滿足(P2)。
引理2(Fulkerson，1971；Lovász，1972)設G滿足(P2)，令
，那麼由G滿足(P3)可推出日滿足(P3)。
引理3(Lovász，1972)若G滿足(P3)，則G滿足(P1)。
由引理3，就可推得
定理 對任意圖G，
推論1 圖G是完美圖當且僅當Gc是完美圖。
推論2 圖G是完美圖當且僅當
是完美圖。
由前面我們已經知道，若G或Gc包含一個生成子圖
，則G不是完美圖。
Berge關於完美圖的第二個猜想(強完美圖猜想)是
猜想 若G或Gc不含生成子圖
，則G是完美圖。
迄今已知這個猜想對許多圖類是成立的，如三角圖 [2]  。
參考資料
  • 1.    數學辭海編輯委員會．數學辭海·第二卷：中國科學技術出版社，2002
  • 2.    田豐 馬仲蕃．圖與網絡流理論：科學出版社，1987年09月第1版：第150頁