(n,k)最小广播图设计.docVIP

（n,k）最小广播图的设计 第13组：杨卓 缪月 蒋悦达 摘要： 针对问题一，利用数学推理的方法，根据源结点连接方式不同，得出。在时，根据两种源结点连接方式分类讨论，进而求得 。在时，同样根据两种源结点连接方式分类讨论，求得 。 针对问题二，根据问题一的思路，讨论源结点带有所有信息时的边数，发现每个源结点在每秒钟都必须传递信息给另一个结点才可满足条件，通过运算不难得出。 针对问题三，源结点越多，使源结点带有所有信息的时间越多，传递信息给其他结点的时间越少，所以为能在固定时间内传递信息给所有结点，只能使源结点之间、结点之间连线数增大，所以随增大而增大的关系。在时，求出的下界和上界。 关键词： 最小广播图 数学推理 源结点 连接方式 分类讨论 一、问题重述 设有n个网站，有若干条线路把他们连起来。每一个网站都能接收信息和传播信息，但只有k个（k≤n）网站能够发布信息。能发布信息的网站称为“源网站”。源网站产生的信息“+”要在最短的时间内传播到其它网站。它的传播方式是这样的：拥有信息“+”的网站每一秒钟“有选择”地向与它相连但未获得该信息的某一个（最多一个）网站发送信息。这里所谓“有选择”是指“使信息传播的总时间最少”。例如：当n=8时，最快的传播过程是１传２，２传４，４传８，所以至少需要3秒钟。对一般情形，至少需要耗费秒时间（表示不小于x的最小整数）。对给定的正整数n和k（k≤n），由n个网站（其中k个源网站）构成的通讯系统，若每个源网站发布的信息“＋”都能按上述传递方式在秒内传播到所有网站，则称该通讯系统为(n, k) 广播图。如果每个网站之间都有一条线路，显然它是(n, k)广播图，但它的造价太高了。线路的条数（以下简称“边数”）最少的称为(n, k)－最小广播图，将它的边数记为f(n, k). 　　当?n=8, k=1时，log28=3。在图１中，标“＋”的网站为唯一的源网站，其它标“t”的网站（t=1,2,3）表示该网站在第t秒后获得信息。易知f(8, 1)=7. 　　请设计(n, k)－最小广播图，确定它的边数f(n, k)： （1）对k=1,2,3,4给出f(n, k)的数值； （2）求，其中p为正整数； （3）对5≤k≤n, 尽你的可能求f(n, k)的值或讨论它的上下界。 　　　　　　　　　　３　 　２　　１　　＋　 ２　　 ３　 　　　　　　　　　　　　　　　　 ３　　３ 图1 二、问题分析 广播是网络信息上的传播过程，在这个过程中一个结点将信息传给所有其他的结点。考虑具有个结点的广播图，在任何一个单位时间内，的任一结点至多向它的一个邻接结点传递信息，因此的广播时间。 个结点的最小广播图代表最廉通信网，即用最少可能的连接边数，在最少可能的单位时间内完成广播。因此，寻找的研究，对于设计与实现计算机网际广播具有理论和实际的意义。封闭的如下图所示。 针对问题一，需要求出、、和的值。根据的不同取值，求出每一个源结点带有所有源结点上信息时得时间以及源结点之间连线条数，再计算出剩下时间内每个源结点传播给信息的结点个数及结点之间连线条数，即可算出最小广播图边数。 针对问题二，需要求出的值。考虑使个源结点在时间内传播信息给最多的点，则需要每个源结点在每一秒钟的时间都要传递信息给其他结点。 针对问题三，需要在范围内求解的上界和下界。值确定，所以总传播时间也是一定的。源结点越多，每一个源结点带有所有信息所用时间越长，剩余时间传播结点越少，所以为能在一定时间内传播更多的结点，需要结点之间边数增加，所以我们可以考虑随的增大而增大。 三、模型假设 （1）假设每个源结点所带信息各不相同。 （2）假设每个结点在一秒内只能将一种信息传递给一个与其相连的结点，但不同种信息传播不受影响，一个结点可以将两种信息分别传递给与它相连的两个结点，也可将两种信息同时传给一个结点。 四、符号设定 — 最小广播图中源结点数量； — 最小广播图中结点总数； — 最小广播图的连线数（题目中称为边数）； — 任意正整数； — 不小于的最小整数； 五、模型建立与求解 5.1问题一求解 在解决以下三个问题之前，我们假设，其中为正整数，则广播图传递信息总时间为。 当时，唯一的源结点在第一秒可将信息传给1个结点，从而有了2个带有信息的结点，这两个结点在第二秒可分别将信息传给1个结点，即在第二秒可将信息传递给2个结点，从而有了4个带有信息的结点，以此类推。不难发现，信息