第6组-最小广播图的设计-.doc

最小广播图的设计 摘要： 最小广播图的设计方案是线路联通问题。针对此问题，经过分析，本模型首先建立了几个基础、重要的不等关系，为后面的求解作好了准备。当k较小时如1、2时，可以直观地求出函数f(n,k)：f（n，1）=n-1,f(n,2)=n-1.当k=3、4时将源网站的连接方式分类：可以将所有源网站同等研究、可以化为两个源网站的问题研究，然后可以求出分段函数的值，得到f(n, 3)= ，f(n, 4)=。当k较大时不易求出函数具体值，但我们利用了模型分析中结论2，将求f(n,k)的下界转化为f（n，5）的下界，在根据在求问题二时得到的结论也可以粗略的求得f（n，k）的值域为或者为，()。 关键词： 结点 发散 时间最短 问题重述 设有n个网站，有若干条线路把他们连起来。每一个网站都能接收信息和传播信息，但只有k个（k≤n）网站能够发布信息。能发布信息的网站称为“源网站”。源网站产生的信息“+”要在最短的时间内传播到其它网站。它的传播方式是这样的：拥有信息“+”的网站每一秒钟“有选择”地向与它相连但未获得该信息的某一个（最多一个）网站发送信息。这里所谓“有选择”是指“使信息传播的总时间最少”。例如：当n=8时，最快的传播过程是１传２，２传４，４传８，所以至少需要3秒钟。对一般情形，至少需要耗费秒时间（表示不小于x的最小整数）。对给定的正整数n和k（k≤n），由n个网站（其中k个源网站）构成的通讯系统，若每个源网站发布的信息“＋”都能按上述传递方式在秒内传播到所有网站，则称该通讯系统为(n, k) 广播图。如果每个网站之间都有一条线路，显然它是(n, k)-广播图，但它的造价太高了。线路的条数（以下简称“边数”）最少的称为(n, k)－最小广播图，将它的边数记为f(n, k)。请设计(n, k)－最小广播图，确定它的边数f(n, k)： 对k=1,2,3,4给出f(n, k)的数值； 求，其中p为正整数； 对5≤k≤n, 尽你的可能求f(n, k)的值或讨论它的上下界。 模型假设与符号系统 假设每个源网站每秒内都可以同时接受和发送信息，且信息量不限。 假设各个源网站发布的信息是不同的，即每个源网站的信息必须共享，最后的状态是所有网站均收到了所有源网站上的信息。 n(n≥1)表示网站数； k(k≥1)表示源网站数； f(n, k)表示(n, k)－最小广播图的边数； 表示不小于x的最小整数； “结点”表示网站，“源结点”表示源网站； “边”表示两结点之间信息的传播线路； “i结点（i=1，2，…）”表示该结点有i条边； 模型分析 该问题相当于给出离散的n个点，有k个点是特殊的，如何用线段将所有点连接起来并且要满足一定的条件。研究这个问题要用到图论的相关知识，虽然有很多人研究过这个问题并给出多种经验性计算公式，但并没有一个统一的答案和准确的结果。我们可以从最简单的1、2、3、4个源网站出发，研究其边数的规律，然后逐步深入。 下面先说明几个简单的结论： 1、对于任一正整数n，总存在非负整数p,使得，此时广播图的传播时间为=p秒。根据传播时间最短的原则，传播的网站数按2的指数增长，即每个结点在p秒内应传播个结点（这也是传播最多的结点数），产生-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越大，函数值递增但不严格递增。 模型建立与问题求解 问题（1）的解答 1、k=1时，要使传播的时间最少，必须按照“1传2，2传4，4传8”的规则，若有n个网站，便需秒钟。按上述传播顺序画出广播图(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。