(n, k) 最小廣播圖的設(shè)計(jì)摘要本題是一個(gè)圖論問題，我們利用將源網(wǎng)站集中的思想對(duì)問題進(jìn)行求解。 對(duì)于第一問，由于對(duì)任意整數(shù)n ，存在整數(shù)p ，使得2p -1

(n, k) 最小廣播圖的設(shè)計(jì)

摘要

本題是一個(gè)圖論問題，我們利用將源網(wǎng)站集中的思想對(duì)問題進(jìn)行求解。 對(duì)于第一問，由于對(duì)任意整數(shù)n ，存在整數(shù)p ，使得2p -1

p -1p -3??n -1, 2

對(duì)于第二問，源網(wǎng)站數(shù)及為需要傳播信息的網(wǎng)站數(shù)，且n=2p ，要在p 秒內(nèi)將每個(gè)源網(wǎng)站每秒鐘均向其相鄰網(wǎng)站傳遞信息，只能任意源網(wǎng)站都相鄰，得到了f (2p , 2p ) =p *n ÷2=p ?2p -1。

對(duì)于第三問，當(dāng)k 較大時(shí)不易求出函數(shù)具體值，所以我們考慮其上下界，下界為n-1是容易求出的，求上界時(shí)，我們利用第二問的結(jié)論，得到了上界為2p 2m -1*(m -2) ，其中2m -1

關(guān)鍵詞：最小廣播圖 源網(wǎng)站連接 時(shí)間最短

一、 問題重述

設(shè)有n 個(gè)網(wǎng)站，有若干條線路把他們連起來。每一個(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í)，最快的傳播過程是１傳２，２傳４，４傳８，所以至少需要3秒鐘。對(duì)一般情形，至少需要耗費(fèi)?log 2n ?秒時(shí)間（?x ?表示不小于x 的最小整數(shù)）。對(duì)給定的正整數(shù)n 和k （k ≤n ），由n 個(gè)網(wǎng)站（其中k 個(gè)源網(wǎng)站）構(gòu)成的通訊系統(tǒng)，若每個(gè)源網(wǎng)站發(fā)布的信息“＋”都能按上述傳遞方式在?log 2n ?秒內(nèi)傳播到所有網(wǎng)站，則稱該通訊系統(tǒng)為(n, k) 廣播圖。如果每個(gè)網(wǎng)站之間都有一條線路，顯然它是(n, k)-廣播圖，但它的造價(jià)太高了。線路的條數(shù)（以下簡(jiǎn)稱“邊數(shù)”）最少的稱為(n, k) －最小廣播圖，將它的邊數(shù)記為f(n, k).

請(qǐng)?jiān)O(shè)計(jì)(n, k)－最小廣播圖，確定它的邊數(shù)f(n, k)：

(1)對(duì)k=1,2,3,4給出f(n, k)的數(shù)值；

(2)求f (2p , 2p ) ，其中p 為正整數(shù)；

(3)對(duì)5≤k ≤n, 盡你的可能求f(n, k)的值或討論它的上下界。

二、 問題分析

（n,k ）最小廣播圖問題是一個(gè)圖論問題，當(dāng)k 較大時(shí)，我們并不能給出其邊數(shù)的準(zhǔn)確答案，故我們從k=1，2，3... 慢慢著手，先畫出n=5，6，7，8，9時(shí)的最小廣播圖，從中發(fā)現(xiàn)規(guī)律，再將其拓展為一般問題，找出網(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)系，所以我們打算建立模型從這方面入手。

三、 模型假設(shè)

1. 假設(shè)各個(gè)源網(wǎng)站發(fā)布的信息是不同的，即每個(gè)源網(wǎng)站的信息都需要傳播給其他網(wǎng)站

2. 當(dāng)一個(gè)網(wǎng)站接收到多種信息時(shí)，它可以同時(shí)向其他網(wǎng)站傳播它所擁有的任一種信息一次，不同信息的傳播不受影響

3.k 個(gè)源網(wǎng)站越集中，傳播時(shí)間越短，邊數(shù)越少

四、 符號(hào)系統(tǒng)

n:總網(wǎng)站數(shù)

k ：源網(wǎng)站數(shù)

f(n, k)：(n, k)－最小廣播圖的邊數(shù)

?x ?：不小于x 的最小整數(shù)

p ：廣播圖的傳播時(shí)間，則?log 2n ?=p，2p -1

五、 模型建立

5.1關(guān)于問題一：

（1） k=1時(shí)(如圖1），“源網(wǎng)站”A 將信息傳給網(wǎng)站B ，此時(shí)增加一條邊，之后，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 21 22 23 ... 2[log 2n ]-2 （n-2[log 2n ]-1）=n-1；

圖1 k=1時(shí)的廣播圖

（2） 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；

圖2 k=2時(shí)的廣播圖

（3） k=3時(shí)，源網(wǎng)站的連接有以下兩種可能：

1 2 3

（1）

B 2 （2）

要使邊數(shù)最少，那么我們先用最短的時(shí)間在源網(wǎng)站之間傳播，使所有源網(wǎng)站都擁有所有信息，再由源網(wǎng)站將所有信息傳播給其他網(wǎng)站即可。

對(duì)于第（1）種情況：我們可以這樣設(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 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時(shí)情況（1）的廣播圖 當(dāng)n ≤3*2p -2時(shí)，只需在上種情況的基礎(chǔ)上在最外圍減去多余的網(wǎng)站，每少

一個(gè)網(wǎng)站就少一條邊，所以f(n,3)=n-1；

對(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)站含有信息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ù)為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時(shí)情況（2）的廣播圖

當(dāng)3*2p -2

p -1p -2??n -1, 2

（4）k=4時(shí)，源網(wǎng)站的連接有以下兩種可能：

A 1 B 2

D 4 C 3

(1) (2)

對(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，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)站可以直接將所有信息

傳播給另一個(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 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時(shí)情況（1）的廣播圖

對(duì)于第（2）種情況：我們可以這樣設(shè)計(jì)（如圖6）：第1秒將A 網(wǎng)站的信息1傳給D 網(wǎng)站，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，同理可知：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時(shí)情況（2）的廣播圖

p -1p -3??n -1, 2

5.2關(guān)于問題二：

要求f (2p , 2p ) ，即求n=k=2p 時(shí)廣播圖的邊數(shù)。n =2p 時(shí)，最短傳播時(shí)間為p 秒，在此p 秒內(nèi)每個(gè)源網(wǎng)站每秒鐘均向其相鄰網(wǎng)站傳遞信息（這樣才能保證傳播量相同時(shí)時(shí)間最短的要求），即每個(gè)結(jié)點(diǎn)應(yīng)有p 條邊，又兩個(gè)結(jié)點(diǎn)共用一條邊，所以f (2p , 2p ) =2p ?p /2=p 2p -1, (p =0, 1, ) 。

5.3關(guān)于問題三：

根據(jù)問題一的求法我們同樣可以得到當(dāng)k=5時(shí)的f(n, 5) 【詳細(xì)過程見附錄】

?n -1, 2p -1

p -3p ?n 2, 7*2

2m -1

下界的確定：當(dāng)源網(wǎng)站數(shù)目增加時(shí)，需要傳播的信息量增加，而在傳播的總網(wǎng)站數(shù)相等情況下，只有線路增加才能保證時(shí)間不變，所以f(n, k) ≤f(n,k 1)。所以f (n , k ) ≥f (n , k -1) ≥ ≥f (n , 6) ≥f (n , 5) =n -1。

上界的確定：所有的網(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)格遞增。所以能夠推出f (n , k ) ≤f (n , 2m ) ≤f (2p , 2m ) ，對(duì)于f (2p , 2m ) ，共有2m 個(gè)源信息，在m 秒內(nèi)，能夠有2m 個(gè)網(wǎng)站具有所有源網(wǎng)站的信息，剩下的網(wǎng)站只需在2p 個(gè)網(wǎng)站中任選2p -2m 個(gè)結(jié)點(diǎn)，對(duì)應(yīng)的增加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、 模型的優(yōu)點(diǎn)

首先該模型的假設(shè)對(duì)實(shí)際問題作了簡(jiǎn)化，并得出3個(gè)基本的結(jié)論 ，為問題的求解作好了準(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)系。

2、模型的缺點(diǎn)

在第（3）問中的解答沒有完整的理論體系，只是根據(jù)實(shí)際情況進(jìn)行假設(shè)，而沒有具體的理論支撐，沒有考慮其他的情況。

3、模型的改進(jìn)

因?yàn)樵葱畔⒌膫鞑タ煽醋鳂涞纳L(zhǎng)，因此還可以用樹圖來解釋邊數(shù)值。

六、 模型推廣

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

當(dāng)然，該模型是在對(duì)實(shí)際問題作了一些簡(jiǎn)化后得到的結(jié)果，而在實(shí)際網(wǎng)絡(luò)通信中也許不成立，如兩點(diǎn)間的通信應(yīng)受帶寬限制，不可能在一秒內(nèi)傳遞任意多的信息。所以模型的改進(jìn)空間還是很大的。

七、 參考文獻(xiàn)

[1]趙靜，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M]，高等教育出版社，2008

[2]譚永基等，數(shù)學(xué)模型，上海復(fù)旦大學(xué)出版社，1996

八、 附錄

k=5時(shí)，源網(wǎng)站的連接有以下多種可能：

情況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，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)站可以直接將所有信息傳播給另一個(gè)網(wǎng)站F, 第4秒將A 網(wǎng)站的信息1234傳給E 網(wǎng)站，信息5傳給D 網(wǎng)站，而B ，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)站都剩下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ù)為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時(shí)情況1的廣播圖

情況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)站含有信息125，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,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ù)為2P -3-1, 所以這種情況下，n=6 6*（2p -3-1）=6*2p -3，（f n,5）=6 n-6=n;

圖8 k=5時(shí)情況2的廣播圖

情況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)站含有信息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í)間將信息傳播給其他網(wǎng)站，故由A(B,C,D,E,F,G與A 相同）網(wǎng)站傳播出的網(wǎng)站數(shù)為2P -3-1, 所以這種情況下，n=7 7*（2p -3-1）=7*2p -3，f （n,5）=8 n-7=n 1;