n,k最小广播图论文.doc

(n, k) 最小广播图的设计摘要本题是一个图论问题，我们利用将源网站集中的思想对问题进行求解。对于第一问，由于对任意整数n，存在整数p，使得，故（n,k）广播图的时间=p。要在p秒内将源网站的信息传播给所有网站,那么所有源网站必须集中在一起，这样信息在规定的时间内用尽量少的边传播完。对于k=1的情况，我们考虑到其传播特点，每一个拥有信息的网站只传播一次给下一个网站，边相应增加一条，且它是成倍增长的，故我们可以得到计算公式f(n,1)=1+.+（n-）=n-1；当k=2时，我们做了简单的分析，发现2个源网站放在一起时，k=1和k=2的情况其实是相同的，那么f(n,2)=n-1；当k=3和k=4时，我们列出了源网站连接的几个最好的模型，考虑先用最短的时间将信息在源网站之间传播，使所有源网站都拥有所有信息，再由源网站将所有信息传播给其他网站，又考虑到时间对源网站数的限制，我们发现：在网站数少时，可以用边数少的模型，而当网站数多时，就需要增加边数来满足要求，最终得到f(n,3)= ,f(n, 4)= 。对于第二问，源网站数及为需要传播信息的网站数，且n=，要在p秒内将每个源网站每秒钟均向其相邻网站传递信息，只能任意源网站都相邻，得到了。对于第三问，当k较大时不易求出函数具体值，所以我们考虑其上下界，下界为n-1是容易求出的，求上界时，我们利用第二问的结论，得到了上界为，其中。关键词：最小广播图 源网站连接 时间最短一、 问题重述设有n个网站，有若干条线路把他们连起来。每一个网站都能接收信息和传播信息，但只有k个（kn）网站能够发布信息。能发布信息的网站称为“源网站”。源网站产生的信息“+”要在最短的时间内传播到其它网站。它的传播方式是这样的：拥有信息“+”的网站每一秒钟“有选择”地向与它相连但未获得该信息的某一个（最多一个）网站发送信息。这里所谓“有选择”是指“使信息传播的总时间最少”。例如：当n=8时，最快的传播过程是传，传，传，所以至少需要3秒钟。对一般情形，至少需要耗费秒时间（表示不小于x的最小整数）。对给定的正整数n和k（kn），由n个网站（其中k个源网站）构成的通讯系统，若每个源网站发布的信息“”都能按上述传递方式在秒内传播到所有网站，则称该通讯系统为(n, k) 广播图。如果每个网站之间都有一条线路，显然它是(n, k)-广播图，但它的造价太高了。线路的条数（以下简称“边数”）最少的称为(n, k)最小广播图，将它的边数记为f(n, k).请设计(n, k)最小广播图，确定它的边数f(n, k)：(1)对k=1,2,3,4给出f(n, k)的数值；(2)求，其中p为正整数；(3)对5kn, 尽你的可能求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的最小整数p：广播图的传播时间，则=p，n五、 模型建立5.1关于问题一：（1） k=1时(如图1），“源网站”A将信息传给网站B，此时增加一条边，之后，A,B再将信息传给另两个网站，边数再增加两条，即信息每传递一次，拥有信息的点就多一倍，边数的增加数就等于拥有信息的网站数，当最后一秒传递信息时，只需部分信息源传递信息给还未接受到信息的网站，增加的边数即为剩余的未接收到信息的网站数，故f(n,1)=1+.+（n-）=n-1； A(+) B 图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； A(+) B(+) 图2 k=2时的广播图（3） k=3时，源网站的连接有以下两种可能： A 1A B C1 2 3 （1） B 2 C 3 （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+.+=-1,所以这种情况下，n=3+3*（-1）=3*，f（n,3）=2+n-3=n-1;1 2 3 12 123 3 123 123 123A B C A B C A B C图3 k=3时情况（1）的广播图 当n3*时，只需在上种情况的基础上在最外围减去多余的网站，每少一个网站就少一条边，所以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相同）网站传播出的网站数为-1,所以这种情况下，n=4+4*（-1）=4*=，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*n时，f(n,3)=n;综上所述，f(n, 3)= 。（4）k=4时，源网站的连接有以下两种可能： A 1 B 2C 3 A 1 D 4 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+.+=-1,所以这种情况下，n=5+5*（-1）=5*，f（n,4）=4+n-5=n-1;C 3 A 1 D 4 C 3 A 1234 D 4 B 2 B 12 C 123 A 1234 D 4 C 1234 A 1234 D 1234 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，同理可知：-1,所以这种情况下，n=4+4*（-1）=，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）的广播图综上所述，f(n, 4)= 5.2关于问题二：要求，即求n=k=时广播图的边数。n =时，最短传播时间为p秒，在此p秒内每个源网站每秒钟均向其相邻网站传递信息（这样才能保证传播量相同时时间最短的要求），即每个结点应有p条边，又两个结点共用一条边，所以。5.3关于问题三： 根据问题一的求法我们同样可以得到当k=5时的f(n, 5)【详细过程见附录】对于一般情况，已知：下界的确定：当源网站数目增加时，需要传播的信息量增加，而在传播的总网站数相等情况下，只有线路增加才能保证时间不变，所以f(n, k)f(n,k+1)。所以。上界的确定：所有的网站最后都应具有所有源网站的信息，所以源网站之间应路线最短、边数最短，使得信息先在源网站内传播，再由源网站将多个信息同时传播给其他非源网站，这样才能节省时间。这相当于源网站集中在内圈、其他网站发散地连接在外围。非源网站在外围，所以增加一个网站那就在外围先加一条边即可，因此k一定时，n越大，函数值递增但不严格递增。所以能够推出，对于，共有个源信息，在m秒内，能够有个网站具有所有源网站的信息，剩下的网站只需在个网站中任选个结点，对应的增加条边，所以五模型分析1、 模型的优点首先该模型的假设对实际问题作了简化，并得出3个基本的结论 ，为问题的求解作好了准备工作。当k=1、2、3、4时根据我们的分析能够得出准确的函数f(n,k)值。同时在附录里得出了k=5的情况，k较大时不易求出函数具体值，但是我们根据“当源网站数目增加时，需要传播的信息量增加，而在传播的总网站数相等情况下，只有线路增加才能保证时间不变”以及“信息先在源网站内传播，再由源网站将多个信息同时传播给其他非源网站，这样才能节省时间”推出了上下界的关系。2、模型的缺点在第（3）问中的解答没有完整的理论体系，只是根据实际情况进行假设，而没有具体的理论支撑，没有考虑其他的情况。 3、模型的改进因为源信息的传播可看作树的生长，因此还可以用树图来解释边数值。六、 模型推广在网络特别是互联网迅速发展的今天，网络成为人们娱乐方式的最常用选择，对于网络经营者来说这几个问题是需要考虑的：一定用户时，如何建立通信线路使用户最快收到服务器上的最新消息同时线路越少越好；什么时候线路的利用率最大，即线路每时每刻都在工作；一定数量的用户和服务器时，最多需要几条线路等等。当然，该模型是在对实际问题作了一些简化后得到的结果，而在实际网络通信中也许不成立，如两点间的通信应受带宽限制，不可能在一秒内传递任意多的信息。所以模型的改进空间还是很大的。七、 参考文献1赵静，数学建模与数学实验M，高等教育出版社，20082谭永基等，数学模型，上海复旦大学出版社，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相同）网站传播出的网站数为-1,所以这种情况下，n=9+9*（-1）=9*，f（n,5）=8+n-9=n-1; B 2 B12 B12345C3 A1 E5 C3 A12345 E5 C123 A12345 E5 D4 D4 D4 I 12345 G12345 F12345 F12345 B12345 B12345 C12345 A12345 E5 C12345 A12345 E12345 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相同）网站传播出的网站数为-1,所以这种情况下，n=6+6*（-1）=6*，f（n,5）=6+n-6=n; A 1 A125 A12345B2 E5 B123 E45 B1235 E1245 C3 D4 C3 D4 C1234 D345 A12345 F12345 B12345 E12345 C12345 D12345图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相同）网站传播出的网站数为-1,所以这种情况