n,k最小广播图论文

(n, k) 最小广播图的设计摘要本题是一个图论问题，我们利用将源网站集中的思想对问题进行求解。 对于第一问，由于对任意整数n ，存在整数p ，使得2p -1

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

摘要

本题是一个图论问题，我们利用将源网站集中的思想对问题进行求解。 对于第一问，由于对任意整数n ，存在整数p ，使得2p -1

p -1p -3⎧⎪n -1, 2

对于第二问，源网站数及为需要传播信息的网站数，且n=2p ，要在p 秒内将每个源网站每秒钟均向其相邻网站传递信息，只能任意源网站都相邻，得到了f (2p , 2p ) =p *n ÷2=p ⋅2p -1。

对于第三问，当k 较大时不易求出函数具体值，所以我们考虑其上下界，下界为n-1是容易求出的，求上界时，我们利用第二问的结论，得到了上界为2p 2m -1*(m -2) ，其中2m -1

关键词：最小广播图 源网站连接 时间最短

一、 问题重述

设有n 个网站，有若干条线路把他们连起来。每一个网站都能接收信息和传播信息，但只有k 个（k ≤n ）网站能够发布信息。能发布信息的网站称为“源网站”。源网站产生的信息“ ”要在最短的时间内传播到其它网站。它的传播方式是这样的：拥有信息“ ”的网站每一秒钟“有选择”地向与它相连但未获得该信息的某一个（最多一个）网站发送信息。这里所谓“有选择”是指“使信息传播的总时间最少”。例如：当n=8时，最快的传播过程是１传２，２传４，４传８，所以至少需要3秒钟。对一般情形，至少需要耗费⎡log 2n ⎤秒时间（⎡x ⎤表示不小于x 的最小整数）。对给定的正整数n 和k （k ≤n ），由n 个网站（其中k 个源网站）构成的通讯系统，若每个源网站发布的信息“＋”都能按上述传递方式在⎡log 2n ⎤秒内传播到所有网站，则称该通讯系统为(n, k) 广播图。如果每个网站之间都有一条线路，显然它是(n, k)-广播图，但它的造价太高了。线路的条数（以下简称“边数”）最少的称为(n, k) －最小广播图，将它的边数记为f(n, k).

请设计(n, k)－最小广播图，确定它的边数f(n, k)：

(1)对k=1,2,3,4给出f(n, k)的数值；

(2)求f (2p , 2p ) ，其中p 为正整数；

(3)对5≤k ≤n, 尽你的可能求f(n, k)的值或讨论它的上下界。

二、 问题分析

（n,k ）最小广播图问题是一个图论问题，当k 较大时，我们并不能给出其边数的准确答案，故我们从k=1，2，3... 慢慢着手，先画出n=5，6，7，8，9时的最小广播图，从中发现规律，再将其拓展为一般问题，找出网站数与边数之间的普遍关系。对于k=1，2时比较好分析，可以由（n,k ）广播图的定义及其传播方式得出结果，但当k=3，4... 时，我们需要考虑所有源网站之间的位置关系，她们对传播时间和广播图的边数有很大的关系，所以我们打算建立模型从这方面入手。

三、 模型假设

1. 假设各个源网站发布的信息是不同的，即每个源网站的信息都需要传播给其他网站

2. 当一个网站接收到多种信息时，它可以同时向其他网站传播它所拥有的任一种信息一次，不同信息的传播不受影响

3.k 个源网站越集中，传播时间越短，边数越少

四、 符号系统

n:总网站数

k ：源网站数

f(n, k)：(n, k)－最小广播图的边数

⎡x ⎤：不小于x 的最小整数

p ：广播图的传播时间，则⎡log 2n ⎤=p，2p -1

五、 模型建立

5.1关于问题一：

（1） k=1时(如图1），“源网站”A 将信息传给网站B ，此时增加一条边，之后，A,B 再将信息传给另两个网站，边数再增加两条，即信息每传递一次，拥有信息的点就多一倍，边数的增加数就等于拥有信息的网站数，当最后一秒传递信息时，只需部分信息源传递信息给还未接受到信息的网站，增加的边数即为剩余的未接收到信息的网站数，故f(n,1)=1 21 22 23 ... 2[log 2n ]-2 （n-2[log 2n ]-1）=n-1；

图1 k=1时的广播图

（2） k=2时（如图2），可在k=1的结论基础上，将第二个“源网站”放在B 处，此时当“源网站”B 第一秒将信息传递给A 时，A,B 都拥有信息，第二秒A ，B 再传递信息时就与k=1时的情况相同了，故f(n,2)=f(n,1)=n-1；

图2 k=2时的广播图

（3） k=3时，源网站的连接有以下两种可能：

1 2 3

（1）

B 2 （2）

要使边数最少，那么我们先用最短的时间在源网站之间传播，使所有源网站都拥有所有信息，再由源网站将所有信息传播给其他网站即可。

对于第（1）种情况：我们可以这样设计（如图3）：第1秒将B 网站的信息2，C 网站的信息3传给A 网站，A 网站的信息1传给B 网站，此时，A 网站含有信息123，B 网站含有信息12，C 网站含有信息3，第2秒将B 网站的信息12传给C 网站，C 网站信息3传给B 网站，此时A,B,C 网站均拥有信息123，且每个网站都剩下p-2秒的时间将信息传播给其他网站，而每个网站1秒只能将同一信息传给一个网站，每增加一个网站就增加一条边，故由A(B,C与A 相同）网站传播出的网站数为1 21 22 ... 2p -3=2p -2-1, 所以这种情况下，n=3 3*（2p -2-1）=3*2p -2，f （n,3）=2 n-3=n-1;

1 2 3 12 123 3 123 123 123 图3 k=3时情况（1）的广播图 当n ≤3*2p -2时，只需在上种情况的基础上在最外围减去多余的网站，每少

一个网站就少一条边，所以f(n,3)=n-1；

对于第（2）种情况：我们可以这样设计（如图4）：第1秒将A 网站的信息1，C 网站的信息3传给B 网站，B 网站的信息2传给A 网站，此时，A 网站含有信息12，B 网站含有信息123，C 网站含有信息3，第2秒将B 网站的信息3传给A 网站，信息12传给C 网站，而A 网站可以直接将所有信息传播给另一个网站D, 此时A,B,C,D 网站均拥有信息123，且每个网站都剩下p-2秒的时间将信息传播给其他网站，同理知，由A(B,C，D 与A 相同）网站传播出的网站数为2p -2-1, 所以这种情况下，n=4 4*（2p -2-1）=4*2p -2=2p ，f （n,3）=4 n-4=n;

A 1 A 123 A 123 D 123

B 2

C 3 B 12 C 3 B 123 C 123

图4 k=3时情况（2）的广播图

当3*2p -2

p -1p -2⎧⎪n -1, 2

（4）k=4时，源网站的连接有以下两种可能：

A 1 B 2

D 4 C 3

(1) (2)

对于第（1）种情况：我们可以这样设计（如图5）：第1秒将B 网站的信息2，C 网站的信息3,D 网站的信息4传给A 网站，A 网站的信息1传给B 网站，此时，A 网站含有信息1234，B 网站含有信息12，C 网站含有信息3，D 网站含有信息4，第2秒将A 网站的信息12传给C 网站，信息34传给B 网站, 第3秒将A 网站的信息4传给C 网站，信息123传给D 网站，而B 网站可以直接将所有信息

传播给另一个网站E, 此时A,B,C,D,E 网站均拥有信息1234，且每个网站都剩下p-3秒的时间将信息传播给其他网站，而每个网站1秒只能将同一信息传给一个网站，每增加一个网站就增加一条边，故由A(B,C,D,E与A 相同）网站传播出的网站数为1 21 22 ... 2p -4=2P -3-1, 所以这种情况下，n=5 5*（2p -3-1）=5*2p -3，f （n,4）=4 n-5=n-1;

C 3 A 1 D 4 C 3 A 1234 D 4

B 2

B 12

B 1234 B 1234 E 1234

图5 k=4时情况（1）的广播图

对于第（2）种情况：我们可以这样设计（如图6）：第1秒将A 网站的信息1传给D 网站，D 网站的信息4传给A 网站，B 网站的信息2传给C 网站，C 网站的信息3传给B 网站，此时，A 网站含有信息14，B 网站含有信息23，C 网站含有信息23，D 网站含有信息14，第2秒将A 网站的信息14传给B 网站，B 网站的信息23传给A 网站，将D 网站的信息14传给C 网站，C 网站的23传给D 网站，此时A,B,C,D, 网站均拥有信息1234，同理可知：2P -2-1, 所以这种情况下，n=4 4*（2p -2-1）=2p ，f （n,4）=4 n-4=n;

A1 B2 A 14 B 23 A 1234 B1234

D4 C3 D 14 C 23 D1234 C1234

图6 k=4时情况（2）的广播图

p -1p -3⎧⎪n -1, 2

5.2关于问题二：

要求f (2p , 2p ) ，即求n=k=2p 时广播图的边数。n =2p 时，最短传播时间为p 秒，在此p 秒内每个源网站每秒钟均向其相邻网站传递信息（这样才能保证传播量相同时时间最短的要求），即每个结点应有p 条边，又两个结点共用一条边，所以f (2p , 2p ) =2p ⋅p /2=p 2p -1, (p =0, 1, ) 。

5.3关于问题三：

根据问题一的求法我们同样可以得到当k=5时的f(n, 5) 【详细过程见附录】

⎧n -1, 2p -1

p -3p ⎪n 2, 7*2

2m -1

下界的确定：当源网站数目增加时，需要传播的信息量增加，而在传播的总网站数相等情况下，只有线路增加才能保证时间不变，所以f(n, k) ≤f(n,k 1)。所以f (n , k ) ≥f (n , k -1) ≥ ≥f (n , 6) ≥f (n , 5) =n -1。

上界的确定：所有的网站最后都应具有所有源网站的信息，所以源网站之间应路线最短、边数最短，使得信息先在源网站内传播，再由源网站将多个信息同时传播给其他非源网站，这样才能节省时间。这相当于源网站集中在内圈、其他网站发散地连接在外围。非源网站在外围，所以增加一个网站那就在外围先加一条边即可，因此k 一定时，n 越大，函数值递增但不严格递增。所以能够推出f (n , k ) ≤f (n , 2m ) ≤f (2p , 2m ) ，对于f (2p , 2m ) ，共有2m 个源信息，在m 秒内，能够有2m 个网站具有所有源网站的信息，剩下的网站只需在2p 个网站中任选2p -2m 个结点，对应的增加2p -2m 条边，

f (2p , 2m ) =f (2m , 2m ) 2p -2m =m *2m -1 2p -2m =2p 2m -1*(m -2) ，所以

f (n , k ) ≤2p 2m -1*(m -2)

五．模型分析

1、 模型的优点

首先该模型的假设对实际问题作了简化，并得出3个基本的结论 ，为问题的求解作好了准备工作。当k=1、2、3、4时根据我们的分析能够得出准确的函数f(n,k)值。同时在附录里得出了k=5的情况，k 较大时不易求出函数具体值，但是我们根据“当源网站数目增加时，需要传播的信息量增加，而在传播的总网站数相等情况下，只有线路增加才能保证时间不变”以及“信息先在源网站内传播，再由源网站将多个信息同时传播给其他非源网站，这样才能节省时间”推出了上下界的关系。

2、模型的缺点

在第（3）问中的解答没有完整的理论体系，只是根据实际情况进行假设，而没有具体的理论支撑，没有考虑其他的情况。

3、模型的改进

因为源信息的传播可看作树的生长，因此还可以用树图来解释边数值。

六、 模型推广

在网络特别是互联网迅速发展的今天，网络成为人们娱乐方式的最常用选择，对于网络经营者来说这几个问题是需要考虑的：一定用户时，如何建立通信线路使用户最快收到服务器上的最新消息同时线路越少越好；什么时候线路的利用率最大，即线路每时每刻都在工作；一定数量的用户和服务器时，最多需要几条线路等等。

当然，该模型是在对实际问题作了一些简化后得到的结果，而在实际网络通信中也许不成立，如两点间的通信应受带宽限制，不可能在一秒内传递任意多的信息。所以模型的改进空间还是很大的。

七、 参考文献

[1]赵静，数学建模与数学实验[M]，高等教育出版社，2008

[2]谭永基等，数学模型，上海复旦大学出版社，1996

八、 附录

k=5时，源网站的连接有以下多种可能：

情况1：我们可以这样设计（如图7）：第1秒将B 网站的信息2，C 网站的信息3,D 网站的信息4，E 网站的信息5传给A 网站,A 网站的信息1传给B 网站，此时，A 网站含有信息12345，B 网站含有信息12，C 网站含有信息3，D 网站含有信息4，E 网站含有信息5，第2秒将A 网站的信息12传给C 网站，信息345传给B 网站, 第3秒将A 网站的信息45传给C 网站，信息123传给D 网站，而B 网站可以直接将所有信息传播给另一个网站F, 第4秒将A 网站的信息1234传给E 网站，信息5传给D 网站，而B ，C,F 网站可以直接将所有信息传播给另一个网站G ,H,I,, 此时A,B,C,D,E,F,G ,H,I 网站均拥有信息12345，且每个网站都剩下p-4秒的时间将信息传播给其他网站，而每个网站1秒只能将同一信息传给一个网站，每增加一个网站就增加一条边，故由A(B,C,D,E,F,G,H,I 与A 相同）网站传播出的网站数为2P -4-1, 所以这种情况下，n=9 9*（2p -4-1）=9*2p -4，f （n,5）=8 n-9=n-1;

D4 D4 D4

D1234 H12345 D12345

图7 k=5时情况1的广播图

情况2：我们可以这样设计（如图8）：第1秒将B 网站的信息2，E 网站的信息5传给A 网站,A 网站的信息1，C 网站的信息3传给B 网站,D 网站的信息4传给E 网站，此时，A 网站含有信息125，B 网站含有信息123，C 网站含有信息3，D 网站含有信息4，E 网站含有信息45；第2秒将A 网站的信息5传给B 网站，信息4传给E 网站，B 网站的信息3传给A 网站，信息12传给C 网站，C

网站的信息3传给D 网站，D 网站的信息4传给E 网站，E 网站的信息5传给D 网站；第3秒将B 网站的信息5传给C 网站，C 网站的信息4传给B 网站，D 网站的信息3传给E 网站，E 网站的信息12传给D 网站，而A 网站可以直接将所有信息传播给另一个网站F, 此时A,B,C,D,E,F 网站均拥有信息12345，且每个网站都剩下p-3秒的时间将信息传播给其他网站，故由A(B,C,D,E,F与A 相同）网站传播出的网站数为2P -3-1, 所以这种情况下，n=6 6*（2p -3-1）=6*2p -3，（f n,5）=6 n-6=n;

图8 k=5时情况2的广播图

情况3：我们可以这样设计（如图9）：第1秒将B 网站的信息2，C 网站的信息3,E 网站的信息5传给A 网站,A 网站的信息1传给B 网站,D 网站的信息4传给C 网站，此时，A 网站含有信息1235，B 网站含有信息12，C 网站含有信息34，D 网站含有信息4，E 网站含有信息5；第2秒将A 网站的信息5传给B 网站，信息123传给E 网站，B 网站的信息12传给C 网站，C 网站的信息3传给B 网站，D 网站的信息4传给E 网站，E 网站的信息5传给D 网站；第3秒将B 网站的信息5传给C 网站，C 网站的信息4传给B 网站，信息123传给D 网站，而A,E 网站可以直接将所有信息传播给另一个网站F,G 此时A,B,C,D,E,F,G 网站均拥有信息12345，且每个网站都剩下p-3秒的时间将信息传播给其他网站，故由A(B,C,D,E,F,G与A 相同）网站传播出的网站数为2P -3-1, 所以这种情况下，n=7 7*（2p -3-1）=7*2p -3，f （n,5）=8 n-7=n 1;