第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）的值域为或者为，()。关键词：结点 发散 时间最短1. 问题重述 设有n个网站，有若干条线路把他们连起来。每一个网站都能接收信息和传播信息，但只有k个（kn）网站能够发布信息。能发布信息的网站称为“源网站”。源网站产生的信息“+”要在最短的时间内传播到其它网站。它的传播方式是这样的：拥有信息“+”的网站每一秒钟“有选择”地向与它相连但未获得该信息的某一个（最多一个）网站发送信息。这里所谓“有选择”是指“使信息传播的总时间最少”。例如：当n=8时，最快的传播过程是传，传，传，所以至少需要3秒钟。对一般情形，至少需要耗费秒时间（表示不小于x的最小整数）。对给定的正整数n和k（kn），由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为正整数；（） 对5kn, 尽你的可能求f(n, k)的值或讨论它的上下界。2. 模型假设与符号系统1、 假设每个源网站每秒内都可以同时接受和发送信息，且信息量不限。2、 假设各个源网站发布的信息是不同的，即每个源网站的信息必须共享，最后的状态是所有网站均收到了所有源网站上的信息。n(n1)表示网站数；k(k1)表示源网站数；f(n, k)表示(n, k)最小广播图的边数；表示不小于x的最小整数；“结点”表示网站，“源结点”表示源网站；“边”表示两结点之间信息的传播线路；“i结点（i=1，2，）”表示该结点有i条边；3. 模型分析该问题相当于给出离散的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越大，函数值递增但不严格递增。4. 模型建立与问题求解问题（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。也可以理解为在 + + 的基础上每增加一个结点需加一条边，所以f(n,2)=f(n-1,1)+1=f(2,2)+n-2=1+n-2=n-1。3、k=4时，源结点的连接有如下两种可能： + 1 + 1 2 2 （1） 3 2 （2）（1）中某个结点的信息可以在2秒内传至其他所有源结点（由图中的标号可知），所以四个源结点获得四处信息均在2秒之后，则在剩下的p-2秒内每个源结点应传播个结点（当然这些结点不包括另外三个源结点，因为它们在前2秒内已经传完），产生-1条边。因此当时，f(n, 4)= 4+4(-1) =（第一个4表示连接源结点所需的边数）。当时，只需在上述广播图中减去相应个数的最外围的1结点即可得到边数且f(n, 4)仍为n。那是不是对所有，f(n, 4)都等于n呢，我们来看第2种情形。（2）由该图可知，对于一个结点的信息来说，传至需一秒，传至另两个结点分别需2秒和3秒，可取这两个源结点看成k=2的情形，那么剩下p-1秒可以向外传播、剩下p-3秒可以向外传播。结点在p-1秒内最多传播个结点，产生-1条边，结点最多传播个结点，产生-1条边。因此，当时，f(n, 4)= 1+(-1)+(-1)=n-1（第一个1表示两个源结点之间的一条边），与n相比根据最少边数的要求得此时f(n, 4)=n-1。当时，只需在上述广播图中减去相应个数的最外围的1结点即可得到边数f(n, 4)仍为n-1。综上所述f(n, 4)= 。4、同样k=3时与k=4作类似分析，源结点的连接有如下两种可能： + + 1 2 2 1 （1） （2）（2）由该图可知，对于一个结点的信息来说，传至需一秒，传至需2秒，可取这两个源结点看成k=2的情形，那么剩下p-1秒可以向外传播、剩下p-2秒可以向外传播。结点在p-1秒内最多传播个结点，产生-1条边，结点最多传播个结点，产生-1条边。因此这样的，当时，f(n, 3)= 1+(-1)+(-1)=n-1（第一个1表示两个源结点之间的一条边）。当时，只需在上述广播图中减去相应个数的最外围的1结点即可得到边数f(n, 3)仍为n-1。又因为f(n,3)k=时，可能只需在上述个结点中任选n-个1结点并对应的添加n-条边，也有可能当n大到某一值时结果变小，即f(n,) f(,)+n-=+ n-=n+,()。2、当(n,k)=(, )、()时，因为结点是2的倍数，所以新的最小广播图在(,)的基础上发散，每个源结点再传播个结点、增加条边，所以f(，)=问题（3）的解答根据问题1的求法我们同样可以得到当k=5时的f(n, 5)时的。有模型分析中的结论二可知：由问题（2）的推论和已知结论有5. 模型分析1、 模型的优点首先该模型的假设对实际问题作了简化，并得出了一些基本结论，为3个问题的求解作好了准备工作。当k=1、2、3、4时根据我们的分析能够得出准确的函数f(n,k)值。k较大时不易求出函数具体值，但我们利用了对问题2的求法，求出了k=时的数值解，另外推出值域的或者为，()。2、模型的缺点在第（3）问中的解答没有完整的理论体系，结果不是很完善、不能令人满意。3、模型的改进因为源信息的传播可看作树的生长，因此还可以用树图来解释边数值。该模型的应用显而易见：在网络特别是互联网迅速发展的今天，网络成为人们娱乐方式的最常用选择，对于网络经营者来说这几个问题是需要考虑的：一定用户时，如何建立通信线路使用户最快收到服务器上的最新消息同时线