最 小 广 播 图 的 设 计

　摘要：

　最小广播图的设计方案是线路联通问题。针对此问题，经过分析，本模型首先建立了几个基础、重要的不等关系，为后面的求解作好了准备。当 k 较小时如1、2 时，可以直观地求出函数 f(n,k)：f（n，1）=n-1,f(n,2)=n-1.当 k=3、4时将源网站的连接方式分类：可以将所有源网站同等研究、可以化为两个源网站的问题研究，然后可以求出分段函数的值，得到 f(n,3)=     p pp pn nn2 2 3 ,2 3 2 , 1 - n22 1，f(n,4)=     p pp pn nn2 2 5 ,2 5 2 , 1 - n33 1。当 k 较大时不易求出函数具体值，但我们利用了模型分析中结论 2，将求 f(n,k)的下界转化为 f（n，5）的下界，在根据在求问题二时得到的结论也可以粗略的求得 f（n，k）的值域为 )) 3 ( 2 2 , 1 (2 1   m nm p或者为 )) 2 ( 2 2 ), 3 ( 2 2 (1 2 1     m mm p m p，( 1 ,   m m p )。

　关键词：

　结点发散时间最短 1. 问题重述 设有 n 个网站，有若干条线路把他们连起来。每一个网站都能接收信息和传播信息，但只有 k 个（k≤n）网站能够发布信息。能发布信息的网站称为“源网站”。源网站产生的信息“+”要在最短的时间内传播到其它网站。它的传播方式是这样的：拥有信息“+”的网站每一秒钟“有选择”地向与它相连但未获得该信息的某一个（最多一个）网站发送信息。这里所谓“有选择”是指“使信息传播的总时间最少”。例如：当 n=8 时，最快的传播过程是１传２，２传４，４传８，所以至少需要 3 秒钟。对一般情形，至少需要耗费 n2log 秒时间（   x 表示不小于 x 的最小整数）。对给定的正整数 n 和 k（k≤n），由 n 个网站（其中 k 个源网站）构成的通讯系统，若每个源网站发布的信息“＋”都能按上述传递方式在 n2log 秒内传播到所有网站，则称该通讯系统为(n,k)广播图。如果每个网站之间都有一条线路，显然它是(n,k)-广播图，但它的造价太高了。线路的条数（以下简称“边数”）最少的称为(n,k)－最小广播图，将它的边数记为 f(n,k)。请设计(n,k)－最小广播图，确定它的边数 f(n,k)：

　（１）

　对 k=1,2,3,4 给出 f(n,k)的数值； （２）

　求 ) 2 , 2 (p pf ，其中 p 为正整数； （３）

　对 5≤k≤n,尽你的可能求 f(n,k)的值或讨论它的上下界。

　2. 模型假设 与 符号系统

　1、假设每个源网站每秒内都可以同时接受和发送信息，且信息量不限。

　2、假设各个源网站发布的信息是不同的，即每个源网站的信息必须共享，最后的状态是所有网站均收到了所有源网站上的信息。

　n(n≥1)表示网站数； k(k≥1)表示源网站数； f(n,k)表示(n,k)－最小广播图的边数；  x 表示不小于 x 的最小整数； “结点”表示网站，“源结点”表示源网站； “边”表示两结点之间信息的传播线路； “i 结点（i=1，2，„）”表示该结点有 i 条边； 3. 模型分析 该问题相当于给出离散的 n 个点，有 k 个点是特殊的，如何用线段将所有点连接起来并且要满足一定的条件。研究这个问题要用到图论的相关知识，虽然有很多人研究过这个问题并给出多种经验性计算公式，但并没有一个统一的答案和准确的结果。我们可以从最简单的 1、2、3、4 个源网站出发，研究其边数的规律，然后逐步深入。

　下面先说明几个简单的结论：

　1、对于任一正整数 n，总存在非负整数 p,使得pn 2 21 - p  ，此时广播图的传播时间为 n2log =p 秒。根据传播时间最短的原则，传播的网站数按 2 的指数增长，即每个结点在 p 秒内应传播p2个结点（这也是传播最多的结点数），产生p2-1条边。

　2、f(n,k)  f(n,k+1)解释：当源网站增加时，图中需要传播的信息增加，而在传播的网站数相等情况下，只有线路增加才能保证时间不变，所以 f(n,k+1)应该变大。

　3、所有的网站最后都应具有所有源网站的信息，所以源网站之间应路线最短、边数最短，使得信息先在源网站内传播，再由源网站将多个信息同时传播给其他非源网站，这样才能节省时间。这相当于源网站集中在内圈、其他网站发散地连接在外围。

　4、f(n-1,k)  f(n,k)解释：由 3 可知，非源网站在外围，所以增加一个网站那就在外围先加一条边即可，因此 k 一定时，n 越大，函数值递增但不严格递增。

　4. 模型建立 与问题求解 问题（1 1 ）的解答

　1、k=1 时，要使传播的时间最少，必须按照“1 传 2，2 传 4，4 传 8”的规则，若有 n 个网站，便需 n2log 秒钟。按上述传播顺序画出广播图(n=8,k=1 时传播顺序如下图，标“＋”的网站为源网站，其它标“t”的网站（t=1,2,3）表示该网站在第 t 秒后获得信息)，可知 f(1,1)=0,f(2,1)=1,f(3,1)=2,„f(n-1,1)=n-2,即网站数多一个时，任选一个网站并加一条边即可，因此 f(n,1)=f(n-1,1)+1=n-1。

　 ３

　２

　１

　＋

　２

　３

　３

　３ 2、k=2 时，相当于 k=1 的那一个源网站已经传播了一秒后广播的传播，所以在边数上 f(n,2)=f(n,1)=n-1。也可以理解为在++的基础上每增加一个结点 需加一条边，所以 f(n,2)=f(n-1,1)+1=„=f(2,2)+n-2=1+n-2=n-1。

　3、k=4 时，源结点的连接有如下两种可能：

　+1①+ ②1 22 （1）④3③2 （2）

　（1）中某个结点的信息可以在 2 秒内传至其他所有源结点（由图中的标号可知），所以四个源结点获得四处信息均在 2 秒之后，则在剩下的 p-2 秒内每个源结点应传播2 - p2 个结点（当然这些结点不包括另外三个源结点，因为它们在前 2 秒内已经传完），产生2 - p2 -1 条边。

　因此当p2 2 4 n2 - p   时，f(n,4)=4+4(2 - p2 -1)= n 2 p  （第一个 4 表示连接源结点所需的边数）。当pn 2  时，只需在上述广播图中减去相应个数的最外围的1 结点即可得到边数且 f(n,4)仍为 n。那是不是对所有pn 2 21 - p  ，f(n,4)都等于n 呢，我们来看第 2 种情形。

　（2）由该图可知，对于一个①结点的信息来说，传至②需一秒，传至另两个结点分别需 2 秒和 3 秒，可取②④这两个源结点看成 k=2 的情形，那么②剩下 p-1秒可以向外传播、④剩下 p-3 秒可以向外传播。②结点在 p-1 秒内最多传播1 - p2 个结点，产生1 - p2 -1 条边，④结点最多传播3 - p2 个结点，产生3 - p2 -1 条边。

　因此3 3 - p 12 5 2 2 n    p p按此传播的 ，当3 3 - p 12 5 2 2 n    p p时，f(n,4)=1+(1 - p2 -1)+(3 - p2 -1)=n-1（第一个 1 表示两个源结点之间的一条边），与n 相比根据最少边数的要求得此时 f(n,4)=n-1。当3 p2 5 2  pn 时，只需在上述广播图中减去相应个数的最外围的 1 结点即可得到边数 f(n,4)仍为 n-1。

　综上所述 f(n,4)=     p pp pn nn2 2 5 ,2 5 2 , 1 - n33 1。

　4、同样 k=3 时与 k=4 作类似分析，源结点的连接有如下两种可能：

　+ +12 21

　①②③ （1）

　（2）

　（2）由该图可知，对于一个①结点的信息来说，传至②需一秒，传至③需 2 秒，可取②③这两个源结点看成 k=2 的情形，那么②剩下 p-1 秒可以向外传播、③剩下 p-2 秒可以向外传播。②结点在 p-1 秒内最多传播1 - p2 个结点，产生1 - p2 -1 条边，③结点最多传播2 - p2 个结点，产生2 - p2 -1 条边。

　因此这样的2 2 - p 12 3 2 2 n    p p，当2 2 - p 12 3 2 2 n    p p时，f(n,3)=1+(1 - p2 -1)+(2 - p2 -1)=n-1（第一个 1 表示两个源结点之间的一条边）。当3 p2 5 2  pn 时，只需在上述广播图中减去相应个数的最外围的 1 结点即可得到边数 f(n,3)仍为 n-1。

　又因为 f(n,3)<=f(n,4)=n，所以对于剩下范围内的 n,只能 f(n,3)=n。

　综上所述 f(n,3)=     p pp pn nn2 2 3 ,2 3 2 , 1 - n22 1。

　问题（2 2 ）的解答

　要求 ) 2 , 2 (p pf ，即求 n=k=p2 时广播图的边数。n=p2 时，最短传播时间为 p秒，在此 p 秒内每个源网站每秒钟均向其相邻网站传递信息（这样才能保证传播量相同时时间最短的要求），即每个结点应有 p 条边，又两个结点共用一条边，所以 ) , 1 , 0 ( , 2 2 / p 2 ) 2 , 2 (1    p p fp p p p。

　推广：1、当 n>k=p2 时，可能只需在上述p2 个结点中任选 n-p2 个 1 结点并对应的添加 n-p2 条边，也有可能当 n 大到某一值时结果变小，即f(n,p2 )  f(p2 ,p2 )+n-p2 =12 pp +n-p2 =n+ ) 2 ( 21pp,(1 p2 2 pn )。

　2、当(n,k)=(p2 ,m2 )、( 1 ,   m m p )时，因为结点是 2 的倍数，所以新的最小广播图在(m2 ,m2 )的基础上发散，每个源结点再传播 ) 1 2 ( 2 2 2 p   m p m m个结点、增加m2 2 p  条边，所以 f(p2 ，m2 )=m p m mf 2 2 ) 2 , 2 (   ) 2 ( 2 2 2 2 21 1      m mm p m p m 问题（3 3 ）的解答

　， ， ，使得 、 、 对m pk n m p k 2 2 2 2 , n1 - m 1 - p      根据问题 1 的求法我们同样可以得到当 k=5 时的 f(n,5)时的。

　有模型分析中的结论二可知：

　1 ) 5 , ( ) 6 , ( ) 1 , ( ) , (        n n f n f k n f k n f 

　由问题（2）的推论和已知结论有 5. 模型分析 1 、 模型的优点 点 首先该模型的假设对实际问题作了简化，并得出了一些基本结论，为 3 个问题的求解作好了准备工作。当 k=1、2、3、4 时根据我们的分析能够得出准确的函数 f(n,k)值。k 较大时不易求出函数具体值，但我们利用了对问题 2 的求法，求出了 k=p2 时的数值解，另外推出 ) 5 )( , ( n k k n f   值域的)) 3 ( 2 2 , 1 (2 1   m nm p或者为 )) 2 ( 2 2 ), 3 ( 2 2 (1 2 1     m mm p m p，( 1 ,   m m p )。

　 2 2 、模型的 缺点

　 在第（3）问中的解答没有完整的理论体系，结果不是很完善、不能令人满意。

　3 3 、 模型的改进 因为源信息的传播可看作树的生长，因此还可以用树图来解释边数值。

　该模型的应用显而易见：在网络特别是互联网迅速发展的今天，网络成为人们娱乐方式的最常用选择，对于网络经营者来说这几个问题是需要考虑的：一定用户时，如何建立通信线路使用户最快收到服务器上的最新消息同时线路越少越好；什么时候线路的利用率最大，即线路每时每刻都在工作；一定数量的用户和服务器时，最多需要几条线路等等。

　当然，该模型是在对实际问题作了一些简化后得到的结果，而在实际网络通信中也许不成立，如两点间的通信应受带宽限制，不可能在一秒内传递任意多的信息。所以模型的改进空间还是很大的。

　6. 参考文献 [1]朱道元等，《数学建模案例精选》，科学出版社。

　7. 附录