本論文是對完全圖作一個大略的介紹，第一章介紹一些相關的基本定義，主要的定義
是：圖G ＝（V ，E ）的每一個導出子圖GA＝（A ，EA）若滿足α（GA）＝θ（GA）
則稱G 為α一完全圖；若每一GA＝（A ，EA）滿足W （GA）＝X （GA）則稱G 為γ一
完全圖。並且對任意圖G ；α（GA）≦θ（GA），W （GA）≦X （GA）作一說明。
第二章是借助引伸圖（duplication graphs）的觀念，證明引理2 ：若G 的每一導出
子圖GA都滿足α（GA）＝θ（GA），而且W （GA）α（GA）≧│A │，則G 的延伸圖
H 的任意子圖HB滿足W （HB）α（HB）≧│B │。由此再推出完全圖定理：G 是α一
完全圖若且唯若G 是γ完全圖。
第三章是證明偶圖、三角圖、比較圖、有序完全圖這四類圖是完全圖，並討論他們之
間的關係，如G 是區間圖若且唯若G 是三角圖且G 的補圖是比較圖，三角圖，三角圖
的補圖，比較圖是有序完全圖。
第四章列舉出幾個算則：判別一個圖是否為三角圖，求最大穩定集，最小覆蓋點團，
最小的塗色數，最大點團及頂點的最小塗色。並在附錄中提供這些算則的FORTRAN 程
式以供參考。
|