n,k最小廣播圖論文

1、<p>　　(n, k) 最小廣播圖的設(shè)計</p><p><b>　　摘要</b></p><p>　　本題是一個圖論問題，我們利用將源網(wǎng)站集中的思想對問題進(jìn)行求解。</p><p>　　對于第一問，由于對任意整數(shù)n，存在整數(shù)p，使得，故（n,k）廣播圖的時間=p。要在p秒內(nèi)將源網(wǎng)站的信息傳播給所有網(wǎng)站,那么所有源網(wǎng)站必須集中在一起

2、，這樣信息在規(guī)定的時間內(nèi)用盡量少的邊傳播完。對于k=1的情況，我們考慮到其傳播特點，每一個擁有信息的網(wǎng)站只傳播一次給下一個網(wǎng)站，邊相應(yīng)增加一條，且它是成倍增長的，故我們可以得到計算公式f(n,1)=1++++...++（n-）=n-1；當(dāng)k=2時，我們做了簡單的分析，發(fā)現(xiàn)2個源網(wǎng)站放在一起時，k=1和k=2的情況其實是相同的，那么f(n,2)=n-1；當(dāng)k=3和k=4時，我們列出了源網(wǎng)站連接的幾個最好的模型，考慮先用最短的時間將信息在源

3、網(wǎng)站之間傳播，使所有源網(wǎng)站都擁有所有信息，再由源網(wǎng)站將所有信息傳播給其他網(wǎng)站，又考慮到時間對源網(wǎng)站數(shù)的限制，我們發(fā)現(xiàn)：在網(wǎng)站數(shù)少時，可以用邊數(shù)少的模型，而當(dāng)網(wǎng)站數(shù)多時，就需要增加邊數(shù)來滿足要求，最終得到f(n,3)= ,f(n, 4)= 。</p><p>　　對于第二問，源網(wǎng)站數(shù)及為需要傳播信息的網(wǎng)站數(shù)，且n=，要在p秒內(nèi)將每個源網(wǎng)站每秒鐘均向其相鄰網(wǎng)站傳遞信息，只能任意源網(wǎng)站都相鄰，得到了。</p>

4、;<p>　　對于第三問，當(dāng)k較大時不易求出函數(shù)具體值，所以我們考慮其上下界，下界為n-1是容易求出的，求上界時，我們利用第二問的結(jié)論，得到了上界為，其中。</p><p>　　關(guān)鍵詞：最小廣播圖 源網(wǎng)站連接 時間最短</p><p><b>　　問題重述</b></p><p>　　設(shè)有n個網(wǎng)站，有若干條線路把他們連起來。每一

5、個網(wǎng)站都能接收信息和傳播信息，但只有k個（k≤n）網(wǎng)站能夠發(fā)布信息。能發(fā)布信息的網(wǎng)站稱為“源網(wǎng)站”。源網(wǎng)站產(chǎn)生的信息“+”要在最短的時間內(nèi)傳播到其它網(wǎng)站。它的傳播方式是這樣的：擁有信息“+”的網(wǎng)站每一秒鐘“有選擇”地向與它相連但未獲得該信息的某一個（最多一個）網(wǎng)站發(fā)送信息。這里所謂“有選擇”是指“使信息傳播的總時間最少”。例如：當(dāng)n=8時，最快的傳播過程是１傳２，２傳４，４傳８，所以至少需要3秒鐘。對一般情形，至少需要耗費秒時間（表示不

6、小于x的最小整數(shù)）。對給定的正整數(shù)n和k（k≤n），由n個網(wǎng)站（其中k個源網(wǎng)站）構(gòu)成的通訊系統(tǒng)，若每個源網(wǎng)站發(fā)布的信息“＋”都能按上述傳遞方式在秒內(nèi)傳播到所有網(wǎng)站，則稱該通訊系統(tǒng)為(n, k) 廣播圖。如果每個網(wǎng)站之間都有一條線路，顯然它是(n, k)-廣播圖，但它的造價太高了。線路的條數(shù)（以下簡稱“邊數(shù)”）最少的稱為(n, k)－最小廣播圖，將它的邊數(shù)記為f(n, k).</p><p>　　請設(shè)計(n, k)

7、－最小廣播圖，確定它的邊數(shù)f(n, k)：</p><p>　　(1)對k=1,2,3,4給出f(n, k)的數(shù)值；</p><p>　　(2)求，其中p為正整數(shù)；</p><p>　　(3)對5≤k≤n, 盡你的可能求f(n, k)的值或討論它的上下界。</p><p><b>　　問題分析</b></p>

8、<p>　?。╪,k）最小廣播圖問題是一個圖論問題，當(dāng)k較大時，我們并不能給出其邊數(shù)的準(zhǔn)確答案，故我們從k=1，2，3...慢慢著手，先畫出n=5，6，7，8，9時的最小廣播圖，從中發(fā)現(xiàn)規(guī)律，再將其拓展為一般問題，找出網(wǎng)站數(shù)與邊數(shù)之間的普遍關(guān)系。對于k=1，2時比較好分析，可以由（n,k）廣播圖的定義及其傳播方式得出結(jié)果，但當(dāng)k=3，4...時，我們需要考慮所有源網(wǎng)站之間的位置關(guān)系，她們對傳播時間和廣播圖的邊數(shù)有很大的關(guān)系

9、，所以我們打算建立模型從這方面入手。</p><p><b>　　模型假設(shè)</b></p><p>　　1.假設(shè)各個源網(wǎng)站發(fā)布的信息是不同的，即每個源網(wǎng)站的信息都需要傳播給其他網(wǎng)站</p><p>　　2.當(dāng)一個網(wǎng)站接收到多種信息時，它可以同時向其他網(wǎng)站傳播它所擁有的任一種信息一次，不同信息的傳播不受影響</p><p>

10、;　　3.k個源網(wǎng)站越集中，傳播時間越短，邊數(shù)越少</p><p><b>　　符號系統(tǒng)</b></p><p><b>　　n:總網(wǎng)站數(shù)</b></p><p><b>　　k：源網(wǎng)站數(shù)</b></p><p>　　f(n, k)：(n, k)－最小廣播圖的邊數(shù)</p&

11、gt;<p>　?。翰恍∮趚的最小整數(shù)</p><p>　　p：廣播圖的傳播時間，則=p，<n</p><p><b>　　模型建立</b></p><p><b>　　5.1關(guān)于問題一：</b></p><p>　　（1） k=1時(如圖1），“源網(wǎng)站”A將信息傳給網(wǎng)站B，此時

12、增加一條邊，之后，A,B再將信息傳給另兩個網(wǎng)站，邊數(shù)再增加兩條，即信息每傳遞一次，擁有信息的點就多一倍，邊數(shù)的增加數(shù)就等于擁有信息的網(wǎng)站數(shù)，當(dāng)最后一秒傳遞信息時，只需部分信息源傳遞信息給還未接受到信息的網(wǎng)站，增加的邊數(shù)即為剩余的未接收到信息的網(wǎng)站數(shù)，故f(n,1)=1++++...++（n-）=n-1；</p><p><b>　　A(+) B</b></p><p&

13、gt;　　圖1 k=1時的廣播圖</p><p>　?。?） k=2時（如圖2），可在k=1的結(jié)論基礎(chǔ)上，將第二個“源網(wǎng)站”放在B處，此時當(dāng)“源網(wǎng)站”B第一秒將信息傳遞給A時，A,B都擁有信息，第二秒A，B再傳遞信息時就與k=1時的情況相同了，故f(n,2)=f(n,1)=n-1；</p><p>　　A(+) B(+)</p><p>　　圖2 k=2時的廣

14、播圖</p><p>　　（3） k=3時，源網(wǎng)站的連接有以下兩種可能：</p><p><b>　　A 1</b></p><p>　　A B C</p><p>　　1 2 3</p><p><b>　　（1

15、） </b></p><p>　　B 2 C 3</p><p><b>　　（2）</b></p><p>　　要使邊數(shù)最少，那么我們先用最短的時間在源網(wǎng)站之間傳播，使所有源網(wǎng)站都擁有所有信息，再由源網(wǎng)站將所有信息傳播給其他網(wǎng)站即可。</p><p>　　對于第（1）種

16、情況：我們可以這樣設(shè)計（如圖3）：第1秒將B網(wǎng)站的信息2，C網(wǎng)站的信息3傳給A網(wǎng)站，A網(wǎng)站的信息1傳給B網(wǎng)站，此時，A網(wǎng)站含有信息123，B網(wǎng)站含有信息12，C網(wǎng)站含有信息3，第2秒將B網(wǎng)站的信息12傳給C網(wǎng)站，C網(wǎng)站信息3傳給B網(wǎng)站，此時A,B,C網(wǎng)站均擁有信息123，且每個網(wǎng)站都剩下p-2秒的時間將信息傳播給其他網(wǎng)站，而每個網(wǎng)站1秒只能將同一信息傳給一個網(wǎng)站，每增加一個網(wǎng)站就增加一條邊，故由A(B,C與A相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為1

17、+++...+=-1,所以這種情況下，n=3+3*（-1）=3*，f（n,3）=2+n-3=n-1;</p><p>　　1 2 3 12 123 3 123 123 123</p><p>　　A B C A B C A

18、 B C</p><p>　　圖3 k=3時情況（1）的廣播圖</p><p>　　當(dāng)n3*時，只需在上種情況的基礎(chǔ)上在最外圍減去多余的網(wǎng)站，每少一個網(wǎng)站就少一條邊，所以f(n,3)=n-1；</p><p>　　對于第（2）種情況：我們可以這樣設(shè)計（如圖4）：第1秒將A網(wǎng)站的信息1，C網(wǎng)站的信息3傳給B網(wǎng)站，B網(wǎng)站的信息2傳給A網(wǎng)站，此時，A網(wǎng)站含有信

19、息12，B網(wǎng)站含有信息123，C網(wǎng)站含有信息3，第2秒將B網(wǎng)站的信息3傳給A網(wǎng)站，信息12傳給C網(wǎng)站，而A網(wǎng)站可以直接將所有信息傳播給另一個網(wǎng)站D,此時A,B,C,D網(wǎng)站均擁有信息123，且每個網(wǎng)站都剩下p-2秒的時間將信息傳播給其他網(wǎng)站，同理知，由A(B,C，D與A相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為-1,所以這種情況下，n=4+4*（-1）=4*=，f（n,3）=4+n-4=n;</p><p>　　A 1

20、 A 123 A 123 D 123</p><p>　　B 2 C 3 B 12 C 3 B 123 C 123</p><p>　　圖4 k=3時情況（2）的廣播圖</p><p>　　當(dāng)3*<n時，f(n,3)=n;</p>

21、<p>　　綜上所述，f(n, 3)= 。</p><p>　?。?）k=4時，源網(wǎng)站的連接有以下兩種可能：</p><p>　　A 1 B 2</p><p>　　C 3 A 1 D 4</p><p>　　B 2

22、 D 4 C 3</p><p>　　(1) (2)</p><p>　　對于第（1）種情況：我們可以這樣設(shè)計（如圖5）：第1秒將B網(wǎng)站的信息2，C網(wǎng)站的信息3,D網(wǎng)站的信息4傳給A網(wǎng)站，A網(wǎng)站的信息1傳給B網(wǎng)站，此時，A網(wǎng)站含有信息1234，B網(wǎng)站含有信息12，C網(wǎng)站含有信息3，

23、D網(wǎng)站含有信息4，第2秒將A網(wǎng)站的信息12傳給C網(wǎng)站，信息34傳給B網(wǎng)站,第3秒將A網(wǎng)站的信息4傳給C網(wǎng)站，信息123傳給D網(wǎng)站，而B網(wǎng)站可以直接將所有信息傳播給另一個網(wǎng)站E,此時A,B,C,D,E網(wǎng)站均擁有信息1234，且每個網(wǎng)站都剩下p-3秒的時間將信息傳播給其他網(wǎng)站，而每個網(wǎng)站1秒只能將同一信息傳給一個網(wǎng)站，每增加一個網(wǎng)站就增加一條邊，故由A(B,C,D,E與A相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為1+++...+=-1,所以這種情況下，n=

24、5+5*（-1）=5*，f（n,4）=4+n-5=n-1;</p><p>　　C 3 A 1 D 4 C 3 A 1234 D 4</p><p>　　B 2 B 12 </p><p>　　C 123

25、A 1234 D 4 C 1234 A 1234 D 1234</p><p>　　B 1234 B 1234 E 1234</p><p>　　圖5 k=4時情況（1）的廣播圖</p><p>　　對于第（2）種情況：我們可以這樣設(shè)計（如圖6）：第1秒將A網(wǎng)站的信息1傳給D網(wǎng)站

26、，D網(wǎng)站的信息4傳給A網(wǎng)站，B網(wǎng)站的信息2傳給C網(wǎng)站，C網(wǎng)站的信息3傳給B網(wǎng)站，此時，A網(wǎng)站含有信息14，B網(wǎng)站含有信息23，C網(wǎng)站含有信息23，D網(wǎng)站含有信息14，第2秒將A網(wǎng)站的信息14傳給B網(wǎng)站，B網(wǎng)站的信息23傳給A網(wǎng)站，將D網(wǎng)站的信息14傳給C網(wǎng)站，C網(wǎng)站的23傳給D網(wǎng)站，此時A,B,C,D,網(wǎng)站均擁有信息1234，同理可知：-1,所以這種情況下，n=4+4*（-1）=，f（n,4）=4+n-4=n;</p>&

27、lt;p>　　A1 B2 A 14 B 23 A 1234 B1234</p><p>　　D4 C3 D 14 C 23 D1234 C1234</p><p>　　圖6 k=4時情況（2）的廣播圖</p><

28、p>　　綜上所述，f(n, 4)= </p><p><b>　　5.2關(guān)于問題二：</b></p><p>　　要求，即求n=k=時廣播圖的邊數(shù)。n =時，最短傳播時間為p秒，在此p秒內(nèi)每個源網(wǎng)站每秒鐘均向其相鄰網(wǎng)站傳遞信息（這樣才能保證傳播量相同時時間最短的要求），即每個結(jié)點應(yīng)有p條邊，又兩個結(jié)點共用一條邊，所以。</p><p>&

29、lt;b>　　5.3關(guān)于問題三：</b></p><p>　　根據(jù)問題一的求法我們同樣可以得到當(dāng)k=5時的f(n, 5)【詳細(xì)過程見附錄】</p><p>　　對于一般情況，已知：</p><p>　　下界的確定：當(dāng)源網(wǎng)站數(shù)目增加時，需要傳播的信息量增加，而在傳播的總網(wǎng)站數(shù)相等情況下，只有線路增加才能保證時間不變，所以f(n, k)f(n,k+1)

30、。所以。</p><p>　　上界的確定：所有的網(wǎng)站最后都應(yīng)具有所有源網(wǎng)站的信息，所以源網(wǎng)站之間應(yīng)路線最短、邊數(shù)最短，使得信息先在源網(wǎng)站內(nèi)傳播，再由源網(wǎng)站將多個信息同時傳播給其他非源網(wǎng)站，這樣才能節(jié)省時間。這相當(dāng)于源網(wǎng)站集中在內(nèi)圈、其他網(wǎng)站發(fā)散地連接在外圍。非源網(wǎng)站在外圍，所以增加一個網(wǎng)站那就在外圍先加一條邊即可，因此k一定時，n越大，函數(shù)值遞增但不嚴(yán)格遞增。所以能夠推出，對于，共有個源信息，在m秒內(nèi)，能夠有個網(wǎng)

31、站具有所有源網(wǎng)站的信息，剩下的網(wǎng)站只需在個網(wǎng)站中任選個結(jié)點，對應(yīng)的增加條邊，</p><p><b>　　，所以</b></p><p><b>　　五．模型分析</b></p><p><b>　　模型的優(yōu)點</b></p><p>　　首先該模型的假設(shè)對實際問題作了簡化，并

32、得出3個基本的結(jié)論 ，為問題的求解作好了準(zhǔn)備工作。當(dāng)k=1、2、3、4時根據(jù)我們的分析能夠得出準(zhǔn)確的函數(shù)f(n,k)值。同時在附錄里得出了k=5的情況，k較大時不易求出函數(shù)具體值，但是我們根據(jù)“當(dāng)源網(wǎng)站數(shù)目增加時，需要傳播的信息量增加，而在傳播的總網(wǎng)站數(shù)相等情況下，只有線路增加才能保證時間不變”以及“信息先在源網(wǎng)站內(nèi)傳播，再由源網(wǎng)站將多個信息同時傳播給其他非源網(wǎng)站，這樣才能節(jié)省時間”推出了上下界的關(guān)系。</p><p

33、><b>　　2、模型的缺點</b></p><p>　　在第（3）問中的解答沒有完整的理論體系，只是根據(jù)實際情況進(jìn)行假設(shè)，而沒有具體的理論支撐，沒有考慮其他的情況。 </p><p><b>　　3、模型的改進(jìn)</b></p><p>　　因為源信息的傳播可看作樹的生長，因此還可以用樹圖來解釋邊數(shù)值。</p&

34、gt;<p><b>　　模型推廣</b></p><p>　　在網(wǎng)絡(luò)特別是互聯(lián)網(wǎng)迅速發(fā)展的今天，網(wǎng)絡(luò)成為人們娛樂方式的最常用選擇，對于網(wǎng)絡(luò)經(jīng)營者來說這幾個問題是需要考慮的：一定用戶時，如何建立通信線路使用戶最快收到服務(wù)器上的最新消息同時線路越少越好；什么時候線路的利用率最大，即線路每時每刻都在工作；一定數(shù)量的用戶和服務(wù)器時，最多需要幾條線路等等。</p><

35、;p>　　當(dāng)然，該模型是在對實際問題作了一些簡化后得到的結(jié)果，而在實際網(wǎng)絡(luò)通信中也許不成立，如兩點間的通信應(yīng)受帶寬限制，不可能在一秒內(nèi)傳遞任意多的信息。所以模型的改進(jìn)空間還是很大的。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1]趙靜，數(shù)學(xué)建模與數(shù)學(xué)實驗[M]，高等教育出版社，2008</p><p>　　[2]

36、譚永基等，數(shù)學(xué)模型，上海復(fù)旦大學(xué)出版社，1996</p><p><b>　　附錄</b></p><p>　　k=5時，源網(wǎng)站的連接有以下多種可能：</p><p>　　情況1：我們可以這樣設(shè)計（如圖7）：第1秒將B網(wǎng)站的信息2，C網(wǎng)站的信息3,D網(wǎng)站的信息4，E網(wǎng)站的信息5傳給A網(wǎng)站,A網(wǎng)站的信息1傳給B網(wǎng)站，此時，A網(wǎng)站含有信息12345

37、，B網(wǎng)站含有信息12，C網(wǎng)站含有信息3，D網(wǎng)站含有信息4，E網(wǎng)站含有信息5，第2秒將A網(wǎng)站的信息12傳給C網(wǎng)站，信息345傳給B網(wǎng)站,第3秒將A網(wǎng)站的信息45傳給C網(wǎng)站，信息123傳給D網(wǎng)站，而B網(wǎng)站可以直接將所有信息傳播給另一個網(wǎng)站F,第4秒將A網(wǎng)站的信息1234傳給E網(wǎng)站，信息5傳給D網(wǎng)站，而B，C,F網(wǎng)站可以直接將所有信息傳播給另一個網(wǎng)站G,H,I,,此時A,B,C,D,E,F,G,H,I網(wǎng)站均擁有信息12345，且每個網(wǎng)站都剩下

38、p-4秒的時間將信息傳播給其他網(wǎng)站，而每個網(wǎng)站1秒只能將同一信息傳給一個網(wǎng)站，每增加一個網(wǎng)站就增加一條邊，故由A(B,C,D,E,F,G,H,I與A相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為-1,所以這種情況下，n=9+9*（-1）=9*，f（n,5）=8+n-9=n-1;</p><p>　　B 2 B12 B12345</p>&l

39、t;p>　　C3 A1 E5 C3 A12345 E5 C123 A12345 E5</p><p>　　D4 D4 D4</p><p><b>　　I 12345</b></p>

40、<p><b>　　G12345</b></p><p>　　F12345 F12345 </p><p>　　B12345 B12345</p><p>　　C12345 A12345 E5 C12345

41、 A12345 E12345</p><p>　　D1234 H12345 D12345</p><p>　　圖7 k=5時情況1的廣播圖</p><p>　　情況2：我們可以這樣設(shè)計（如圖8）：第1秒將B網(wǎng)站的信息2，E網(wǎng)站的信息5傳給A網(wǎng)站,A網(wǎng)站的信息1，C網(wǎng)站的信息3傳給B網(wǎng)站,D網(wǎng)站的信息4傳給E網(wǎng)站，此時，A網(wǎng)站含有信息1

42、25，B網(wǎng)站含有信息123，C網(wǎng)站含有信息3，D網(wǎng)站含有信息4，E網(wǎng)站含有信息45；第2秒將A網(wǎng)站的信息5傳給B網(wǎng)站，信息4傳給E網(wǎng)站，B網(wǎng)站的信息3傳給A網(wǎng)站，信息12傳給C網(wǎng)站，C網(wǎng)站的信息3傳給D網(wǎng)站，D網(wǎng)站的信息4傳給E網(wǎng)站，E網(wǎng)站的信息5傳給D網(wǎng)站；第3秒將B網(wǎng)站的信息5傳給C網(wǎng)站，C網(wǎng)站的信息4傳給B網(wǎng)站，D網(wǎng)站的信息3傳給E網(wǎng)站，E網(wǎng)站的信息12傳給D網(wǎng)站，而A網(wǎng)站可以直接將所有信息傳播給另一個網(wǎng)站F,此時A,B,C,D,

43、E,F網(wǎng)站均擁有信息12345，且每個網(wǎng)站都剩下p-3秒的時間將信息傳播給其他網(wǎng)站，故由A(B,C,D,E,F與A相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為-1,所以這種情況下，n=6+6*（-1）=6*，f（n,5）=6+n-6=n;</p><p>　　A 1 A125 A12345</p><p>　　B2

44、 E5 B123 E45 B1235 E1245</p><p>　　C3 D4 C3 D4 C1234 D345</p><p>　　A12345 F12345</p><p>　　B12345

45、 E12345</p><p>　　C12345 D12345</p><p>　　圖8 k=5時情況2的廣播圖</p><p>　　情況3：我們可以這樣設(shè)計（如圖9）：第1秒將B網(wǎng)站的信息2，C網(wǎng)站的信息3,E網(wǎng)站的信息5傳給A網(wǎng)站,A網(wǎng)站的信息1傳給B網(wǎng)站,D網(wǎng)站的信息4傳給C網(wǎng)站，此時，A網(wǎng)站含有信息1235，B網(wǎng)站含有信息12，C網(wǎng)站含有

46、信息34，D網(wǎng)站含有信息4，E網(wǎng)站含有信息5；第2秒將A網(wǎng)站的信息5傳給B網(wǎng)站，信息123傳給E網(wǎng)站，B網(wǎng)站的信息12傳給C網(wǎng)站，C網(wǎng)站的信息3傳給B網(wǎng)站，D網(wǎng)站的信息4傳給E網(wǎng)站，E網(wǎng)站的信息5傳給D網(wǎng)站；第3秒將B網(wǎng)站的信息5傳給C網(wǎng)站，C網(wǎng)站的信息4傳給B網(wǎng)站，信息123傳給D網(wǎng)站，而A,E網(wǎng)站可以直接將所有信息傳播給另一個網(wǎng)站F,G此時A,B,C,D,E,F,G網(wǎng)站均擁有信息12345，且每個網(wǎng)站都剩下p-3秒的時間將信息傳播給

47、其他網(wǎng)站，故由A(B,C,D,E,F,G與A相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為-1,所以這種情況下，n=7+7*（-1）=7*，f（n,5）=8+n-7=n+1;</p><p>　　A1 A1235 A12345</p><p>　　B2 E5 B12 E5

48、 B1235 E12345</p><p>　　C3 D4 C34 D4 C1234 D45</p><p>　　A12345 F12345</p><p>　　B12345 E12345 G12345</p><p>　　C

49、12345 D12345</p><p>　　圖9 k=5時情況3的廣播圖</p><p>　　情況4：我們可以這樣設(shè)計（如圖10）：第1秒將B網(wǎng)站的信息2，C網(wǎng)站的信息3,E網(wǎng)站的信息5傳給A網(wǎng)站,A網(wǎng)站的信息1，D網(wǎng)站的信息4傳給B網(wǎng)站,此時，A網(wǎng)站含有信息1235，B網(wǎng)站含有信息124，C網(wǎng)站含有信息3，D網(wǎng)站含有信息4，E網(wǎng)站含有信息5；第2秒將A網(wǎng)站的信息5傳給B網(wǎng)站，信

50、息123傳給E網(wǎng)站，B網(wǎng)站的信息12傳給C網(wǎng)站，C網(wǎng)站的信息3傳給B網(wǎng)站，D網(wǎng)站的信息4傳給E網(wǎng)站，E網(wǎng)站的信息5傳給D網(wǎng)站；第3秒將C網(wǎng)站的信息123傳給D網(wǎng)站，D網(wǎng)站的信息45傳給C網(wǎng)站，而A,B,E網(wǎng)站可以直接將所有信息傳播給另一個網(wǎng)站F,G,H此時A,B,C,D,E,F,G,H網(wǎng)站均擁有信息12345，且每個網(wǎng)站都剩下p-3秒的時間將信息傳播給其他網(wǎng)站，故由A(B,C,D,E,F,G,H與A相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為-1,所以這

51、種情況下，n=8+8*（-1）=8*=，f（n,5）=10+n-8=n+2;</p><p>　　A1 A1235 A12345</p><p>　　B2 E5 B124 E5 B12345 E12345</p><p>

52、;　　C3 D4 C3 D4 C123 D45</p><p>　　A12345 F12345</p><p>　　G12345 B12345 E12345 H12345</p><p>　　C12345 D12345</p><p>