Ramsey定理的应用VIP

1、精品文档第一节ramsey定理在网络规划中的应用一、基础知识定义1.给定正整数n, r和图hi, h2,，hr,用r种颜色对完 全图kn的所有边进行着色，由第i色边构成的子图记为gi.如果存在 一种着色方法，使得对所有的i(1wgr)都有hi gi,则称kn对于(hi, h2,，hr)可r 着色.如果hl h2hr h,则简称kn对于h可 r 一着色.定义2.使得kn对于(kpi，kp2,，kpr)不能r着色的最小正整数n 称为(经典)ramsey 数 r( pi,p2,pr).如果 pi= p2= = pr= p,则把 r( pi, p2,., pr)简写为 rr(p).定义3.使得kn对于

2、(hi, h2,，hr)不能r 着色的最小正整数 n 称为广义 ramsey 数 r(hi, h2,，hr).如果 hi h2 hr h, 则把r(hl, h2,，hr)简写为rr(h).定理 i. r(c4,c4)=6定理 2. r(c4,c4,c4)=ii定理3.若一个n个顶点的图至少有-n3/21n条边，则它总包含 24c4。二、分组交换网的设计分组交换网是采用分组交换技术的网络，它从终端或计算机接收 报文，把报文分割成分组，并按某种策略选择最佳路径在网中传输， 到达目的地后再将分组合并成报文交给目的终端或计算机。分组交换 技术在网络设计中被广泛采用。用顶点表示通信设备，用边表示通信链路

3、，这样得到一个图。假 定该图是完全图，即任意两点间都有一条边相连。在某些应用场合， 顶点两两配对作为一个整体。我们希望保证在某些链路出故障不能使 用时，任两对配对顶点间都至少有一条链路畅通无阻。设顶点xi,x2组成一对，yi,y2为一对，zi ,z2为一对，且故障发生 在诸如微波塔、中继站等中间设施上。在此类设施上的故障将影响所 有共享该设施的链路。对共享同一个中间设施的链路，我们用同一种 颜色来标记它们.如上图表示一个有三种中间设施的通信网络。在图 中，若标记红色的中间设施出了故障.那么在顶点对xl,x2和顶点对 z1 ,z2之间将没有可用的链路，而这对应于下列事实：四条边(xi,zj)构成

4、 一个单色的c4(4个顶点的回路)。一般来说，设计一个网络需决定中 间设施的数量以及哪个链路使用哪个设施。止匕外，在任何一个中间设 施损坏时，我们希望所设计的网络中任两对配对顶点间有一个可使用的链路。根据上面的讨论，我们应该避免出现单色的c4。已知ramsey数r(c4,c4)=6。因此，如果只有两个中间设施， 那么存在一个5个顶点的网络使得可以安排一种不出现单色c4的连接方式。已知ramsey数r(c4,c4,c4)=11,所以存在一个10个顶点 的网络，它使用三个中间设施且没有单色的 c4。前面说过，设计一个网络需要决定中间设施的数量以及哪个链路 使用哪个设施。中间设施是很昂贵的，因而希望

5、使其数量尽可能少。 所以自然要问：如果有一个n个顶点的网络，在不出现单色c4的条件 下中间设施的最少个数是多少？换句话说，满足r(c4,c4,c4)n的最 r小的r是多少？比如对上图，n=6 ,由于r(c4,c4)=6 , r(c4,c4,c4)=11所以r=3 ,即我们需要3个中间设施般情况下，若n个顶点的图的n(n-1)/2条边分成r种颜色类,由鸽巢原理，则必存在某个类至少有 血-些条边。我们要选择 r得不存在包含有2n3/2 :n条边的类，因此，选r使其满足就行，即满足上述不等式的最小r就是所需要的最少中间设施数。第二节 ramsey 定理在信息检索中的应用信息检索是计算机科学中一个基本

6、而又重要的问题。如何组织数据，使用什么样的查找方法对检索的效率有很大的影啊。我们所熟知的在有序表结构上的二分搜索算法是一种很有效的方法，但二分搜索是最好的算法吗 ?假设一个表有n 个不同的项，其元素取自键空间 m=1,2, ，m. 我们希望找到在表中存储m 的任意 n 元子集 s 的方法，使得容易回答下述询问：x在s中吗？如何存储m的n元子集的规则称为一个表结构或(m ， n)- 表结构。最简单的表结构是有序表结构，它是按上升序列出 s 中的元素。更一般的是按置换排序的表结构，它是固定1,2，,n的一个置换，根据此置换的次序列出s中的元素。信息检索的计算复杂性依赖于表结构和搜索策略。 复杂性的

7、度量是最坏情形下确定x 是否在 s 中所需要的询问次数。 例如， 对于有序表结构，如果用二分搜索，所需要的询问次数是 log 2(n+1) 。信息检索的计算复杂性f(m , n)定义为所有可能的(m, n)-表结构和搜索策略下的复杂性的最小值。关于 f(m ， n) 我们有如下结论:定理1.对每个n,存在数n( n)使得f(m , n) = log 2(n+1)对所有 m n (n) 成立。据此定理，对充分大的 m ，就信息检索来说，用“有序表结构”“二分搜索”是最有效的方法。利用下述两个引理,可得此定理的证明。引理 1 若 m 2n- l , n 2 ，则对于按置换排序的表结构，无论采用何种

8、策略，在最坏情形下要确定x 是否在 s 中至少需要log 2(n+1) 次检查。引理 2 给定 n ，存在数 n(n) 满足 :当 m n(n) ，且给定一个(m ，n)-表结构，则存在有2n-1个键的集合k,使得对应于k的n元子集 的表形成按置换排序的表结构。证明：设n个键的集合s=j 1,j2/ jn 以某种次序存放在表结构中， 如果ji j2 . j n,且ji存放在表中第ui项中，则s对应1,2,n的 置换 u 1,u 2, ., un 。按置换排序的表结构中， 每个 n 键集都对应同一置换。 给定一个(m,n)- 表结构，设(u1,u2,.,un) =s|s 是 n 个键的集合且对应

9、的置换是u1 ,u2, ., un。令 qi=q 2=qt=2n-1,t=n!又设 n(n) 是 ramsey 数 r(q 1 ,q2,.,qt;n) 。假设 m n (n) ，我们把键空间 m 的 n 元子集(有序)分成t=n! 个部分，每一部分恰对应一个集合(u1,u2,.,un), 其中的 n 元子集的对应置换都是(u1,u2,.,un) ， 根据ramsey数r(q i,q2,qk；n)的定义，存在某个i和m的某个qi元 子集 (2n-1 元子集 )k,k 的所有 n 元子集都属于某个(u1,u2,.,un) 。故引 理 2. 2 成立。至此， 利用 ramsey 数证明了引理2 。 对一个给定的 (m,n)- 表结构和搜索策略以及m n (n),可找到满足引理2的集合k,再由引理 1 ，即使限制在集合k 上，在最坏情况下至少需要log 2(n+1) 次检查。 因而有 f(m,n) log 2(n+1) 。 但我们知道有序表上的二分搜索的最