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

1、（n,k）最小广播图的设计第13组：杨卓 缪月 蒋悦达摘要： 针对问题一，利用数学推理的方法，根据源结点连接方式不同，得出。在时，根据两种源结点连接方式分类讨论，进而求得 。在时，同样根据两种源结点连接方式分类讨论，求得 。 针对问题二，根据问题一的思路，讨论源结点带有所有信息时的边数，发现每个源结点在每秒钟都必须传递信息给另一个结点才可满足条件，通过运算不难得出。 针对问题三，源结点越多，使源结点带有所有信息的时间越多，传递信息给其他结点的时间越少，所以为能在固定时间内传递信息给所有结点，只能使源结点之间、结点之间连线数增大，所以随增大而增大的关系。在时，求出的下界和上界。关键词： 最小广播

2、图 数学推理 源结点 连接方式 分类讨论一、问题重述 设有n个网站，有若干条线路把他们连起来。每一个网站都能接收信息和传播信息，但只有k个（kn）网站能够发布信息。能发布信息的网站称为“源网站”。源网站产生的信息“+”要在最短的时间内传播到其它网站。它的传播方式是这样的：拥有信息“+”的网站每一秒钟“有选择”地向与它相连但未获得该信息的某一个（最多一个）网站发送信息。这里所谓“有选择”是指“使信息传播的总时间最少”。例如：当n=8时，最快的传播过程是传，传，传，所以至少需要3秒钟。对一般情形，至少需要耗费秒时间（表示不小于x的最小整数）。对给定的正整数n和k（kn），由n个网站（其中k个源网站

3、）构成的通讯系统，若每个源网站发布的信息“”都能按上述传递方式在秒内传播到所有网站，则称该通讯系统为(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为

4、正整数； （3）对5kn, 尽你的可能求f(n, k)的值或讨论它的上下界。 图1二、问题分析 广播是网络信息上的传播过程，在这个过程中一个结点将信息传给所有其他的结点。考虑具有个结点的广播图，在任何一个单位时间内，的任一结点至多向它的一个邻接结点传递信息，因此的广播时间。个结点的最小广播图代表最廉通信网，即用最少可能的连接边数，在最少可能的单位时间内完成广播。因此，寻找的研究，对于设计与实现计算机网际广播具有理论和实际的意义。封闭的如下图所示。针对问题一，需要求出、和的值。根据的不同取值，求出每一个源结点带有所有源结点上信息时得时间以及源结点之间连线条数，再计算出剩下时间内每个源结点传播给信

5、息的结点个数及结点之间连线条数，即可算出最小广播图边数。针对问题二，需要求出的值。考虑使个源结点在时间内传播信息给最多的点，则需要每个源结点在每一秒钟的时间都要传递信息给其他结点。针对问题三，需要在范围内求解的上界和下界。值确定，所以总传播时间也是一定的。源结点越多，每一个源结点带有所有信息所用时间越长，剩余时间传播结点越少，所以为能在一定时间内传播更多的结点，需要结点之间边数增加，所以我们可以考虑随的增大而增大。三、模型假设 （1）假设每个源结点所带信息各不相同。 （2）假设每个结点在一秒内只能将一种信息传递给一个与其相连的结点，但不同种信息传播不受影响，一个结点可以将两种信息分别传递给与它

6、相连的两个结点，也可将两种信息同时传给一个结点。四、符号设定 最小广播图中源结点数量； 最小广播图中结点总数； 最小广播图的连线数（题目中称为边数）； 任意正整数； 不小于的最小整数；五、模型建立与求解5.1问题一求解 在解决以下三个问题之前，我们假设，其中为正整数，则广播图传递信息总时间为。当时，唯一的源结点在第一秒可将信息传给1个结点，从而有了2个带有信息的结点，这两个结点在第二秒可分别将信息传给1个结点，即在第二秒可将信息传递给2个结点，从而有了4个带有信息的结点，以此类推。不难发现，信息传播存在“1传2，2传4，4传8”的指数增长传播规律，并且每传播一个结点就会形成一条边，所以在前秒时

7、间内，传播信息产生的边数为。在最后一秒，由于已经有个结点带有信息，这些结点可以将信息传递给个不带信息的结点，产生个带信息的结点，但结点总数不大于，未带有信息的结点数，所以最后一秒只需从已带有信息的结点中挑出一部分为剩下还未带有信息的结点传播信息，从而求出最后一秒形成条边。综上，可以得出： 当时，首先考虑使两个源结点带有所有两种信息。显然，两个源结点相连，需1秒钟使二者都带有两种信息。剩下的秒内，两个结点分别按照“1传2，2传4，4传8”的传播规律传递信息，这与时情况完全相同。综上，可以得出： 当时，需先算出三个源结点带有所有信息时所用时间和此时源结点之间连线条数，再算出剩余时间内源结点传递信息

8、时所产生的最小边数。根据源结点连接方式，分两类情况进行讨论： 图2 图3 （1）三个源结点排列方式如图2所示，显然每个源结点同时带有三个源结点的信息需要2秒，所以三个源结点有秒的时间向其他结点传递信息，每个源结点最多可以传递信息给个结点，所以在此种情况下。三个源结点在秒时间内形成的最多边数为，在最后一秒时，根据前文结论，需要减去多算的几条边。综上，可以得出，此时。（2）三个源结点另一种排列方式如图3所示，其中有阴影的结点为源结点，无阴影的结点为普通结点。显然，四个结点带有三种源结点信息需要2秒。四个结点在秒内形成最大边数为，在根据第一种情况的方法，减去多算的几条边，可以得到。综上，时取值为：

9、当时，同样按照源结点之间连接方式，分两种情况讨论： 图4 图5 （1）源结点连接方式如图4所示，不难看出，此种情况与时的第二种情况相似，故可以求出。 （2）源结点另一种连接方式如图5所示。假设中间源结点为，带有信息1，周围三个源结点为、和，分别带有信息2、3和4。第1秒，将2、将3、将4传递给，将1传递给，此时带有信息1234，带有信息12，带有信息3，带有信息4。第2秒，将12传递给，将34传递给，此时带有信息1234，带有信息1234，带有信息123，带有信息4。第3秒，将123传递给，将4传递给，此时四个源结点都带有信息1234。显然，有一个源结点可传递个结点，三个源结点可传递个结点，故

10、此时。四个源结点在秒内可形成最大边数为，再减去多算的边数，则此时。综上，时取值： 5.2问题二求解 在问题二中，可求出传播时间，要在固定时间内尽可能传播信息给最多的结点，故每秒钟每个结点都会传递信息给另一个未携带此信息的结点，所以每个结点在时间内对个结点传播信息，故一共有个结点数次。又因为按照这种算法计算的话，每个结点被算了两遍，而每传播一次只产生一条边，所以不难得出：5.3问题三求解5.3.1下界确定根据问题分析，我们已经得出随的增大而增大，即对于且为整数，都有，所以，接下来只要求出的值，下界即可确定。当时，根据源结点连接方式，可分为以下四种情况讨论：图6 （1）五个结点连接方式如图6所示。

11、假设中间源结点为，带有信息1，周围四个结点为、和，带有信息2、3、4和5。第1秒，将2、将3、将4、将5传递给，将1传递给，此时带有信息12345，带有信息12，带有信息3，带有信息4，带有信息5。第2秒，将345传递给，将12传递给，此时与带有信息12345，带有信息123，带有信息4，带有信息5。第3秒，将45传递给，将123传递给，此时都带有信息12345，带有信息1234，带有信息5。第4秒，将5传递给，将1234传递给，此时五个源结点都带有信息12345，由此可以得出，在此种情况下。在秒时间内传递信息产生的最大边数为，再减去多算的边数，所以。图7 （2）源结点第二种连接方式如图7所示

12、。假设从顶端结点按逆时针顺序分别为、，带有信息1、2、3、4、5。第1秒，将2、将5传递给，将1、将3传递给，将4传递给，此时带有信息125，带有信息123，带有信息3，带有信息4，带有信息45。第2秒，将5传递给，将12传递给，将3传递给，将12传递给，将3传递给，将4传递给，将4传递给，将5传递给，此时带有信息12345，带有信息1235，带有信息1234，带有信息345，带有信息1245。第3秒，将4传递给，将3传递给，将5传递给，将12传递给，此时所有源结点都带有信息12345。在这种情况下，。图8（3）第三种连接情况如图8所示，点的名称与所带信息假设与第二种情况相同。第1秒，将2、将

13、3、将5传递给，将1传递给，将4传递给，此时带有信息1235，带有信息12，带有信息34，带有信息4，带有信息5。第2秒，将5传递给，将123传递给，将12传递给，将3传递给，将4传递给，将4传递给，此时带有信息12345，带有信息1235，带有信息1234，带有信息4。第3秒，将4传递给，将传递给，将123传递给，将5传递给，此时五个源结点均带有所有信息。此时，。图9 （4）最后一种连接情况如图9所示，点的名称及所带信息的假设同上，点之间信息的传播与第三种情况相似，共需要3秒，。综上，所以下界为。5.3.2上界确定 假设，显然。由问题二结论可知，个源结点全部带有所有信息形成边数为，则有所以可以得到的上界六、模型推广在实际广播信息传播中，结点是否可以同时传不同信息给相对应的不同结点是不确定的，因此在实际广播图设计中，也需要结合实际情况，考虑一个结点不能同时给两个及以上结点分别发送不同种信息的广播图组成。七、结论本文利用数学推理的方法，根据源结点连接