关于最小广播图的研究

1、关于最小播送图的研究梁英杰1，朱异1，褚泽帆21. 河海大学理学院，南京 211100；2. 河海大学计信院，南京 211100 摘要：本文研究的问题是如何在保证最短传播时间的前提下构建最小播送图，这是一个具有 复杂性与不确定性的问题。本文先后建立了“p 级单源树模型和“p 维超方体模型，得 到了问题一和问题二的结果，并证明了“p 维超方体就是最小的播送图。然后结合前面的 两种模型，并运用“动态保时删点的思想，巧妙地解决了问题三。最后，引入了播送函数 的概念，讨论了所有站点都是源点这一特殊的最小播送图，给出了一些已有结论和已经构造出的高位最小播送图实例。关键词： 最小播送图；p 级单源树；p

2、维超方体；动态保时删点；播送函数中图分类号：O29On the smallest radio diagramLIANG Yingjie1, ZHU Yi1, CHU Zefan2(1. College of science,Hohai University, Nanjing 211100;3. College of computer science,Hohai University, Nanjing 211100)Abstract: In this paper, the problem is how to ensure the shortest travel time under the pr

3、emise of building the minimum broadcast graph,this is a complex problem with uncertainty.This paper has established the p-class single-source tree model and p-dimensional super-cube model.By using them, first and the second questionand are solved and prove that the p-dimensional hypercube is the min

4、imum broadcast graph.Finally, the introduction of the concept of broadcasting function to discuss the source of all sites in this category are specific minimum broadcast graph and gives some conclusions and has already constructed a high minimum broadcast graph instance.Key words: Minimum broadcast

5、graph; P-class single-source tree; P-dimensional hypercube; Delete point dynamic protection;Broadcast function0引言设有 n 个网站，有假设干条线路把它们连接起来。每一个网站都能接收和传播信号，但其中只有 k 个 (k n) 网站能够发布信息。能发布信息的网站称为“源网站，简称“源。源网站产生的信息“+要在最短的时间内传播到其他网站，它的传播方式是这样的：拥有信息“+的网站每隔一秒钟“有选择地向与它相连但未获得该信息的某一个最多一个网站发送信 息。这里所谓“ 有选择 是指“ 使信息传播

6、的总时间最少 。对一般情形，至少需要消耗p = log2 n 秒时间。对给定的正整数 n 和 k (k n) ,由 n 个网站其中 k 个源网站构成的通讯系统，假设每个源网站发布的信息都能按上述传播方式在 p 秒内传播到所有网站，那么称该通讯系统为n,k播送图。每次只有一个源网站发布的一条信息在网站间传播，如果每隔 网站之间都有一条网络线，显然它是n,k播送图，但它的网络线太多了。网络线的条数以下简称“边数最少的成为n,k最小播送图，将它的边数记为 f (n, k ) 。当 n=8,k=1 时， log2 8 = 3 ，在图 1 中，标“+的为源网站，其他标“t的网站表示该网站在第 t 秒后获

7、得该信息，易知图 1 是8,1最小播送图，于是 f (8,1) = 7 。作者简介：梁英杰1988-，男，本科，从事数学与应用数学的研究. E-mail: HYPERLINK mailto:lyj_1988126 lyj_1988126 请设计n,k最小播送图，确定它的边数 f (n, k ) ：1对 k=1,2,3,4 给出 f (n, k ) 的数值；2求 f (2 p , 2 p ) ；3对 5 k n ，尽你的可能求 f (n, k ) 的值或讨论它的上、下界。1问题分析1.1对最小播送图的认识图 18,1最小播送图在分析完题目后，我们初步拟定用图论的相关知识来解答此题。我们可以把题目

8、中的最小播送图抽象为图论中的一个无向连通图G = (V , E) ，其中点集 V 表示网络中的 n 个站点，边集 E 那么表示站点与站点之间的连接线路。所谓播送就是网络中的某源点将其产生的信息传播到所有其他站点的过程。由题目要求，我们可以归纳出播送需要满足的约束条件： (1)每个顶点只能向与它相连的顶点传播信息； (2)每个顶点在同一时间，至多只能参与一对顶点之间的信息传递； (3)顶点之间传递一次信息需要的时间均为 1s。1.2 对源网站发送的信息“+的认识 按照此题原先提供的条件，针对源网站发布信息的方式，有如下两种可能： (1)所有源网站要发送的信息都相同，并且每次只有源网站发布的一条信

9、息在网站间传播；(2)不同的源网站同时发布不同的信息在网站间传播。 在查阅了大量相关资料后，我们知道，如果考虑情况二的话，问题会变得非常复杂，并且无法处理。基于简化模型的思想，在下面的讨论中，我们默认了情况一的可能。2模型假设1、所有源网站产生的信息“+都相同；2、每次只有一个源网站发布的一条信息在网络间传播；3、在初始时刻，要发布的信息“+只存在于一个源网站。3模型建立与求解3.1 模型准备由于本文需要用到大量的图论相关知识，在建立模型前，我们先简单介绍一些图论中的 根本概念，作为研究下文的知识准备。图：一个无向图是由某个非空有限集合 V(G)和 V(G)中某些元素的无序对集合 E(G)构成

10、的二元组，记为 G = (V , E) 。其中 V (G) = v1 , v2 vn 称为图 G 的顶点集或节点集，E (G) = e1 , e2 en 称为图 G 的边集。度：设 v V (G) ，G 中与 v 关联的边数称为顶点 v 的度，记作 d(v)。路：W = v0e1v1e2 ek vk ，其中 ei E(G),1 i k ，v j V (G), 0 j k ，ei 与 vi 1 , vi相关联，称 W 为图 G 的一条道路简称路，k 为路长，顶点 v0 和 vk 分别称为路 W 的起点和终点，而 v1 , v2 v k 1 称为它的内部顶点。圈：路 W 的顶点互不相同，那么 W

11、称为轨；起点和终点重合的轨叫做圈。树：连通的无圈图叫做树，记之为 T。3.2 p 级单源树模型我们把 2 个点的树称为 1 级单源树，见图 2，其中表上+的点称为它的源。下面我们采 用所谓的“生长法构造任意的 p 级单源树1。设已经得到 p 级单源树， p 1，它有 2p 个点，2p-1 条边，一个源。另外给出 2 p 个点，将 p 级单源树上的 2 p 个点分别与新给出的 2 p 个点中的一个相连，就得到 p+1 级单源树，它有 2 p +1 个点，2 p +1 1 条边，它的源还是原来 p 级单源树的那个源，例如图 3 是 2 级单源树，图 1 是 3 级单源树。由 p 级单源树的生长过程

12、可知，由源产生的信息“+可在 p 秒内传播到所有的点。并 且任一点包括源在内在获得信息的每隔一秒钟都不间断地将信息传播给与它邻接的某一 个点，一直到每一个点都获得信息为止。每一个 p 级单 源树 当 p 1 时有 2 p 1 个一度 点。 假设 2 p 1 n 2 p ， 此 时仍然 有pp = log2 n ，从 p 级单源树删去 2 n 个一度点后就得到一个拥有 n 个点的树，显然这个树产生的源信息也可以在 p 秒内传遍所有的站点。我们运用有关 p 级单源点的知识来解决第 一问中的相关问题。图 2 1 级单源树 图 3 2 级单源树3.2.1结论一: f (n,1) = n 1从上面的讨论

13、可知该结论是显然的，从 p 级单源树中删去假设干个一度点就可得到n,1最小播送图。3.2.2结论二： f (n, 2) = n 2显然，在n,1最小播送图中在 1 秒钟后获得信息的那个点例如在图 1，图 2 和图 3中标 1 的那个点也可以作为源，事实上由它产生的信息首先传播给原图中的源，以后的传播方式不变，故而我们得到 f (n,1) = f (n, 2) 。n 1,3.2.3结论三： f (n, 4) = n,当2 p1 n 5 2 p 3 时，当5 2 p3 n 2 p 时。证明：证明过程我们分成三个局部，在证明前我们先介绍一个原那么。“源优先，源中 v1 优先原那么：意思即为在信息传输

14、过程中假设下一步待选的节点中存在源节点，那么优先传给源节点；更进一步，假设存在假设干个源节点，那么优先传给源节点 v1 ，此外我们还规定，源信息在基图只含源节点的图中传播时，应优先选取与 v1 距离最短的路径， 例如在图 4 中，由 v3 传递信息到 v1 ，我们只考虑环上的路径，显然有两条路，这里我们选择红色的路径，因为这样可以使二者的距离最短。第一步，我们证明 f (n, 4) n ，图 4 信息传递图1234当 n = 2 p 时，构造 4 棵 p-2 级单源树，设它们的源分别为 v , v , v 和vp。再将 v1 , v2 , v3 , v4p连成一个 4 圈 v1v2v3v4v1

15、 ，参见图 5，我们得到一个 2个点的图，它有 2条边。容易证明v1 , v2 , v3 , v4 中任一个源产生的信息均可在 p 秒内传遍所有点。事实上，由对称性，只要考虑 v1 产生的信息传播的过程，第 1 秒将信息传给 v2 ，第 2 秒， v1和v2 将信息传给了 v3和v4 ， 余下 p-2 秒，这 4 个源 v1 , v2 , v3 , v4 可分别将信息传给 4 棵单源树的每一个点，于是得到：f (2 p , 4) 2 p图 5 p-2 级单源树假设 2 p 1 n 2 ，在图 中删去 2 p n 个一度点，即得n,4播送图， 故有： f (n, 4) n 。第二步，我们证明当5

16、 2 p 3 n 1 。用反证法，设此时有 f (n, 4) n 1，但由于播送图必须是连通的，故有 f (n, 4) = n 1 ，即它是一棵树，设 v1 , v2 , v3 , v4 是 4 个源，我们来证明存在两个源，例如 v1和v2 ，使得 v1 产生的信息至少在 3 秒后才能传至 v2 。如果存在两个源，它们的距离大于 2，结论显然成立；如果任两个源的距离不超过 2， 那么 v1 , v2 , v3 , v4 的邻接关系我们只能画出如图 6 一种情况。考虑由 v1 产生的信息， v4 最快 在 1 秒后获得， v2和v3 中至少有一个点最快在 3 秒后才能获得，不妨设这个点为 v2

17、，这就证明了我们的论断。图 6 邻接关系图于是由 v1 产生的信息传至 v2 后最多剩下 p-3 秒的时间。因此，以 v2 为源的单源树最多 是 p-3 级的，删去以 v2 为源的单源树，余下的最多 p-1 级单源树，这是因为由 v2 产生的信息 最快在 1 秒后才能传到其中某个点在图 5.5 中就是 v4 所以改图的点数 n 必须满足不等式：n 2 p 3 + 2 p 1 = 5 2 p 3 因此，当5 2 p 3 n 1 。 第三步，我们证明，当 2 p 1 n 1。先考虑当 n = 5 2 p 3 的情形，如图 7，我们构造 3 棵 2 p 3 级单源树时，设它们的源分别p 2为 v2

18、, v3 , v4 ；构造一棵 2级单源树，它的源为 v1 ，再将 v1 , v2 , v3 , v4 如图 3.5 的方式连接，这样，我们得到 n = 3 2 p 3 + 2 p 2 = 5 2 p 3 阶树。图 7 2 p 3 级单源树由 4 个源分别产生的信息按下述原那么传播：先传给未获得信息的源，在源中先传给 v1 ，即按“源优先，源中 v1 优先的原那么传播，于是无论哪个源产生的信息， v1 至多 2 秒后获 得此信息，并可开始传给以它为源的单源树上的各点，而在 3 秒后 v2 , v3 , v4 均可获得该信息，在余下的 p-3 秒内足够传至所有的点，故有： f (5 2 p 3

19、, 4) = n 1当 2 p 1 n 5 2 p 3 时 ，只要在上述情形得到的图中删去假设干个一度点就可以了，故此时有 f (n, 4) = n 1 。综上所述，结论三得证。n 1,3.2.4结论四： f (n, 3) = n,当2 p1 n 3 2 p 2 时，当3 2 p 2 n 2 p 时证明：显然，我们有 f (n, 3) f (n, 4) ，故由结论三可知， f (n, 3) n ，以下我们分两步证明结论四。第一步证明当 3 2 p 2 n 1 ，用反证 法证之， 设此时 f (n, 3) = n 1 ,于是得到的播送图是一棵树，在它的三个源 v1 , v2 , v3 中至少有两

20、个源，不妨设是 v1和v2 ，它们之间的距离不小于 2。于是由 v1 产生的信息至少经过 2 秒才能到达 v2 。以v2 为源的单源树最多是 p-2 级的，删去这个单源树，余下最多是 p-1 级单源树，于是n 2 p 2 + 2 p 1 = 3 2 p 2 ，因此，当3 2 p 2 n n 1第二步证明当 2 p 1 n 3 2 p 2 时， f (n, 3) = n 1 ，先考虑 n = 3 2 p 2 的情形，如图8，我们构造 3 棵 2 p 2 级单源树，设它们的源分别是 v , v 和v，再将 v 和v连接，v 和 v 连1231223接，由 v1 , v2或v3 分别产生的信息按“源

21、优先，源中 v1 优先的原那么传播，均可在 p 秒内将信息传到达所有的点，故有：f (3 2 p3 , 3) = n 1图 8 2 p 2 级单源树当 2 p 1 n 3 2 p 2 时，在上述情形得到的图中删去假设干个 1 度点就可以了，故此时有：f (n, 3) = n 1 。综上所述，结论四也是正确的。至此，第一个问题得到了圆满的解答。3.3 p 维超立方体模型一维超方体就是由图 2 所示的两个点的图。2 维超方体是由两个一维超方体，分别连接 它们对应点之间的边得到的，如图 9 就是一个 2 维超方体。类似地，将两个 2 维超方体对应 点连接起来就得到了 3 维超方体，参见图 10。一般

22、情形，假设已经得到 p 维超方体2，将两个 p 维超方体对应的点连接起来就得到 p+1 维超方体。图 9 2 维超方体 图 10 3 维超方体p 维超方体还可以采用下述方法得到，设：v = (a1 , a2 , a p ) a1 , a2 ,a p为0或1v 是 p 维0,1向量集合，将 v 中每一个向量作为点，两个不同的点邻接当且仅当它们恰有 p-1 个分量对应相等，这样得到的图就是 p 维超方体。由 p 维超方体的构造可知，它恰有 2 p 个点，每一个点的度均等于 p，于是它的边数为1 p 2 p = p 2 p 1 。2下面我们来证明 p 维超方体是 (2 p , 2 p ) 最小播送图

23、。由 p 维超方体的对称性，只要考虑任一点产生的信息传播途径，对一维超方体来说，某 一点产生的信息经过 1 秒能传到另一点，由 2 维，3 维，p 维超方体“归纳构造过程可 知，经过 p 秒信息可以传到达 p 维超方体的每一个点。很显然，产生信息的那一个点必须连续不间断地传送 p 次信息，即它的度至少是 p，由于每一点都是源，于是每一点的度至少是 p，因此 (2 p , 2 p ) 最小播送图的边数不少于 p 2 p 1 ，所以 p 维超方体就是 (2 p , 2 p ) 最小播送图。结论五： f (2 p , 2 p ) = p 2 p 1 ，且 p 维超方体就是 (2 p , 2 p )

24、最小播送图。 动态保时删点关于一般情况 f (n, k ) 的最小播送图的研究是一个非常复杂，计算量庞大的问题，在这 里，我们可以给出一个关于 f (n, k ) 的粗略的估计：n 1 f (n, k ) 1 k (k 1) + n k2证明：当 k 2t , t Z 时，对于一个固定的 k 值，对任意的 n ，必有 k 2a1 n k 2a ， 其中， a 1, a Z 。考察 n 值的变化情况。3.4.1情况一当 n = k 2a 时，按“p 级单源树-基图模型，构造基图和 k 棵 a 级单源树，那么播送图的总边数为基图边数与单源树边数之和。基图边数为 f (k , k ) ，即保证每个源

25、产生的信息可在alog2 k 秒内传至其他所有源节点。每棵 a 级单源树的边数为 2 1 ，播送图的总边数为f (n, k ) = f (k , k ) + k (2a 1) = f (k , k ) + n k下证该播送图可以保证任意源 vi 产生的信息均可在log2 n 秒内传至所有节点，并且信息“+从源 vi 传播至其他 k 1个源耗时在log2 k 内。i对于每棵 a 级单源树，源节点产生的信息可在 a 秒内传至其他所有点。所以，任意源va产生的信息均可在log2 k + a 秒内传至所有节点。又 log 2 n = log 2 (k 2 ) = log2 k + a ， 下面我们证明

26、: log2 n = log2 k + a ，即任意源 vi 产生的信息均可在log2 n 秒内传至所有节点。2证明：令2i n = k 2a 2i +1 ，那么有logn = i + 1且2i a k 2i a +1，于是进一步有log2 k = i a + 1，从而得到：log2 n = log2 k + a 。为了完本钱问题的证明，我们先后证明如下两个定理：1定理 1f (k, k ) k (k 1)(k = 2, 3, .)21证明：由 k 个源节点两两相连构成的完备图的边数为 2 k (k 1) 。而 (k , k ) 最小播送图的边数必不超过完备图的边数，故上述定理成立。定理 2f

27、 (k , k ) f (k ,1)证明：由源的定义知上述定理显然成立。 由上述两个定理，我们可以得出如下不等关系：f (k ,1) + n k f (k , k ) + n k =f (n, k ) 1 k (k 1) + n k ，2又 f (k ,1) = k 1 ，故 n 1 3.4.2情况二f (n, k ) 1 k (k 1) + n k 。2当 n k 2a 时，首先证明如下定理：k 2a 1 2 p k 2a定理 3：p Z ，使证明：不妨设 2b 1 k 2b , b 1, b Z ，令 p = a + b 1 ，那么k 2a 1 2b 1 2a = 2a +b 1 = 2

28、p 。1当 2 p n k 2a 时，沿用上面证明过程中的符号和表达式，有：2 2，2 p n k 2a 2b 2a = 2a +b = 2 p +1 ，从而logn = log (k 2a ) = p + 1即最小信息传播时间与 n = k 2a 时相同。此时最小播送图可由上述播送图中的单源树去除k 2a n 个 1 度点即得。2当 k 2a 1 n 2 p 时，logn = log 2 p = p ，故logn =log (k 2a ) 1 ，222 2最小信息传播时间比 n = k 2a 时少 1 秒。此时需要考虑当在上述播送图中去除 k 2a n 个一度点时是否可以保证信息仍在 p 秒

29、内传完，即保证“减点不减时。考虑 n 的极大值 n = 2 p 时的情形，我们设计一种信息传播方案见图 11，可以保证在 p 秒内传完。图 11 信息传播方案此时，在上述最小播送图去除假设干点后，图中的假设干 a 级单源树变成 a 1级单源树。 不妨设此时有t 棵 a 1级单源树， s 棵 a 级单源树通过方程组t 2a 1 + s 2a = n = 2 pt + s = k解得：t = 2k 2 p a+1 = 2k 2bs = 2b k设源节点 v1 , v2 , , vs 为 a 级单源树的源，源节点 vs +1 , , vk 为 a 1 级单源树的源，令c = 1 t = k 2b1

30、，信息从源节点 v (1 i s) 开始传播的情况：2首 先 在 源 节 点iv1 , v2 , , vs , vs +1 , , vs + c之 间 传 播 ， 所 需 时 间 为 ：log (s + c) = log 2b1= b 1秒。在第b 秒内，源节点 v , v , , v 将信息分别传至各自2 2 1 2 sa 级单源树中的 第1级节点 ；而源节点 vs +1 , , vs + c 那么 将信息分别一对一传至源节点vs + c +1 , , vk 。从b + 1 秒开始，源节点 v1 , v2 , , vs 及各自单源树中的第 1 级节点分别将信息传至单源树中所有其他节点，源节点

31、 vs +1 , , vk 也分别将信息传至各自单源树中所有其他节点，v1 , v2 , , vs 在 b-1 秒之后共传输了 a 秒，vs +1 , , vs + c 传输了 1+a-1秒，而 vs + c +1 , , vk在 b 秒之后传了 a-1 秒，故共耗时b 1 + a = b 1 + 1 + (a 1) = b + (a 1) = p信息从源节点 vi (s + 1 i k ) 开始传播的情况：不妨设从源节点 vs +1 开始传播，信息首先在源节点 v1 , v2 , , vs , vs +1 , , vs + c 之间传播，2 2所需时间为log (s + c) = log 2

32、b1 = b 1秒。在b 秒时，源节点 v1 , v2 , , vs 将信息分别传至各自单源树中的第 1 级节点，源节点 vs +1 , , vs + c 将信息分别传至源节点 vs + c +1 , , vk 。b + 1 秒时，源节点 v1 , v2 , , vs 及各自单源树中的第 2 级节点分别将信息传至单源树中的第2 级节点，源节点 vs +1 , , vk 也分别将信息传至各自单源树中第 2 级节点，由于都是第 2 级节点，故传完所需时间为 a 2 秒。共耗时(b + 1) + (a 2) = a + b 1 = p综上， n = 2 p 时可以保证信息在 p 秒内传完。p当 k

33、2a 1 n 2 p时，log2 n = log2 2= p ，此时最小播送图可由n = 2 p时的最小播送图中的单源树去除假设干个一度点即得。 由情况一和情况二的证明我们可以得出： n 1 f (n, k ) 1 k (k 1) + n k2在给出了 f(n,k)的上、下界之后，我们希望能够发现一些特殊的规律，这些规律可能无 法很好的适用于所有情况，只是凤毛麟角的一些发现，但是，在某些特定场合下，我们确实 是可以用到这些结论，到达解决一类问题的目的，下面我们不假证明的给出这些结论：1 f (n, 2m ) n + (m 2) 2m 1 , 这里m为自然数，n 2m ；2 f (n, k )

34、= n 1 2 p 1 n 2 p1 + 2 p k +1 ；n 1,n,3 f (n, 5) =当2 p 1 n 9 2 p 4 时当9 2 p 4 n 3 2 p 2 时n + 1,当3 2p 2 n 7 2p3 时n + 2,当7 2 p 3 n 2 p 时4 f (n, 6) n + 35关于函数 f (n, k ) 的单调性问题，显然有下述不等式：f (n, k ) f (n + 1, k )这里1 k n ，这从源的定义立即得到，但对于给定的 k，一般来说对与 n 并不是单调的。 关于播送函数 B(n) 的特殊研究定义：在日常生活中，我们研究得最为广泛的一种情况往往是播送图中的每一

35、个站点都 可以发送信息即每一个站点都是源站点。这是 f (n, k ) 中的 k 等于 n 的一个特殊情况，也是富有意义和研究价值的一种情况。我们把：B(n) =f (n, n)定义为播送函数3，历史上对播送函数的研究已经有很多了，当 n 比拟小时，人们可以 通过画图的方式，来求出一些简单的播送函数的值见表 1：表 1 一些简单播送函数的值n123456789101112131415161718B(n)01245681210121315182124322223在问题二中，我们求得的 f (2 p , 2 p ) = p 2 p 1 是 n = 2 p 时的一种特殊的播送函数。在实 际研究过程中

36、，我们往往研究的是 B(2 p j) 4这种特殊形式的播送函数，并得出了它们的上界或者下界。下面，我们得出了一些初步的结论： 1 (k n 2k n 1 B(2k 1) = 22k + 2 1 (k 1) n + 2n当k为偶数时，当k为奇数时， 22k + 22 B(2k 2) = (k 1)(2k 1 1)1 2(2k 4)3 B(2k 3) (2k + 1+ (k 2)(2k 3)k4 1 ( 2(2 4) + (k 2)(2k 4) B(2k 4) (k 2)(2k 1 2) + 2k 2 12k + 1k 15 B(2k 6) (k 2)(2k 1 3) + 2 3k6Bn的上界可以表示成如下的分段不等式形式： 3n log16 2 2n log 92n + 3n , (8m n 9m)8n + 14n , (9m n 10m)45 nn log n +