资源描述：
《广播网络的最佳源点集.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、年月应用数学与计算数学学报第卷第期,广播网络的最佳源点集谢政刘树立国防科技大学数学系,长沙。。摘要广播是研究通信网络的某个成员的消息如何尽快地传递给所有其它成员的消息传递问题有两类常见的通信模式,一类是模式,即在一个单位时间内一个顶点能够和它的所有邻点通信另一类是模式,即在一个单位时间以内,一个顶点最多只能和它的一个邻点通信通信网络通常用图来描述最初贮存消息的网络成员称为撅点本文提出了最佳源点集的新概念,解决了在劝亡初通信模式下如何选择两个或更多的网络成员作为源点,以使网络的广播时间最短的向题,并且进一步讨论了它与多选址间题的联系及
2、推广应用关健词广播,,最佳源点集,图网络葬法网络模型我们假设所研究的图,冈认是连通的且在广播过程中满足以下三个条件一个顶点得知消息后,只能将消息传递给它的邻点每次消息传递都能在一个时间单位内完成一个顶点得知消息后,这个顶点的所有邻点均可以在下一个时间单位后得知这个消息考虑在网络中选择,,网络的一个顶点作为源点使广播时间最短这样的源点称为最佳源点类似地若可以选择两个顶点作为源点,且选取某两个顶点为源点时,网络广,则称这两个顶点为最佳源点对对,播时间最短于可以选择七个源点的情形类似地可,称之为最佳源点集首先讨论如何在以定义为最佳源点集为
3、方便起见一个广播,网络中求解最佳源点对的问题这需要用到算法算法算法是用,于求网络中所有顶点对之间的最短路长的算法是于年提出来的关于不含负,我们将其稍加改回路的有向网络的算法可以参考【,进,即可得到关二,,二于不含负圈的无向网络的算法对于叫其中为与本文年月日收到应用数学与计算数学学报卷,叭勺,对应的权集可看作中各边的边长我们规定对一切令尹十二,艺兴,切一,云,,。表示由顶点集合‘勺,。,⋯,二,用“导出的的子网络特别地￡,,‘,勺导出的的子网络,,。中最短‘,表示由顶点集把“链的长。记为尸则显然有如下结论成立气玄,’叨云,,,,,‘。
4、,,厂艺二因此试罗为中最短链的长其中下’,,一,,,“”一、因为‘‘’‘是‘‘,爪的子网络故尹,三尹,二,二“,二,。一,。,了,二。,,一,。生,二证少一’。恤“所以盆一刀乙刁一”己。一‘,沈二二,艺,二,,⋯,。,定理设无向网络认不含有负圈则对一切上面定义。的罗满足,。一‘。一‘。一‘,。,‘。“,’二’,‘二。了尹少沈此定理的证明略,可参考【中定理的证明由定理可以保证下述算法的正确性在无向图中求任意顶点对之间最短链长的’算法的具体步骤如下。‘,,,,,,二‘令珍⋯,几,,令。,。一‘’。一‘’。一‘’对一切三三三三矛尹二思。,
5、结束二。如果。否则置二转。”容易估计出此算法的复杂性为,二,,,⋯,。,‘,叭在网络,中设令力表示在图中从顶点,‘,,到顶点巧的最短链的长矩阵的第夕个元素是武力则可以应用算法计算”“,。矩阵‘罗,如模式广播网络的最佳源点对。我们考虑在阶广播网络从中给边集中的每条边都赋以权值设二卜,。,叭,勺￡,‘,,吻⋯任袱并力若以巧为广播网络从的源点对则中任意一点最早得到消息所经过的时间应为·‘,,,‘,勺为源点对,因此以在网络中广播一条消息所需的时间为,,,。界,二亡亡⋯亡。由以上分析可得到如下求解阶广播网络’日中的最佳源点对的算法如期谢政等广
6、播网络的最佳源点集刀,。应用二算法求出距离矩阵‘‘了罗葱,置了对。,亡‘,,,一切三令“·,亡,,⋯,。令毛。,即若置转即‘,,七若。一置‘￡再置‘转·若二,￡。一,转取·。二买几叼使成立的叭两即·为最小广播时间算法结束为网络的最佳源点对命题上述求解。阶广播网络的最佳源点对的算法是正确的,且该算法的复杂性为沪证明该算法的正确性由前面的分析可知下面分析算法的复杂性的算￡,,。,法复杂性为护对每对不同的了和的复杂性为而在个不同·个,故一‘‘落,,值中的不同的组合的个数为午一。,,的总的复杂性为。而最后一步是在不超过誓个数值中取一个最小值
7、所以印二“的复杂性为矿从而该算法的复杂性为血模式广播网络的最佳源点集我们得到的主要结果是在模式广播网络中求解最佳源点集的算法对。,,于阶广播网络认给边集中的每条边都斌以权值得到一个赋权网络,,,,⋯,。。,,叭认司不妨设令力表示在图中从顶点到顶点勺,有如下求解广播网络中的最佳饭点集的最短链的长三的算法如下应用算法求出距离矩阵武‘,力令落·,,,葱‘‘‘⋯‘,一令对一切三。,饥令忿,,‘,。,‘,⋯,。,‘,‘⋯‘,令双二,,即若‘。‘,‘,置转￡一一,‘,一‘一,‘‘一,若置转‘。一,‘。,,⋯,一,若置‘葱‘转‘,,若一置葱葱转乞
8、九一,若转应用数学与计算数学学报卷··‘、‘,。二即”取少竺协动二几‘‘算法结束奥巧,,⋯,巧,由的结果得到所要求的最佳源点集场命题算法是正确的,且其算法复杂性为砂证明对于任意选定的个位置,在即中求出了每一个顶点与最靠近它的位置的距离
