完美圖

完美圖(perfect graph)是一種特殊的簡單圖，若圖G的任意一個節點導出圖H的色數χ(H)等於H的團數，則稱G是χ完美圖。若圖G的任意一個節點導出子圖H的獨立數α(H)等於H的團劃分數，則稱G是α完美圖，弱完美圖猜想：G是χ完美圖的充分必要條件是G為α完美圖；或等價地，完美圖的補圖是完美圖。由於它已獲證，並稱為完美圖定理，這就允許不必區別χ完美圖和α完美圖，而統稱為完美圖，強完美圖猜想：G是完美圖若且唯若G和G的補圖G^C都不含長大於3的奇圈作為節點導出子圖，這個猜想至今尚未得到證明。

基本介紹

• 中文名：完美圖
• 外文名：perfect graph
• 所屬學科：數學
• 所屬問題：組合學(圖與超圖)
• 簡介：一種特殊的簡單圖

基本介紹

我們已經知道，對任一個圖，有如下一些基本參數：

點無關數，即最大點無關集的點數；

團數，即最大團的點數；

點色數；

還有另一個參數：

團覆蓋數，即這樣的最小的k，使G中存在k個團，有。

如果我們給了一個集合S的一個子集族，使，則稱覆蓋了S，利用“覆蓋”的語言，那么點色數就是覆蓋所需要的點無關集的最小個數；而團覆蓋數就是覆蓋所需要的團的最小個數。

以上這些參數之間有著緊密的聯繫。若G^c是G的補圖，則有

這是因為在G與G^c中，點無關集和團是一一對應的．。此外，顯然有

這是因為任一個團和任一個點無關集最多有一個公共點。

1960年Berge引進了完美圖的概念。

稱圖G是x完美圖，如果

稱圖G是完美圖，如果

若圖G既是x完美圖，又是完美圖，則稱G是完美圖。

相關性質定理

1961年，Berge提出了如下猜想：

一個圖是完美的充分必要條件是它為x完美圖(或完美圖)，即。

1972年，Lovász，Fulkerson相繼獨立地證明了這個猜想。

因為對任意的，有

所以當G滿足(P₁)或(P₂)時，顯然也滿足

由(1)推知：

G滿足(P₁)G^c滿足(P₂)；

G滿足(P₃)G^c滿足(Ps)，

所以假如我們能夠證明，則G滿足滿足滿足滿足滿足，從而就證明了。

因已知，所以證明上述Berge猜想的關鍵是去證明。

現在我們給出的證明。

首先引入圖上的一種運算——倍點運算。

對任意的，用表示這樣的一個圖：在G中增加一個新點v'，並且若且唯若，我們說是由G通過倍點運算得到的。

設，設是任一非負整數向量，以表示這樣的一個圖： 用點無關集代替v_i，對任意的若且唯若，當某個時，則意味著從G中丟去，因此，對任意的(0，1)向量h，與G的生成子圖對應。

引理1 設，則

(1)若G滿足(P₁)，則H滿足(P₁)；

(2)若G滿足(P₂)，則H滿足(P₂)。

引理2(Fulkerson，1971；Lovász，1972)設G滿足(P₂)，令，那么由G滿足(P₃)可推出日滿足(P₃)。

引理3(Lovász，1972)若G滿足(P₃)，則G滿足(P₁)。

由引理3，就可推得

定理 對任意圖G，

推論1 圖G是完美圖若且唯若G^c是完美圖。

推論2 圖G是完美圖若且唯若是完美圖。

由前面我們已經知道，若G或G^c包含一個生成子圖，則G不是完美圖。

Berge關於完美圖的第二個猜想(強完美圖猜想)是

猜想 若G或G^c不含生成子圖，則G是完美圖。

迄今已知這個猜想對許多圖類是成立的，如三角圖。