n,k最小廣播圖論文

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

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

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

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

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

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

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

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

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

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

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

12、增加一條邊，之后，A,B再將信息傳給另兩個網站，邊數再增加兩條，即信息每傳遞一次，擁有信息的點就多一倍，邊數的增加數就等于擁有信息的網站數，當最后一秒傳遞信息時，只需部分信息源傳遞信息給還未接受到信息的網站，增加的邊數即為剩余的未接收到信息的網站數，故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的結論基礎上，將第二個“源網站”放在B處，此時當“源網站”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時，源網站的連接有以下兩種可能：</p><p><b>　　A 1</b></p><p>　　A B C</p><p>　　1 2 3</p><p><b>　?。?

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

16、情況：我們可以這樣設計（如圖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

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

19、息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;</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>　　當3*<n時，f(n,3)=n;</p>

21、<p>　　綜上所述，f(n, 3)= 。</p><p>　　（4）k=4時，源網站的連接有以下兩種可能：</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）種情況：我們可以這樣設計（如圖5）：第1秒將B網站的信息2，C網站的信息3,D網站的信息4傳給A網站，A網站的信息1傳給B網站，此時，A網站含有信息1234，B網站含有信息12，C網站含有信息3，

23、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=

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）種情況：我們可以這樣設計（如圖6）：第1秒將A網站的信息1傳給D網站

26、，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;</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關于問題二：</b></p><p>　　要求，即求n=k=時廣播圖的邊數。n =時，最短傳播時間為p秒，在此p秒內每個源網站每秒鐘均向其相鄰網站傳遞信息（這樣才能保證傳播量相同時時間最短的要求），即每個結點應有p條邊，又兩個結點共用一條邊，所以。</p><p>&

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

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

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

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

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

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

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

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

37、，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，且每個網站都剩下

38、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;</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：我們可以這樣設計（如圖8）：第1秒將B網站的信息2，E網站的信息5傳給A網站,A網站的信息1，C網站的信息3傳給B網站,D網站的信息4傳給E網站，此時，A網站含有信息1

42、25，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,

43、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;</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：我們可以這樣設計（如圖9）：第1秒將B網站的信息2，C網站的信息3,E網站的信息5傳給A網站,A網站的信息1傳給B網站,D網站的信息4傳給C網站，此時，A網站含有信息1235，B網站含有信息12，C網站含有

46、信息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秒的時間將信息傳播給

47、其他網站，故由A(B,C,D,E,F,G與A相同）網站傳播出的網站數為-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：我們可以這樣設計（如圖10）：第1秒將B網站的信息2，C網站的信息3,E網站的信息5傳給A網站,A網站的信息1，D網站的信息4傳給B網站,此時，A網站含有信息1235，B網站含有信息124，C網站含有信息3，D網站含有信息4，E網站含有信息5；第2秒將A網站的信息5傳給B網站，信

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