平面Ramsey數(shù)PR（K-,4--e，K-,6-）和PR（C-,4-，K-,7-）的研究.pdf

1、圖的Ramsey數(shù)研究是Ramsey理論的一個(gè)重要研究方向．該問題不僅在數(shù)學(xué)的發(fā)展中有重要的理論價(jià)值，而且在信息論和理論計(jì)算機(jī)科學(xué)等許多領(lǐng)域中也有重要的應(yīng)用．Ramsey數(shù)的確定是一個(gè)NP困難問題，用數(shù)學(xué)方法僅能求出極少數(shù)圖的Ramsey數(shù)的準(zhǔn)確值．計(jì)算機(jī)技術(shù)的應(yīng)用給圖的Ramsey數(shù)研究注入了新的活力．本文將計(jì)算機(jī)構(gòu)造性證明與數(shù)學(xué)證明相結(jié)合，對(duì)圖的平面Ramsey數(shù)問題進(jìn)行了深入研究． 1969年，Walker首先提出了平面R

2、amsey數(shù)PR(H<,1>，H<,2>)的概念．Bielak和Gorgol證明了PR(C<,4>，K<,5>)=13和PR(C<,4>，K<,6>)=17，并給出PR(C<,4>，K<,l>)的一個(gè)下界． 本文在這些研究的基礎(chǔ)上，發(fā)現(xiàn)用臨界圖策略算法在可容忍的時(shí)間內(nèi)最多只能證明PR(K<,4>-e，K<,5>)=14和驗(yàn)證PR(C<,4>，K<,6>)=17．針對(duì)此算法這一不足，本文研制了計(jì)算平面Ramsey數(shù)PR(H<,1>

3、，H<,2>)值的新算法CPG．該算法沒有采用通常的臨界圖策略，而是針對(duì)平面Ramsey數(shù)中平面性這一限制，利用非平面圖一定包含同胚于K<,5>或K<,3,3>的子圖這一定理，通過增加頂點(diǎn)與邊從小頂點(diǎn)構(gòu)造出所有不含禁止子圖H<,1>(H<,1>≌K<,4>-e或H<,1>≌C<,4>)的n個(gè)頂點(diǎn)的平面圖，然后判定這些圖中是否存在一個(gè)圖G使得H<,2> G．若存在這樣的圖，則PR(H<,1>，H<,2>)≥n+1；否則，PR(H<,1>，

4、H<,2>)≤n．該算法已在Intet P4 1.7G，內(nèi)存500M的計(jì)算機(jī)上運(yùn)行．實(shí)驗(yàn)表明，該算法可驗(yàn)證到PR(K<,4>-e，K<,l>)(l≤6)和PR(C<,4>，K<,l>)(l≤7)的值，并可證明PR(K<,4>-e，K<,6>)=17和PR(C<,4>，K<,7>)=20． 該算法因不存在刪邊操作，運(yùn)行速度也比臨界圖策略算法提高了6倍多．本文同時(shí)將歐拉公式和三連通平面圖的平面嵌入唯一的性質(zhì)應(yīng)用到平面Ramsey數(shù)的