圖的鄰集分解與最大團(tuán)問(wèn)題的研究.pdf

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

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