Ramsey定理的应用

1、第一节 Ramsey定理在网络规划中的应用一、基础知识定义1. 给定正整数n，r和图H1，H2，Hr，用r种颜色对完全图Kn的所有边进行着色，由第i色边构成的子图记为Gi.如果存在一种着色方法，使得对所有的i(1ir)都有HiGi，则称Kn对于(H1，H2，Hr)可r着色.如果HlH2HrH，则简称Kn对于H可r着色.定义2. 使得Kn对于(, )不能r着色的最小正整数n称为(经典)Ramsey数R().如果=，则把R()简写为Rr(p).定义3. 使得Kn对于(H1，H2，Hr)不能r着色的最小正整数n称为广义Ramsey数R(H1，H2，Hr).如果HlH2HrH，则把R(Hl，H2，Hr

2、)简写为Rr(H).定理1. R(C4,C4)=6定理2. R(C4,C4,C4)=11定理3.若一个n个顶点的图至少有条边，则它总包含C4。二、分组交换网的设计 分组交换网是采用分组交换技术的网络，它从终端或计算机接收报文，把报文分割成分组，并按某种策略选择最佳路径在网中传输，到达目的地后再将分组合并成报文交给目的终端或计算机。分组交换技术在网络设计中被广泛采用。用顶点表示通信设备，用边表示通信链路，这样得到一个图。假定该图是完全图，即任意两点间都有一条边相连。在某些应用场合，顶点两两配对作为一个整体。我们希望保证在某些链路出故障不能使用时，任两对配对顶点间都至少有一条链路畅通无阻。 设顶点

3、x1,x2组成一对，y1,y2为一对，z1 ,z2为一对，且故障发生在诸如微波塔、中继站等中间设施上。在此类设施上的故障将影响所有共享该设施的链路。对共享同一个中间设施的链路，我们用同一种颜色来标记它们.如上图表示一个有三种中间设施的通信网络。在图中，若标记红色的中间设施出了故障.那么在顶点对x1,x2和顶点对z1 ,z2之间将没有可用的链路，而这对应于下列事实:四条边(xi,zj)构成一个单色的C4(4个顶点的回路)。一般来说，设计一个网络需决定中间设施的数量以及哪个链路使用哪个设施。此外，在任何一个中间设施损坏时，我们希望所设计的网络中任两对配对顶点间有一个可使用的链路。根据上面的讨论，我

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)=1

5、1所以r=3，即我们需要3个中间设施。一般情况下，若n个顶点的图的n(n-1)/2条边分成r种颜色类，由鸽巢原理，则必存在某个类至少有条边。我们要选择r使得不存在包含有条边的类，因此，选r使其满足<就行，即满足上述不等式的最小r就是所需要的最少中间设施数。第二节 Ramsey定理在信息检索中的应用 信息检索是计算机科学中一个基本而又重要的问题。如何组织数据，使用什么样的查找方法对检索的效率有很大的影啊。我们所熟知的在有序表结构上的二分搜索算法是一种很有效的方法，但二分搜索是最好的算法吗? 假设一个表有n个不同的项，其元素取自键空间M=1,2,.，m.我们希望找到在表中存储M的任意n元子集

6、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)使得

7、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

8、存放在表中第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)。但我们知道有序表上的二分搜索的最坏情形