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

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

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

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