本文選題：Ramsey數(shù) + 星-臨界Ramsey數(shù)��； 參考：《北京交通大學(xué)》2016年博士論文

【摘要】：Ramsey理論是組合數(shù)學(xué)的一個重要分支,它廣泛應(yīng)用于計算機科學(xué)、信息論以及決策學(xué)等領(lǐng)域。在Ramsey理論研究中,一個與圖論交叉的重要分支是求解圖的Ramsey數(shù),它在邏輯分析、并行計算和計算幾何等計算機科學(xué)領(lǐng)域都有重要作用。本文利用計算機構(gòu)造與數(shù)學(xué)證明相結(jié)合的方法,對與圈相關(guān)的星-臨界Ramsey數(shù)、四邊形對輪圖(或星圖)以及圈集對完全圖的Ramsey數(shù)進(jìn)行了研究。星-臨界Ramsey數(shù)r*(C4,Cn)。星-臨界Ramsey數(shù)由Hook和lsaak于2011年提出,并給出了r*(C4,C3)的準(zhǔn)確值。本文首先利用圖的Hamilton性質(zhì)證明了所有(C4.Cn；n)-圖G的結(jié)構(gòu)；然后在圖G的基礎(chǔ)上增加一個新的頂點v，通過討論頂點v與G的n個頂點之間的添邊情形,并結(jié)合三類特殊圖的Hamilton-connected特性詳細(xì)分析了添加的最大邊數(shù),最終證明了當(dāng)n≥4時,r*(C4,G)=5。四邊形對輪圖的Ramsey數(shù)R(C4,Wm)。Tse用計算機算法確定了7≤m≤13時R(C4,Wm)的準(zhǔn)確值。Dybizbanski和Dzido確定了14≤m≤17時R(C4,Wm)的值,并給出了R(C4,Wm)的上界。本文首先基于(k，5)-籠(3≤k≤7)構(gòu)造了不含C4且滿足最小度要求的圖,給出了R(C4,Wm)的下界；然后運用星-臨界Ramsey的研究成果證明了任意圖G是(C4,Wm;n)-圖的充分必要條件,并利用不含C4的極圖的相關(guān)研究成果證明了一些(C4,Wm;n+1)-圖是不存在的,從而改進(jìn)了相關(guān)R(C4,Wm)的上界,最終求解出18≤m≤44中R(C4,Wm)的9個準(zhǔn)確值。四邊形對星圖(或輪圖)的Ramsey數(shù)。Parsons給出了四邊形對星圖的Ramsey數(shù)R(C4,K1,m)的上界,并證明了當(dāng)q為任意素數(shù)冪時,R(C4,K1,q2)=q2+q+1和R(C4,K1,q2+1)=q2+q+2。本文通過研究基于射影平面的極性圖的結(jié)構(gòu)特性,構(gòu)造性的給出了R(C4,K1,q2-2)的下界,并結(jié)合Parsons給出的上界,最終證明了R(C4,K1,q2-2)=q2+q-1。利用該構(gòu)造方法,還給出了當(dāng)q為任意素數(shù)冪時,R((C4,Wq2+2)和R(C4,Wq2-1)的下界。通過詳細(xì)分析q2++2個頂點不包含C4圖的特性,改進(jìn)了R(C4,Wq2+2)的上界：再結(jié)合前人給出的R(C4,Wq2-1)的上界,最終證明了R(C4,Wq2+2)=q2+q+2和R(C4,Wq2-1)=q2+q-1。圈集對完全圖的Ramsey數(shù)R(Csm,Km)。Erdos和Faudree等人證明了：當(dāng)n≥2m-1時,R(C≤n,Km)=2m-1;當(dāng)mn2m-1時,R(C≤n,Km)=2m。本文研究了n≤m≤n+2時的R(C≤n,Km)。首先利用平面圖的特性證明了極圖集合EX(2n;C≤n)中圖的結(jié)構(gòu)；然后通過分析EX(2n;C≤n)中圖的獨立數(shù)證明了：當(dāng)n為奇數(shù)時,R(S≤n,Kn)=2n;當(dāng)n為偶數(shù)時R(C≤n,Kn)=2n+1。利用上述結(jié)論證明了Ramsey數(shù)R(Csn,Kn+1)的上界,并結(jié)合構(gòu)造的(C≤n,Kn+1;2n+2)-圖證明了當(dāng)奇數(shù)n≥4和偶數(shù)n之16時,R(C≤n,Kn+1)=2n+3。另外,當(dāng)n為奇數(shù)時,通過構(gòu)造(C≤n,Kn+2;2n+4)-圖給出了R(C≤n,Kn+2)的下界,證明了任意的(C≤n,Kn+1;2n+2)-圖的結(jié)構(gòu),并利用反證法給出了R(C≤n,Kn+2)的上界,最終確定了當(dāng)奇數(shù)n≥25時R(C≤n,Kn+2)=2n+5。求解Ramsey數(shù)R(C≤n,Km)的多核并行算法研究。本文研究了求解Ramsey數(shù)R(C≤n,Km)的串行算法,對其中的可并行化部分進(jìn)行了系統(tǒng)分析,設(shè)計了的求解Ramsey數(shù)R(C≤n,Km)的并行算法,并在Phoenix++平臺上對其進(jìn)行了實現(xiàn)。同時采用數(shù)據(jù)預(yù)處理和合理分割數(shù)據(jù)集等措施提高了并行算法的執(zhí)行效率。優(yōu)化試驗結(jié)果表明,并行算法在四核下的加速比和執(zhí)行效率分別達(dá)到了3.70和92.50%。最后,利用該并行算法確定了當(dāng)4≤n≤12時,R(C≤n,Kn+1和R(C≤n,Kn+2)的準(zhǔn)確值。
[Abstract]:It is an important branch of combinatorial mathematics , which is widely used in the fields of computer science , information theory and decision - making . In this paper , the Hamiltonian properties of graphs are first used to prove all ( C4.Cn ) .
n ) - the structure of FIG . G ;
Then , a new vertex v is added on the basis of graph G . By discussing the boundary between vertices v and n vertices of G , the maximum number of edges added is analyzed in detail by Hamilton - connected features of three special graphs . Finally , it is proved that when n 鈮，

本文編號：2075017