1、在無向圖G=(V，E)中，團（ clique)指圖 G的一個完全子圖，在這個子圖中的任意兩個頂點之間都有邊連接。最大團問題（Maximum Clique Problem)指在給定的圖 G中找出包含頂點個數(shù)最多的一個團。最大團問題是經(jīng)典的N P難度問題，其對應的判定問題：給定無向圖G和整數(shù) A;，判斷圖 G中是否存在大小為A:的團，是 N P完全間題。最大團問題在故障診斷、生物信息學、編碼理論、計算機視覺、組合拍賣、經(jīng)濟學分析、社會網(wǎng)絡分

2、析等實際問題中存在著廣泛的應用，與最大獨立集、最小頂點覆蓋、圖染色等其它經(jīng)典的NP難度問題也密切相關(guān)。研究最大團問題的求解算法具有重要的理論意義和應用價值。
　　當前求解最大團問題的算法主要分為兩類：啟發(fā)式算法和精確算法。啟發(fā)式算法通常能在較短的時間內(nèi)給出質(zhì)量相對較高的解，但無法保證解的最優(yōu)性。精確算法通過系統(tǒng)搜索問題的整個解空間，從而保證最終得到的解為全局最優(yōu)解。盡管從理論分析上看，現(xiàn)有的最大團精確算法在最壞情況下的時間復雜度無

3、一例外都是指數(shù)級的，但近年來的研究進步使得精確算法的實際求解能力得到顯著提升。
　　本文研究基于分支定界方案的最大團精確算法。論文工作緊緊圍繞分支與定界這兩個決定算法性能的關(guān)鍵策略展開。具體工作體現(xiàn)在以下四個方面：
　　(一）在標準 MaxSAT推理的基礎上，提出了更加高效的漸進MaxSAT推理技術(shù)用于減少分支頂點數(shù)量。對圖進行近似頂點染色是估計最大團上界的經(jīng)典方法。但近似染色數(shù)上界與最大團的實際值之間往往存在較大差距。標準

4、 MaxSAT推理將頂點的染色結(jié)果編碼成MaxSAT公式，利用 MaxSAT推理技術(shù)來計算更加精確的上界。盡管標準MaxSAT推理能顯著減少搜索樹大小，但對搜索樹的剪枝作用仍存在“全或無”的顯著特征。本文從設計思路上將MaxSAT推理的目標從改進上界估計轉(zhuǎn)變?yōu)闇p少分支頂點數(shù)量，提出了漸進MaxSAT推理技術(shù)。實驗表明，漸進 MaxSAT推理在減少分支數(shù)量方面總是能產(chǎn)生積極效果，與傳統(tǒng)的MaxSAT推理技術(shù)相比效率更高。
　　(二）

5、研究了動態(tài)順序和靜態(tài)順序兩種分支順序策略，提出了混合分支順序策略。結(jié)合漸進MaxSAT推理技術(shù)，本文設計了基于動態(tài)分支順序的DoMC算法和基于靜態(tài)分支順序的 SoMC算法。SoMC算法在保持靜態(tài)分支順序的前提下最小化分支頂點集，而 DoMC允許分支順序動態(tài)變化以使分支頂點集最小化。實驗表明二者在性能上相互補充?；趧討B(tài)順序與靜態(tài)順序性能互補的觀察，本文提出了混合分支順序策略，設計了混合分支順序算法MoMC。實驗結(jié)果表明， DoMC、 S

6、oMC和 MoMC三個算法的總體性能顯著地超越當前國際上最好的精確算法。
　　(三）針對大量存在的真實世界稀疏大圖，設計了簡單高效的預處理程序。該預處理程序在單一的過程中高效地完成初始頂點順序計算、初始團尋找、圖規(guī)?；喌热楊A處理任務。結(jié)合該預處理程序和漸進MaxSAT推理技術(shù)，設計了針對稀疏大圖的精確算法LMC。實驗表明， LM C能夠快速求解頂點規(guī)模達到千萬級的真實世界大圖，其性能明顯超越了目前國際上最好的大圖精確算法PM

7、C和 BBMCSP。LMC算法的優(yōu)異表現(xiàn)也駁斥了文獻中關(guān)于MaxSAT推理等高級技術(shù)并不適用于大稀疏圖求解的觀點。
　　(四）針對最大團問題的變型一加權(quán)最大團問題，設計了精確算法WLMC。由于頂點之間存在權(quán)重差異，加權(quán)圖中的頂點關(guān)系更加復雜，使得加權(quán)最大團問題的求解難度要顯著地高于非加權(quán)的經(jīng)典最大團問題。為簡化頂點之間的復雜關(guān)系，本文提出了由沖突驅(qū)動的兩個頂點權(quán)重切分規(guī)則：顯式?jīng)_突切分和隱式?jīng)_突切分，并從圖概念的視角直觀地闡述了基

8、于沖突獨立集探測的上界估計。大量真實世界圖集上的實驗結(jié)果表明， W LMC算法的整體性能表現(xiàn)顯著地超越了當前最好的精確算法和啟發(fā)式算法，有力地駁斥了精確算法對解決大規(guī)模圖能力不足的主流觀點。
　　傳統(tǒng)的最大團分支定界算法集中關(guān)注如何改進上界估計，本文在算法設計思路上集中關(guān)注如何減少分支數(shù)量。這一設計思路的轉(zhuǎn)變使得對MaxSAT推理和頂點權(quán)重切分等技術(shù)的運用效率更高。該設計思路也有望用于改進其它基于分支定界的組合優(yōu)化問題算法設計。針