Ramsey定理的应用

《Ramsey定理的应用》由会员分享，可在线阅读，更多相关《Ramsey定理的应用（6页珍藏版）》请在装配图网上搜索。

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

2、能r 着色的最小正整数 n称为广义Ramsey数R(Hi, H2，Hr).如果H H三H H, 则把R(H|, H2，,Hr)简写为Rr(H).定理 1. R(C4,C4)=6定理 2 R(C4,C4,C4)=11定理3.若一个n个顶点的图至少有In3/2 -丄n条边，则它总包含C4。24二、分组交换网的设计分组交换网是采用分组交换技术的网络，它从终端或计算机接收 报文，把报文分割成分组，并按某种策略选择最佳路径在网中传输， 到达目的地后再将分组合并成报文交给目的终端或计算机。分组交换 技术在网络设计中被广泛采用用顶点表示通信设备，用边表示通信链路，这样得到一个图。假 定该图是完全图，即任意两

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

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

5、个顶点的网络，在不出现单色 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种颜色类，由 鸽巢原理，则必存在某个类至少有 血卫2条边。我们要选择r使得r不存在包含有丄n3/2条边的类，因此，选r使其满足24n(n-1)/2.1 3/21v nnr 24就行，即满足上述不等式的最小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中所需要的询问次数。例如，对于有序 表结构，如果用二分搜索，所需要的询问次数是 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中

8、至少需要log2(n+1)次检查。引理2给定n，存在数N(n)满足:当m_N(n)，且给定一个(m, n)- 表结构，则存在有2n-1个键的集合K,使得对应于K的n元子集的表 形成按置换排序的表结构。证明：设n个键的集合S=ji,j2,jn 以某种次序存放在表结构中， 如果ji j2 . jn,且ji存放在表中第Ui项中，则S对应1,2,n的置 换 Ui,U2,，Un。按置换排序的表结构中，每个n键集都对应同一置换。给定一个 (m,n)-表结构，设(u1,U2,.,un)=S|S是n个键的集合且对应的置换是Ui ,U2, ., Un。令 q1=q2= qt=2n-1,t二n!又设 N(n)是

9、Ramsey数 r(q1,q2,.,q;n)。假设 m_N (n)，我们把键 空间M的n元子集(有序)分成t=n!个部分，每一部分恰对应一个 集合(u1,U2,.,un),其中的n元子集的对应置换都是-(U1,U2,.,Un)，根据 Ramsey数 心山2,.耳；n)的定义，存在某个i和M的某个q元子集(2n-1 元子集)K,K的所有n元子集都属于某个 心山2,.也)。故引理2. 2成立。至此，利用Ramsey数证明了引理2。对一个给定的(m,n)-表结构 和搜索策略以及mN (n),可找到满足引理2的集合K，再由引理1, 即使限制在集合K上，在最坏情况下至少需要log 2(n+1)次检查。因 而有f(m,n) logyn+1)。但我们知道有序表上的二分搜索的最坏情形复杂性是 log 2(n+1) ，故有 f(m,n)=log 2(n+1) ，这就证明了定理 1，从 而知道二分搜索对大的键空间是最好的检索方法。参考文献：1 A.C. Yao. Should Tables Be Sorted? J. ACM 28(1981，) pp.615-628