圈的多色拉姆塞數及相關極圖問題研究

《圈的多色拉姆塞數及相關極圖問題研究》是依託北京交通大學，由孫永奇擔任項目負責人的面上項目。

基本介紹

• 中文名：圈的多色拉姆塞數及相關極圖問題研究
• 項目類別：面上項目
• 項目負責人：孫永奇
• 依託單位：北京交通大學

項目摘要

拉姆塞理論在很多領域都有套用，如資訊理論和計算機科學等。圖的拉姆塞數研究是拉姆塞理論的一個主要研究方向，它對網路設計中通信設施數量的選擇以及通訊頻道Shannon容量的確定有重要意義。它是NP困難問題，研究它對解決一般NP困難問題有意義。.到目前為止，只有很有限的一些圖簇的拉姆塞數得到了精確值，其成果主要集中在對兩色拉姆塞數的研究。但實際套用中遇到的可能是多色拉姆塞數。本課題著重研究圈的多色拉姆塞數以及相關極圖問題；研製出較好的計算圈的多色拉姆塞數的算法、計算圈的多色拉姆塞數下界的算法以及構造相關極圖的算法。主要目標是探索出一條求解圈的多色拉姆塞數問題的有效途徑，為圈的拉姆塞數的實際套用提供更堅實的理論基礎，也為其它圖簇多色拉姆塞數的求解提供借鑑。.　　在圖的多色拉姆塞數研究領域，申請者已經取得了一些研究成果。本項目的研究，將有助於我們在該領域取得更大的突破。

結題摘要

本項目主要對圈的多色拉姆塞數及極圖問題進行了研究，取得了一些研究成果。首先研究了特定的非完全圖在邊著色算法中的套用。在對多色拉姆塞數的研究中，證明了一些比較規範的非完全圖如二部圖或多部圖的一些性質，並將其運用到多色拉姆塞數的求解中。利用該成果確定了R3(C8)和R(K4-e, K4-e, C4)的準確值，這些特殊子圖的套用可使算法的執行效率提高十倍以上。在此基礎上對二部拉姆塞數進行了深入研究，證明了b(C2m; K2,2)和b(C2m; C6)的準確值，並給出了b(C2m; C2n)的下界。發表期刊論文2篇，國際會議論文1篇，其中1篇期刊論文已被SCI檢索。這項研究成果不僅有助於求解多色拉姆塞數R(G, C6, C4)、R(G, C6, C6) 和R4(C6)，而且也有助於求解其他相關多色拉姆塞數。其次，研究了圈的4色拉姆塞數R(Cm, Cn, Ck, C6)，其中m、n和k等於4或6。利用拼圖法確定了R(C6, C4, C4, C4) = 19，關於該成果的論文已被SCI刊源期刊錄用。此外還確定了18 ≤ R(C6, C6, C4, C4) ≤ 19、18 ≤ R(C6, C6, C6, C4) ≤ 19和18 ≤ R4(C6) ≤ 19。在對拼接的圖的補圖2著色時充分研究了邊著色順序與著色效率的關係，在著色前重新給頂點合理標號以提高算法的執行效率。第三，研究了不含偶圈的極圖構造算法。設計了不包含偶圈的分散式極圖構造算法，計算出頂點數不超過28且不含六邊形的極圖。計算結果表明，該分散式算法的平均執行效率達到了75.48%，最高值則達到91.41%。關於該成果的論文已被EI刊源期刊錄用。第四，研究了圍長為9和10的極圖，確定了當22 ≤ n ≤ 30時ex(n;{C3,C4,…,C8})的準確值，並給出當31 ≤ n ≤ 57時ex(n;{C3,C4,…,C8})的下界，關於該研究成果的論文已投稿到Utilitas Mathematica(SCI刊源期刊)。還確定了當26 ≤ n ≤ 33時ex(n;{C3,C4,…,C9})的準確值，並給出當34 ≤ n ≤ 69時ex(n;{C3,C4,…,C9})的下界。