圖的鄰集分解與最大團問題的研究.pdf

1、最大團問題(Maximum clique problem，MCP)是圖論中經(jīng)典的組合優(yōu)化問題。本文綜述了國內(nèi)外學者對該問題的研究成果，包括該問題的應(yīng)用背景、界的估計及各種算法的研究。 本文首先對最大團的界進行了論述，并提出了一個新的上界。其次詳細探討了圖的鄰集分解與最大團。圖的分解不僅使問題的規(guī)?？s小(其中參數(shù)的選擇和平均度的應(yīng)用使得規(guī)模再次縮小)，同時該方法不會陷入局部最優(yōu)?；趫D的鄰集分解及不同排序策略提出了一種新的精確算法

2、——截支定界法。該算法吸取了分支定界法的優(yōu)點，先用下界把圖中對求解最大團沒價值的點刪去，再應(yīng)用圖的鄰集分解方法對給出的隨機圖進行分解，使求解最大團的搜索規(guī)模大大收縮，從而加快了算法的收斂速度，最后再對團進行搜索。其中在團的搜索階段對不同類型的圖采取不同的搜索策略。對邊密度較大的圖由于最大團中包含最大度頂點的概率比較大，所以采取貪婪搜索策略；對邊密度較小的圖由于最大團中包含最小度頂點的概率比較大，所以采取非貪婪的搜索策略；對中等密度的圖由