n,k最小廣播圖論文

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

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

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

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

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

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

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

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

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

10、;　　3.k個(gè)源網(wǎng)站越集中，傳播時(shí)間越短，邊數(shù)越少</p><p><b>　　符號(hào)系統(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>　　：不小于x的最小整數(shù)</p><p>　　p：廣播圖的傳播時(shí)間，則=p，<n</p><p><b>　　模型建立</b></p><p><b>　　5.1關(guān)于問(wèn)題一：</b></p><p>　　（1） k=1時(shí)(如圖1），“源網(wǎng)站”A將信息傳給網(wǎng)站B，此時(shí)

12、增加一條邊，之后，A,B再將信息傳給另兩個(gè)網(wǎng)站，邊數(shù)再增加兩條，即信息每傳遞一次，擁有信息的點(diǎn)就多一倍，邊數(shù)的增加數(shù)就等于擁有信息的網(wǎng)站數(shù)，當(dāng)最后一秒傳遞信息時(shí)，只需部分信息源傳遞信息給還未接受到信息的網(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時(shí)的廣播圖</p><p>　?。?） k=2時(shí)（如圖2），可在k=1的結(jié)論基礎(chǔ)上，將第二個(gè)“源網(wǎng)站”放在B處，此時(shí)當(dāng)“源網(wǎng)站”B第一秒將信息傳遞給A時(shí)，A,B都擁有信息，第二秒A，B再傳遞信息時(shí)就與k=1時(shí)的情況相同了，故f(n,2)=f(n,1)=n-1；</p><p>　　A(+) B(+)</p><p>　　圖2 k=2時(shí)的廣

14、播圖</p><p>　　（3） k=3時(shí)，源網(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ù)最少，那么我們先用最短的時(shí)間在源網(wǎng)站之間傳播，使所有源網(wǎng)站都擁有所有信息，再由源網(wǎng)站將所有信息傳播給其他網(wǎng)站即可。</p><p>　　對(duì)于第（1）種

16、情況：我們可以這樣設(shè)計(jì)（如圖3）：第1秒將B網(wǎng)站的信息2，C網(wǎng)站的信息3傳給A網(wǎng)站，A網(wǎng)站的信息1傳給B網(wǎng)站，此時(shí)，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)站，此時(shí)A,B,C網(wǎng)站均擁有信息123，且每個(gè)網(wǎng)站都剩下p-2秒的時(shí)間將信息傳播給其他網(wǎng)站，而每個(gè)網(wǎng)站1秒只能將同一信息傳給一個(gè)網(wǎng)站，每增加一個(gè)網(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時(shí)情況（1）的廣播圖</p><p>　　當(dāng)n3*時(shí)，只需在上種情況的基礎(chǔ)上在最外圍減去多余的網(wǎng)站，每少一個(gè)網(wǎng)站就少一條邊，所以f(n,3)=n-1；</p><p>　　對(duì)于第（2）種情況：我們可以這樣設(shè)計(jì)（如圖4）：第1秒將A網(wǎng)站的信息1，C網(wǎng)站的信息3傳給B網(wǎng)站，B網(wǎng)站的信息2傳給A網(wǎng)站，此時(shí)，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)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站D,此時(shí)A,B,C,D網(wǎng)站均擁有信息123，且每個(gè)網(wǎng)站都剩下p-2秒的時(shí)間將信息傳播給其他網(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時(shí)情況（2）的廣播圖</p><p>　　當(dāng)3*<n時(shí)，f(n,3)=n;</p>

21、<p>　　綜上所述，f(n, 3)= 。</p><p>　　（4）k=4時(shí)，源網(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>　　對(duì)于第（1）種情況：我們可以這樣設(shè)計(jì)（如圖5）：第1秒將B網(wǎng)站的信息2，C網(wǎng)站的信息3,D網(wǎng)站的信息4傳給A網(wǎng)站，A網(wǎng)站的信息1傳給B網(wǎng)站，此時(shí)，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(niǎo)網(wǎng)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站E,此時(shí)A,B,C,D,E網(wǎng)站均擁有信息1234，且每個(gè)網(wǎng)站都剩下p-3秒的時(shí)間將信息傳播給其他網(wǎng)站，而每個(gè)網(wǎng)站1秒只能將同一信息傳給一個(gè)網(wǎng)站，每增加一個(gè)網(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時(shí)情況（1）的廣播圖</p><p>　　對(duì)于第（2）種情況：我們可以這樣設(shè)計(jì)（如圖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)站，此時(shí)，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)站，此時(shí)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時(shí)情況（2）的廣播圖</p><

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

29、lt;b>　　5.3關(guān)于問(wèn)題三：</b></p><p>　　根據(jù)問(wèn)題一的求法我們同樣可以得到當(dāng)k=5時(shí)的f(n, 5)【詳細(xì)過(guò)程見(jiàn)附錄】</p><p>　　對(duì)于一般情況，已知：</p><p>　　下界的確定：當(dāng)源網(wǎng)站數(shù)目增加時(shí)，需要傳播的信息量增加，而在傳播的總網(wǎng)站數(shù)相等情況下，只有線路增加才能保證時(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)站將多個(gè)信息同時(shí)傳播給其他非源網(wǎng)站，這樣才能節(jié)省時(shí)間。這相當(dāng)于源網(wǎng)站集中在內(nèi)圈、其他網(wǎng)站發(fā)散地連接在外圍。非源網(wǎng)站在外圍，所以增加一個(gè)網(wǎng)站那就在外圍先加一條邊即可，因此k一定時(shí)，n越大，函數(shù)值遞增但不嚴(yán)格遞增。所以能夠推出，對(duì)于，共有個(gè)源信息，在m秒內(nèi)，能夠有個(gè)網(wǎng)

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

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

33、><b>　　2、模型的缺點(diǎn)</b></p><p>　　在第（3）問(wèn)中的解答沒(méi)有完整的理論體系，只是根據(jù)實(shí)際情況進(jìn)行假設(shè)，而沒(méi)有具體的理論支撐，沒(méi)有考慮其他的情況。 </p><p><b>　　3、模型的改進(jìn)</b></p><p>　　因?yàn)樵葱畔⒌膫鞑タ煽醋鳂?shù)的生長(zhǎng)，因此還可以用樹(shù)圖來(lái)解釋邊數(shù)值。</p&

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

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

36、譚永基等，數(shù)學(xué)模型，上海復(fù)旦大學(xué)出版社，1996</p><p><b>　　附錄</b></p><p>　　k=5時(shí)，源網(wǎng)站的連接有以下多種可能：</p><p>　　情況1：我們可以這樣設(shè)計(jì)（如圖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)站，此時(shí)，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(niǎo)網(wǎng)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站F,第4秒將A網(wǎng)站的信息1234傳給E網(wǎng)站，信息5傳給D網(wǎng)站，而B(niǎo)，C,F網(wǎng)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站G,H,I,,此時(shí)A,B,C,D,E,F,G,H,I網(wǎng)站均擁有信息12345，且每個(gè)網(wǎng)站都剩下

38、p-4秒的時(shí)間將信息傳播給其他網(wǎng)站，而每個(gè)網(wǎng)站1秒只能將同一信息傳給一個(gè)網(wǎng)站，每增加一個(gè)網(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時(shí)情況1的廣播圖</p><p>　　情況2：我們可以這樣設(shè)計(jì)（如圖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)站，此時(shí)，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)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站F,此時(shí)A,B,C,D,

43、E,F網(wǎng)站均擁有信息12345，且每個(gè)網(wǎng)站都剩下p-3秒的時(shí)間將信息傳播給其他網(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時(shí)情況2的廣播圖</p><p>　　情況3：我們可以這樣設(shè)計(jì)（如圖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)站，此時(shí)，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)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站F,G此時(shí)A,B,C,D,E,F,G網(wǎng)站均擁有信息12345，且每個(gè)網(wǎng)站都剩下p-3秒的時(shí)間將信息傳播給

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時(shí)情況3的廣播圖</p><p>　　情況4：我們可以這樣設(shè)計(jì)（如圖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)站,此時(shí)，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)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站F,G,H此時(shí)A,B,C,D,E,F,G,H網(wǎng)站均擁有信息12345，且每個(gè)網(wǎng)站都剩下p-3秒的時(shí)間將信息傳播給其他網(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>