(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

综上所述，

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.

［责任编辑：刘展］