文档介绍：第卷第期经济数学
年月
模式下广播网络的最佳源点集
伍勇安谢政
国防科技大学理学院,湖南长沙,
摘要所谓广播,就是将网络中一个成员所拥有的消息,沿着网络成员之间的通信线路传递给其它所有成
员的过程称最初拥有消息的成员为源点从不同的源点广播一条消息所需的时间一般是不同的关于
模式和模式下树上的最佳源点与最佳源点对问题,已有相关文章进行过讨本文提出子比
。广播模式更一般的广播模式的概念,并从该模式出发,在树形网络中设计了寻找最佳源点和最佳
源点集的算法
关键词广播网络,厂广播,最佳源点集,算法,图
网络模式
广播是网络通信中基本的和主要的工作之一我们将通信网络抽象为图,图中顶点表示消
息处理机,可以是源点也可以是接收点边表示消息处理机之间的通信线路所谓广播,是指在
简单连通图,中,。仁,。中的所有顶点都知道某条消息,而。中的顶
点都不知道这条消息,用尽可能少的时间使得这些顶点得到该消息的过程由于从不同的源点
出发广播一条消息所需的时间一般是不同的,因此考虑在图中选择一个顶点作为源点,使广播
时间最小,这样的源点称为最佳源点对于可以选择镇镇】一个源点的情形,类
似的可以定义最佳源点集,以后在本文中出现的,若无特别说明,均是指蕊簇一

定义在图,中,设,称满足下述三个条件的广播为广播
每次消息传送只需一个单位时间
每次消息传递只能在两个互邻的顶点之间进行
任,顶点在一个单位时间内至多能进行次消息传送
从上面的定义可以看出,模式的广播和模式的广播分别是了性和了性
二时两种特殊的广播,而。广播也是三。时的特例以后的广播若不特别指明,都指的是
广播
下面给出广播网络中的一些常用概念和符号
定义在图,中,设。仁为源点集,以最小时间完成广播的一个过程称
为的一个广播方案
定义在图,中,任,。仁定义,或。,是对于图
以或。为源点或源点集完成广播所需要的时间单位定义,任
收稿日期一一
一一经济数学第卷
是图的广播时间或广播复杂度,定义二,任
为的图最小广播时间
根据定义,最佳源点也就是满足临。,,任的顶点公。而最佳
源点集就是满足订。,,任,的顶点集护。
本文的目的,就是要在树形网络上广播模式下,设计寻找最佳源点艺。和最佳源点集
。的算法,并将该算法推广到连通网络中
树形网络上选取最佳源点补。的删点法
设树为,,除非特别指明,本文中所讨论的树都至少是阶的要寻找
最佳源点艺。,可从最佳源点的定义出发,在艺。所对应的的一个广播方案中,从最后一次消息
传送开始逆推分析到第一次消息传送,进而得到云。的有关性质,然后利用这个性质来设计寻
找最佳源点的算法
引理设,是树,。,,⋯,仇一,。是源点如果中所有悬挂点都得
到消息,则完成了上的广播
证明假设中所有悬挂点都得到消息,但日任,没有得到消息
因为,不是的悬挂点,所以必存在一个悬挂点,是,关于。的后代又由于是树,
因此。,之间有惟一的链,从而。,,,链是。,,之间的惟一链,于是,一定要经过。,
、,,链得到消息,所以要先于,得到消息,这与假设矛盾· 口
根据引理,艺。所对应的的一个广播方案中是最后一次消息传送的对象必是的某
些悬挂点,