最小广播图的设计  

作　　者：朱文旺 张典典 曹明纬 周文韬[1] 曹如意[2] 

机构地区：[1]河海大学土木与交通学院,江苏南京210098 [2]河海大学港口海岸与近海工程学院,江苏南京210098

出　　处：《科技视界》2014年第15期175-175,304,共2页Science & Technology Vision

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

关 键 词：结点 发散 时间最短 

分 类 号：O157.5[理学—数学]