輪圖和圈集的拉姆塞數及相關算法研究

《輪圖和圈集的拉姆塞數及相關算法研究》是依託北京交通大學，由孫永奇擔任項目負責人的面上項目。

基本介紹

• 中文名：輪圖和圈集的拉姆塞數及相關算法研究
• 項目類別：面上項目
• 項目負責人：孫永奇
• 依託單位：北京交通大學

項目摘要

拉姆塞理論廣泛套用於數學、計算機科學以及經濟金融等領域，它在並行編程、近似算法、博弈論以及理論計算機科學中有很多套用。. 本項目著重研究廣義拉姆塞數R(H1, H2, ..., Hr)，其中r＞=2，H1為輪圖Wn或圈集{C3, C4, ..., Cm}。(1) 研究與這兩類圖相關的拉姆塞圖的結構特徵；(2) 根據這兩類圖的特點設計出較好的計算拉姆塞數及其下界的算法，對他們的拉姆塞數進行計算；(3) 設計帶權圖的同構判定算法，用於邊著多種顏色圖的同構判定；(4) 利用多色子圖填充法對與這些圖類相關的多色拉姆塞數進行研究，給出他們的準確值或更好的界。. 本項目的目標是找到輪圖和圈集的拉姆塞數變化規律，並探索拉姆塞數研究的新方法和新技術。項目的研究將為這些圖類在網路設計中的套用奠定更加堅實的理論基礎，並為解決其他NP困難問題提供借鑑。

結題摘要

拉姆塞理論在資訊理論、計算機科學以及經濟金融等很多領域都有套用，但確定拉姆塞數是非常困難的。本項目採用計算機構造與數學證明相結合的方法對圈集和輪圖的拉姆塞數及極圖問題進行了研究。首先研究了圈集對完全圖的拉姆塞數，給出了極圖集合EX(2n; C≤n)中圖的結構，從而確定了R(C≤n, Kn)和R(C≤n, Kn+1)的準確值；並給出了當n為奇數且n ≥ 25時R(C≤n, Kn+2)的值。然後，研究了完全圖的哈密爾頓圈分解，給出了完全圖的新的分解方式。對於奇數k，證明了Rk(C≤k+1)；對於偶數k，則給出了R4(C≤5) = 12，R6(C≤7) = 16和Rk(C≤k+1) = 2k + 3，其中8 ≤ k ≤ 12。第三，研究了圍長為9的極圖，通過分析頂點數n = 13, 16, 18, 22 和26時EX(n; 8)中極圖的特點，證明了當25 ≤ n ≤ 30時ex(n; 8)的準確值；還構造了三個特殊的圖，並基於他們改進了31 ≤ n ≤ 57時ex(n; 8)的下界值。研究了不包含圈集的極圖構造算法，設計了一種基於量子進化的構造給定圍長圖的極圖構造算法，利用該算法構造出頂點數為n (31 ≤ n ≤ 89)圍長為11的圖，從而給出了相應的ex(n;11)的下界。第四，研究了六邊形對星圖、六邊形對輪圖的拉姆塞數，給出了當5 ≤ n ≤ 28時R(C6, Sn)的準確值或上下界，給出了當4 ≤ n ≤ 26時R(C6, Wn)的準確值或上下界。最後，對圖論和複雜網路理論在生物信息處理中的套用進行了研究，在關鍵蛋白質識別、複合物檢測以及疾病與RNA的關聯關係預測等方面取得了一系列研究成果。