Ramsey定理的应用

第一节Ramsey定理在网络规划中的应用一、基础知识定义1.给定正整数n，r和图H1，H2，…，Hr，用r种颜色对完全图Kn的所有边进行着色，由第i色边构成的子图记为Gi.如果存在一种着色方法，使得对所有的i(1≤i≤r)都有HiGi，则称Kn对于(H1，H2，…，Hr)可r－着色.如果HlH2…HrH，则简称Kn对于H可r－着色.定义2.使得Kn对于(1pK,2pK,…,rpK)不能r－着色的最小正整数n称为(经典)Ramsey数R(rppp,...,,21).如果1p=2p=…=rp=p，则把R(rppp,...,,21)简写为Rr(p).定义3.使得Kn对于(H1，H2，…，Hr)不能r－着色的最小正整数n称为广义Ramsey数R(H1，H2，…，Hr).如果HlH2…HrH，则把R(Hl，H2，…，Hr)简写为Rr(H).定理1.R(C4,C4)=6定理2.R(C4,C4,C4)=11定理3.若一个n个顶点的图至少有nn41212/3条边，则它总包含C4。二、分组交换网的设计分组交换网是采用分组交换技术的网络，它从终端或计算机接收报文，把报文分割成分组，并按某种策略选择最佳路径在网中传输，到达目的地后再将分组合并成报文交给目的终端或计算机。分组交换技术在网络设计中被广泛采用。用顶点表示通信设备，用边表示通信链路，这样得到一个图。假定该图是完全图，即任意两点间都有一条边相连。在某些应用场合，顶点两两配对作为一个整体。我们希望保证在某些链路出故障不能使用时，任两对配对顶点间都至少有一条链路畅通无阻。x2x1z1z2y2y1设顶点x1,x2组成一对，y1,y2为一对，z1,z2为一对，且故障发生在诸如微波塔、中继站等中间设施上。在此类设施上的故障将影响所有共享该设施的链路。对共享同一个中间设施的链路，我们用同一种颜色来标记它们.如上图表示一个有三种中间设施的通信网络。在图中，若标记红色的中间设施出了故障.那么在顶点对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的条件下中间设施的最少个数是多少?换句话说，满足),...,,(444rCCCRn的最小的r是多少?比如对上图，n=6，由于R(C4,C4)=6，R(C4,C4,C4)=11所以r=3，即我们需要3个中间设施。一般情况下，若n个顶点的图的n(n-1)/2条边分成r种颜色类，由鸽巢原理，则必存在某个类至少有r1)/2-n(n条边。我们要选择r使得不存在包含有nn41212/3条边的类，因此，选r使其满足r1)/2-n(nnn41212/3就行，即满足上述不等式的最小r就是所需要的最少中间设施数。第二节Ramsey定理在信息检索中的应用信息检索是计算机科学中一个基本而又重要的问题。如何组织数据，使用什么样的查找方法对检索的效率有很大的影啊。我们所熟知的在有序表结构上的二分搜索算法是一种很有效的方法，但二分搜索是最好的算法吗?假设一个表有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)]对所有mN(n)成立。据此定理，对充分大的m，就信息检索来说，用“有序表结构”＋“二分搜索”是最有效的方法。利用下述两个引理,可得此定理的证明。引理1若m2n-l,n2，则对于按置换排序的表结构，无论采用何种策略，在最坏情形下要确定x是否在S中至少需要[log2(n+1)]次检查。引理2给定n，存在数N(n)满足:当mN(n)，且给定一个(m，n)-表结构，则存在有2n-1个键的集合K,使得对应于K的n元子集的表形成按置换排序的表结构。证明：设n个键的集合S={j1,j2,…jn}以某种次序存放在表结构中，如果j1j2...jn，且ji存放在表中第ui项中，则S对应1,2,…,n的置换u1,u2,...,un。按置换排序的表结构中，每个n键集都对应同一置换。给定一个(m,n)-表结构，设),...,,(21nuuu={S|S是n个键的集合且对应的置换是u1,u2,...,un}。令q1=q2=…qt=2n-1,t=n!又设N(n)是Ramsey数r(q1,q2,...,qt;n)。假设mN(n)，我们把键空间M的n元子集（有序）分成t=n!个部分，每一部分恰对应一个集合),...,,(21nuuu,其中的n元子集的对应置换都是),...,,(21nuuu，根据Ramsey数r(q1,q2,...,qk;n)的定义，存在某个i和M的某个qi元子集(2n-1元子集)K,K的所有n元子集都属于某个),...,,(21nuuu。故引理2.2成立。至此，利用Ramsey数证明了引理2。对一个给定的(m,n)-表结构和搜索策略以及mN(n)，可找到满足引理2的集合K，再由引理1，即使限制在集合K上，在最坏情况下至少需要[log2(n+1)]次检查。因而有f(m,n)[log2(n+1)]。但我们知道有序表上的二分搜索的最坏情形复杂性是[log2(n+1)]，故有f(m,n)=[log2(n+1)]，这就证明了定理1，从而知道二分搜索对大的键空间是最好的检索方法。参考文献：[1]A.C.Yao.ShouldTablesBeSorted?J.ACM28(1981)，pp.615-628