资源描述：
《最小广播图研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、年月计算机学报第期最小广播图研究肖金声王晓中山大学计算机科学系。考人二,夕。,,夕,,场·,,哪,摘要广播是网络上信忽的传播过程在这个过程中一个结点将信息传目前已有结果的基础上,确给所有其它结点本文在定了的位给出了,,一些新此外还介绍了一种得到的新分割法并随之列出一个时上界的。估计砚恤当一、‘二考,,虑代表通信网的无向连通图其中是网中结点集是网中结点对之间的通信线路集所谓广播就是网中某源结点将其信息传递给网中所有其它结点的过程。,讨论广播问题时我们接受如下约束每个结点只能向其相邻结点传递信息结点对之间传递一次信息需要一个单位时间,。每个结点在任何单位时间里至多只能参予一对结
2、点之间的信息传递广播问题中使用如下定义“,““定义图中某结点的广播时间是完成以为源结点的广播所需最少单位时间数,。,“,,“。显然在结点通信网中对于任一结点而言都有》「们因为在一个单本文年月日收到计算机学报,年,“位时间里得到点信息的结点数至多能增加一倍乙图,‘‘,定义‘的广播时间是指中结点广播时间的最大值即‘‘。,定义设图有个结点若川且对的任何真生成子图’均,,,。,,有’「则称图为个结点的极小广播图记为,,,可以用最少单位时间完成广播但不一定具有最少可能的边数一般来说个结点的极小广播图并不唯一定义广播函数的之值定义为的中的最小边数,,定义个结点的最小广播图是指有条边的极
3、小广播图记为习,,具有最少可能的连接边数并能在最少可能的单位时间内完成广播因此,代表最廉通信网一般来说也不唯一。,,对于任意自然数找出具有实际意义近几年来发表了若干研究广播问,题的文章文献和研究了构造边数较少的的方法同时也给出了的。,,值的上界文献和给出了和时的刀的值但其中用以求取。,心值的方法不适用于任意文献还给出了‘的所有以及。的当时已知的所有的,,,,不幸的是文献指出的识别间题是完全的同时猜测为任意确定刀幻值的问题也是尸完全的,“”石的值的问题就被这样一来逼近最小广播图和采用特殊方法求取某些提出来了,,,在本文中我们确定了的值还给出了一些新它们同以前所知的,,那些不同
4、构最后我们还要介绍一种得到的新分割法并随之给出一个估计的上。界的公式、二的值我们先证明下述引理,笋‘,。,引理若自然数而是所有中结点的最小度数则有,一,《一。,,证对题设的自然数必有相应的自然数使得一‘称,刃一《‘浮,假定是含有度结点的的我们分两种情形来证明引理的结论】,,,‘若假定是中的度结点则应当形如·,迄〕期肖金声等最小广播图研究,,一个结点及,一条,‘显然’有边这时由中结点原来的广播方案容易得出“中每个结点至多使用个单位时间的广播方案于是,一。,一成一,,,‘若假定结点是度结点则应当形如,、,,,,,‘,‘,,,其中⋯是的个邻结点这时我们先删去及其所有关联边然后如,
5、,,,,,‘,,,、,,,,,,‘果⋯中某两个结点间原来无边就加上一条边以形成⋯之间。,,一个的完全子图我们把这样得到的图记为’显然’中有结点和至多。一一十一条边。,现在我们要由中结点的广播方案给出’中任一结点都至多使用个单位时间的广播方案,‘,,,,,不失一般性我们假定在中同一结点的广播方案中在时刻向传递信息,,,‘。,,,。在时刻十⋯“分别向它的邻结点约的⋯约传递信息这意味约,,约,,约,‘,‘,‘二,‘着⋯分别在时刻十之后需要信息‘,,,,,,,,,,,,,,,,在的对应广播方案中我们让⋯分别在时刻⋯约,约,,,约,,‘一向⋯传递信息而其余的信息传递同中的对应方案一样
6、在同一,时刻进行用这种方法我们就得到了’中任一结点至多使用互个单位时间的广播方,案因此,一,成一引理得证,,,推论在引理的同样假设下若一则有,一定理证图中的无向图是一个有个结点和条边的极小广播图为了验证这一,,点可以容易地为每个结点给出在五个单位时间内完成的广播方案作为例子这里仅给,、,,出以为源结点的广播方案如图所示其中边上的数字表示单位时间的序数箭头计算机学报年方向为信息传递方向。,由此可见,,另一方面可以肯定所有中结点最小度数否则,》,,导出矛盾故由前述推论知但文献【中证明因此一。定理得证,用同样的方法可以大为简化地证明文献中所给出的下面是迄今所知的各的值一止一几一兰
7、一一卜二二止‘兰三止上二二二二里二生兰二生竺生竺·‘,’’’’几互斗互构、三新,,一一,,从前面引理的证明容易看出若且有度或度半平尔必李》佃图迄今所知的所有期肖金声等最小广播图研究,,,结点我们只要简单地删去该结点及其关联边并且在删去度结点的情况下加一条边,,连接其两个相邻结点就可以构造出一对于这样构造的一其广,,,播方案很容易由原来的广播方案导出因此在条件符合时这是构造新。。一的简便方法,,,斗,,,,考虑图的我们可以分别删去结点或,以及两条关联边并且用一条边连接被删结点的两个邻结点所得的图都是,虽然用这种方法生
