(資料圖片)

完美圖，關于完美圖介紹這個很多人還不知道,現在讓我們一起來看看吧！

1、 完美圖(perfect graph)是一種特殊的簡單圖，若圖G的任意一個節點導出圖H的色數χ(H)等于H的團數，則稱G是χ完美圖。

2、若圖G的任意一個節點導出子圖H的獨立數α(H)等于H的團劃分數，則稱G是α完美圖，弱完美圖猜想：G是χ完美圖的充分必要條件是G為α完美圖；或等價地，完美圖的補圖是完美圖。

3、由于它已獲證，并稱為完美圖定理，這就允許不必區別χ完美圖和α完美圖，而統稱為完美圖，強完美圖猜想：G是完美圖當且僅當G和G的補圖GC都不含長大于3的奇圈作為節點導出子圖，這個猜想至今尚未得到證明。

標簽：