(n,k)最小广播图的设计方案分析

蒋俊豪 王 儒 何佳龙

(河海大学,江苏 南京 210098)

【摘 要】(n,k)最小广播图问题是一个图论问题。源网站每一秒只能向某一个网站发布它所具有的信息。由n个网站(其中k个源网站)构成的通讯系统,若每个源网站发布的信息“+”都能按上述传递方式在[log2n]秒内传播到所有网站,则称该通讯系统为(n,k)广播图。结合图论的基本理论与分析手段,引用p级单源树的思想,引入p级超方体的思想进行推理。

教育期刊网 http://www.jyqkw.com
关键词 (n,k)最小广播图;图论;p级单源树;p级超方体

0 引言

(n,k)最小广播图问题是一个图论问题。在所有广播网站中,有若干条线路把他们连起来。其中的每一个网站都能接收信息和传播信息,但只有部分网站能够发布信息,即源网站。源网站每一秒只能向某一个网站发布它所具有的信息。(n,k)广播图的通讯系统是由n个网站(其中k个源网站)构成的通讯系统,每个源网站发布的信息“+”都能按上述传递方式在[log2n]秒内传播到所有网站保证在规定时间内减少网站间的线路数,使网站间铺设的线路最少,形成(n,k)-最小广播图,减少花销。

1 模型

1.1 k= 1时

1.1.1 第一种算法

第1秒时,“源网站”A将信息“+”传给网站B,增加一条边(L1=1)(见图5-1),第2秒时,A、B再分别将信息传给另两个网站C、D,边数再增加两条(L2=)(见图5-2)第3秒时,A、B、C、D再分别将信息传给另外四个网站E、F、G、H,边数再增加4条(L=22图5-3),以后依次类推。当边数最少时,除了源网站之外,则边数的增加数就等于拥有信息的网站数。

则有结论,k=1时,广播网络的边数为f(n,1)=1+21+22+…2[log2n]-2+(n-2[log2n]-1)=n-1

1.1.2 第二种算法

p级单源树:p级单源树有2p个点,2p-1条边,一个源。

p+1级单源树:另外给出2p个点,将p级单源树上的点分别与新给出的2p个点中的一个相连接,就得到p+1级单源树。

当p>1时,p级单元树有2p-1个根结点。单个源产生的信号(+)可以在p秒内传给所有的点。则必然存在某一个数值n满足:2p-1<n≤2p,因此,在删去2p-n个点之后,单个源产生的信号(+)仍可以在p秒内传给剩余的n个点。则最终n个点的线路数为f(n,1)=2p-1-(2p-n)=n-1。

1.2 k=2时

1.2.1 第一种算法

k=2时,广播网络的边数f(n,1)=1+21+22+23+...+2[log2n]-2+(n-2[log2n]-1)=n-1。

1.2.2 第二种算法

与第一种模型的分析方法相同,则有最终线路个数为f(n,1)=2p-1-(2p-n)=n-1。

1.3 k=3时

当k=3时,源网络可以有两种排列方式。(设A的信号为1,B的信号为2,C的信号为3)。要使边数最少,先用最短的时间在源网站之间传播,使所有源网站都拥有所有信息,再由源网站将所有信息传播给其他网站即可。

1.3.1 第一种情况

每个源传播的方式完全相同,每个源网站传播出的网站数相等,为1+21+22+...+2p-3=2p-2-1。这就要求网站的总数n≤3+3*(2p-2-1)=3*2p-2 。在满足时间要求的范围内,n≤3+3*(2p-2-1)=3*2p-2,则减去算出的多余的网站,减去每一个网站对应的就少了一条边,则有最终线路个数f(n,3)=2+(n-3)=n-1。当网站总数n>3*2p-2时,这种做法不满足原题要求,以上结论不能成立。

1.3.2 第二种情况

每个源传播的方式完全相同,每个源网站传播出的网站数相等,为1+21+22+...+2p-2=2p-1-1。

这就要求网站的总数n≤3+3×(2p-1-1)=3×2p-1,在满足时间要求的范围内,n≤3+3*(2p-2-1)=3*2p-1,则减去算出的多余的网站,减去每一个网站对应的就少了一条边,则有最终线路个数f(n,3)=3+(n-3)=n。

当网站总数n>3*2p-1时,这种做法不满足要求,以上结论不能成立。

当3*2p-2<n≤2p 时,f(n,3)=n;

综上所述,

1.4 k=4时

当k=4时,源网络可以有四种排列方式。(设A的信号为1,B的信号为2,C的信号为3,D的信号为4)。

1.4.1 第一种情况

每个源传播的方式完全相同,每个源网站传播出的网站数相等,为1+21+22+...+2p-4=2p-3-1。

这就要求网站的总数n≤4+4×(2p-3-1)=4×2p-3,在满足时间要求的范围内,n≤4+4×(2p-3-1)=4×2p-3=2p-1,则减去算出的多余的网站,减去每一个网站对应的就少了一条边,则有最终线路个数f(n,4)=3+(n-4)=n-1。

当网站总数n>2p-1时,这种做法不满足原题要求,以上结论不能成立。

1.4.2 第二种情况

只考虑在源网站之内的传递信号过程,时间最短情况,由每个网站传播出的网站数为1+21+22+...+2p-5=2p-4-1,所以这种情况下,n=8+8*(2p-4-1)=8*2p-4=2p-1,f(n,4)=7+n-8=n-1。

1.4.3 第三种情况

只考虑在源网站之内的传递信号过程,时间最短情况(见图5-12),同理可知:2p-2-1,所以这种情况下,n=4+4*(2p-2-1)=2p,f(n,4)=4+n-4=n;

1.4.4 第四种情况

由于第四种情况是前两种情况(链状)与第三种情况(环状)的结合,因此其结果可以被前面结果包含,不作具体分析。

综上所述,

观察以上4种k的不同取值,可将(n,k)最小广播图设计问题简化为图集G(V,E)连通的问题,其中顶点数V=n,f(n,k)=min{E},保持各顶点互相连通的情况下,使得边数最小。其数学模型为:

Obj f(n,k)=min{E}

s.t. k’|t=0=k

max kt’=2kt-1’

∑t≤[log2n]

教育期刊网 http://www.jyqkw.com
参考文献

[1]吴朝福.关于最小广播图研究[J].计算机学报,1994(2):147-151.

[2]孙光耀.最小广播图研究[J].河北师范大学学报:自然科学版,1990(4):62-68.

[3]李贵祥.n维超正方体中几何元素的数量关系[J].天津纷织工学院学报,1996(1):72-74.

[责任编辑:刘展]

浏览次数:  更新时间:2015-09-23 19:18:59
上一篇:基于项目驱动的ASP.NET程序设计课程教学改革和实践
下一篇:基于S3C2440的触摸屏设计
网友评论《(n,k)最小广播图的设计方案分析》
Top