蒋俊豪 王 儒 何佳龙
（河海大学，江苏 南京 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.
［责任编辑：刘展］