一種求解Ramsey數(shù)的計(jì)算機(jī)算法.pdf

1、Ramsey理論問題是一個(gè)經(jīng)典的組合數(shù)學(xué)問題.1930年，英國數(shù)學(xué)家F.P.Ramsey發(fā)表了一篇題為“On a problem of formal logic”的論文，文中首次提出了Ramsey定理.之后，越來越多的數(shù)學(xué)家加入到Ramsey理論的研究.現(xiàn)在，Ramsey理論已經(jīng)發(fā)展為一門跨學(xué)科的理論，Ramsey理論的結(jié)果也應(yīng)用到了越來越多的領(lǐng)域.
　　Ramsey數(shù)是Ramsey理論的重要研究內(nèi)容.然而，求解Ramsey數(shù)的困

2、難性遠(yuǎn)超我們想象.目前為止，只有9個(gè)較小的Ramsey數(shù)的值被精確求出，對于其他的Ramsey數(shù)，人們目前所知的上下界也相去甚遠(yuǎn).
　　本文對Ramsey理論中的若干問題作了相關(guān)研究.探討了Ramsey理論與矩陣之間的關(guān)聯(lián)，并創(chuàng)造性的提出了一種基于集合理論的計(jì)算機(jī)算法，該算法有望求得包括R(5，5)在內(nèi)的更多Ramsey數(shù)的精確值.
　　本文主要的研究內(nèi)容及章節(jié)如下:
　　第一章介紹相關(guān)工作的背景及研究意義，發(fā)展概況等

3、問題.
　　第二章給出Ramsey數(shù)，廣義Ramsey數(shù)等相關(guān)概念.
　　第三章介紹Ramsey的矩陣?yán)碚?，給出Ramsey矩陣的定義，探討Ramsey理論與矩陣的關(guān)系.
　　第四章針對Ramsey數(shù)的求值問題，提出一種基于集合理論的計(jì)算機(jī)算法，并以R(3，3)為例驗(yàn)證了該算法.
　　第五章針對對角型Ramsey數(shù)，對通過事先“確定”一部分邊的值的方法，對算法進(jìn)行優(yōu)化.
　　第六章對整篇文章作總結(jié)并提出將來