最大全子圖（maximum clique）的求取一直為圖學理論及其應用上的有趣的問題，然
而此為一NP-complete 的問題，即其執行時間隨著圖形的增大而呈指數倍數的遞增，
故而未能有效率的將它解決。而且目前所存在的解決方法不是太過繁複就是太耗時間
，遂於是，我們希望另外找到一種新的方法去簡化最大全子圖的求取。
本論文中，我們提出了一很簡單且固定的方法去解決最大全子圖求取的方法，方法是
對某些點以其相鄰點建立點產生圖（vertex generated graph）即其相鄰點的點形成
圖（vertex induced subgraph）， 並且合併（merge） 部分的點產生圖，再對所有
產生出來的圖繼續的以相同的處理方式遞迴（recursion） 的找到各個圖中最大的全
子圖，然後由其中擇取最大者，再繼續的迴朔（back-tracking） 而上，一直到最後
能將最大全子圖找出為止；即所有的已經產生出來的圖均已被找過了。同時的，此法
因簡單亦使得伴隨我們演算法的分析方式較有系統且簡單。
我們不但方法較目前所存在的演算法為簡單，分析方式較有系統外，而且於最差的情
形下分析所得到時間複雜度的結果，比Tarjan提出來找尋最大獨立點集（maximum
independent set） 的時間上限的為低，因最大全子圖求取的演算法亦可應用於最大
獨立點集的求解，為０（２ ）。
最後，我們期待能進一步的改善我們的演算法，得到一較好的時間上限，使能突破目
前的時間上限，此為我們最大的期許。
|