完美圖

完美圖

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

基本介紹

  • 中文名:完美圖
  • 外文名:perfect graph
  • 所屬學科:數學
  • 所屬問題:組合學(圖與超圖)
  • 簡介:一種特殊的簡單圖
基本介紹,相關性質定理,

基本介紹

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

相關性質定理

1961年,Berge提出了如下猜想:
一個圖是完美的充分必要條件是它為x完美圖(或
完美圖),即
1972年,Lovász,Fulkerson相繼獨立地證明了這個猜想。
因為對任意的
,有
所以當G滿足(P1)或(P2)時,顯然也滿足
由(1)推知:
G滿足(P1)
G滿足(P2);
G滿足(P3)
G滿足(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是完美圖若且唯若G是完美圖。
推論2 圖G是完美圖若且唯若
是完美圖。
由前面我們已經知道,若G或G包含一個生成子圖
,則G不是完美圖。
Berge關於完美圖的第二個猜想(強完美圖猜想)是
猜想 若G或G不含生成子圖
,則G是完美圖。
迄今已知這個猜想對許多圖類是成立的,如三角圖。

相關詞條

熱門詞條

聯絡我們