Ramsey定理在计算机领域中的应用

PAGE4Ramsey定理在计算机领域中的应用熊菡（武汉科技大学计算机科学与技术学院，湖北武汉）摘要：本文主要介绍了经典Ramsey定理的内容，以及Ramsey理论在网络规划和信息检索中的应用，将数学问题引入计算机领域进行研究和探讨。关键词：Ramsey定理，网络规划，信息检索1.引言Ramsey理论作为图论的一个重要研究分支，它产生于1930年，起源文章为英国数学家FrankRamsey的《OnaProblemofFormalLogic》。在这篇文章里FrankRamsey讨论了在某种条件下无论对集合如何划分都能够产生人们预期想要得到的子集的现象。后来人们在他工作的基础上不断扩充，确定了Ramsey理论的研究内容为：在某种条件下，无论对一个大系统（结构）如何进行分割，总是能够得到人们预期想要得到的子系统（结构）。这里的系统即由相互关联的事物所组成，要研究这种系统可以通过很多种方式进行探讨，但是“图”是表达这种系统的最佳工具，因为图论正是讨论“事物”及其“关系”的一个数学工具。所以图论理所当然地成为研究Ramsey理论的一个最重要的表达工具。在计算机领域，Ramsey理论同样也能帮助我们解决一些问题，本文主要研究的是Ramsey理论在网络规划和信息检索中的应用。2.Ramsey理论及其基础知识[问题]试证明任意6个人当中一定至少有3个人相互认识或者相互不认识。解：首先我们先不失一般性地假设“认识”是一种什么关系：认识是相互的，即如果A认识B，则B也认识A；认识是非传递的，即如果A认识B，B认识C，但A未必认识C。下面对这6个人编号：A，B，C，D，E，F。任意取一个人，比如说A，那么根据“鸽笼原理”A要么至少认识剩下5个人当中的3人，或者至少不认识剩下5个人当中的3人。那么我们先任意取一种情况，比如取A至少认识剩下5个人当中的3人（任意）：B，C，D。那么如果B，C，D三个人当中有任意两个人相互认识，比如说是B和C，则A、B、C三人构成相互认识的三个，题目的证；如果三人当中都相互不认识，则B、C、D三人构成相互不认识个人，题目也的三得证。对于另外一种情况，即A至少不认识剩下5个人当中的3人其证明与前面的证明相同。所以题目的结论是正确的。下面我们用数学的语言来描述上面的文字，可以这样说：对于有6个顶点完全图的边用2种颜色（比如是红色和蓝色）进行任意染色，则结果一定是：要么存在一个红色的三角形，要么存在一个蓝色的三角形。定义1.给定正整数n，r和图H1，H2，…，Hr，用r种颜色对完全图Kn的所有边进行着色，由第i色边构成的子图记为Gi.如果存在一种着色方法，使得对所有的i(1≤i≤r)都有HiGi，则称Kn对于(H1，H2，…，Hr)可r－着色.如果HlH2…HrH，则简称Kn对于H可r－着色.定义2.使得Kn对于(,,…,)不能r－着色的最小正整数n称为(经典)Ramsey数R().如果==…==，则把R()简写为Rr(p).定义3.使得Kn对于(H1，H2，…，Hr)不能r－着色的最小正整数n称为广义Ramsey数R(H1，H2，…，Hr).如果HlH2…HrH，则把R(Hl，H2，…，Hr)简写为Rr(H).定理1.R(C4,C4)=6定理2.R(C4,C4,C4)=11定理3.若一个n个顶点的图至少有条边，则它总包含C4。Ramsey定理在计算机中的应用3.1Ramsey定理在网络规划中的应用分组交换网是采用分组交换技术的网络，它从终端或计算机接收报文，把报文分割成分组，并按某种策略选择最佳路径在网中传输，到达目的地后再将分组合并成报文交给目的终端或计算机。分组交换技术在网络设计中被广泛采用。用顶点表示通信设备，用边表示通信链路，这样得到一个图。假定该图是完全图，即任意两点间都有一条边相连。在某些应用场合，顶点两两配对作为一个整体。我们希望保证在某些链路出故障不能使用时，任两对配对顶点间都至少有一条链路畅通无阻。图3.1设顶点x1,x2组成一对，y1,y2为一对，z1,z2为一对，且故障发生在诸如微波塔、中继站等中间设施上，见图3.1。在此类设施上的故障将影响所有共享该设施的链路。对共享同一个中间设施的链路，我们用同一种颜色来标记它们.如上图表示一个有三种中间设施的通信网络。在图中，若标记红色的中间设施出了故障.那么在顶点对x1,x2和顶点对z1,z2之间将没有可用的链路，而这对应于下列事实:四条边(xi,zj)构成一个单色的C4(4个顶点的回路)。一般来说，设计一个网络需决定中间设施的数量以及哪个链路使用哪个设施。此外，在任何一个中间设施损坏时，我们希望所设计的网络中任两对配对顶点间有一个可使用的链路。根据上面的讨论，我们应该避免出现单色的C4。已知Ramsey数R(C4,C4)=6。因此，如果只有两个中间设施，那么存在一个5个顶点的网络使得可以安排一种不出现单色C4的连接方式。已知Ramsey数R(C4,C4,C4)=11,所以存在一个10个顶点的网络，它使用三个中间设施且没有单色的C4。前面说过，设计一个网络需要决定中间设施的数量以及哪个链路使用哪个设施。中间设施是很昂贵的，因而希望使其数量尽可能少。所以自然要问:如果有一个n个顶点的网络，在不出现单色C4的条件下中间设施的最少个数是多少?换句话说，满足>n的最小的r是多少?比如对上图，n=6，由于R(C4,C4)=6，R(C4,C4,C4)=11所以r=3，即我们需要3个中间设施。一般情况下，若n个顶点的图的n(n-1)/2条边分成r种颜色类，由鸽巢原理，则必存在某个类至少有条边。我们要选择r使得不存在包含有条边的类，因此，选r使其满足<就行，即满足上述不等式的最小r就是所需要的最少中间设施数。3.2Ramsey定理在信息检索中的应用信息检索是计算机科学中一个基本而又重要的问题。如何组织数据，使用什么样的查找方法对检索的效率有很大的影啊。我们所熟知的在有序表结构上的二分搜索算法是一种很有效的方法，但二分搜索是最好的算法吗?假设一个表有n个不同的项，其元素取自键空间M={1,2,，m}.我们希望找到在表中存储M的任意n元子集S的方法，使得容易回答下述询问:x在S中吗?如何存储M的n元子集的规则称为一个表结构或(m，n)-表结构。最简单的表结构是有序表结构，它是按上升序列出S中的元素。更一般的是按置换排序的表结构，它是固定{1,2,…,n}的一个置换，根据此置换的次序列出S中的元素。信息检索的计算复杂性依赖于表结构和搜索策略。复杂性的度量是最坏情形下确定x是否在S中所需要的询问次数。例如，对于有序表结构，如果用二分搜索，所需要的询问次数是[log2(n+1)]。信息检索的计算复杂性f(m，n)定义为所有可能的(m，n)-表结构和搜索策略下的复杂性的最小值。关于f(m，n)我们有如下结论:定理1.对每个n，存在数N(n)使得f(m，n)＝[log2(n+1)]对所有mN(n)成立。据此定理，对充分大的m，就信息检索来说，用“有序表结构”＋“二分搜索”是最有效的方法。利用下述两个引理,可得此定理的证明。[引理1]若m2n-l,n2，则对于按置换排序的表结构，无论采用何种策略，在最坏情形下要确定x是否在S中至少需要[log2(n+1)]次检查。[引理2]给定n，存在数N(n)满足:当mN(n)，且给定一个(m，n)-表结构，则存在有2n-1个键的集合K,使得对应于K的n元子集的表形成按置换排序的表结构。{证明}：设n个键的集合S={j1,j2,…jn}以某种次序存放在表结构中，如果j1<j2<...<jn，且ji存放在表中第ui项中，则S对应1,2,…,n的置换u1,u2,...,un。按置换排序的表结构中，每个n键集都对应同一置换。给定一个(m,n)-表结构，设={S|S是n个键的集合且对应的置换是u1,u2,...,un}。令q1=q2=…qt=2n-1,t=n!又设N(n)是Ramsey数r(q1,q2,...,qt;n)。假设mN(n)，我们把键空间M的n元子集（有序）分成t=n!个部分，每一部分恰对应一个集合,其中的n元子集的对应置换都是，根据Ramsey数r(q1,q2,...,qk;n)的定义，存在某个i和M的某个qi元子集(2n-1元子集)K,K的所有n元子集都属于某个。故引理2.2成立。至此，利用Ramsey数证明了引理2。对一个给定的(m,n)-表结构和搜索策略以及mN(n)，可找到满足引理2的集合K，再由引理1，即使限制在集合K上，在最坏情况下至少需要[log2(n+1)]次检查。因而有f(m,n)[log2(n+1)]。但我们知道有序表上的二分搜索的最坏情形复杂性是[log2(n+1)]，故有f(m,n