第6組-最小廣播圖的設(shè)計-(編輯修改稿)
2025-07-26 16:30 本頁面
【文章內(nèi)容簡介】 )=1,f(3,1)=2,…f(n1,1)=n2,即網(wǎng)站數(shù)多一個時，任選一個網(wǎng)站并加一條邊即可，因此f(n,1)=f(n1,1)+1=n1。 ?。场? ２ １ ＋ ?。病 ?３ ?。场 。砶=2時，相當(dāng)于k=1的那一個源網(wǎng)站已經(jīng)傳播了一秒后廣播的傳播，所以在邊數(shù)上f(n,2)=f(n,1)=n1。也可以理解為在 + + 的基礎(chǔ)上每增加一個結(jié)點(diǎn)需加一條邊，所以f(n,2)=f(n1,1)+1=…=f(2,2)+n2=1+n2=n1。k=4時，源結(jié)點(diǎn)的連接有如下兩種可能： + 1 ①+ ②1 2 2 （1） ④3 ③ 2 （2）（1）中某個結(jié)點(diǎn)的信息可以在2秒內(nèi)傳至其他所有源結(jié)點(diǎn)（由圖中的標(biāo)號可知），所以四個源結(jié)點(diǎn)獲得四處信息均在2秒之后，則在剩下的p2秒內(nèi)每個源結(jié)點(diǎn)應(yīng)傳播個結(jié)點(diǎn)（當(dāng)然這些結(jié)點(diǎn)不包括另外三個源結(jié)點(diǎn)，因為它們在前2秒內(nèi)已經(jīng)傳完），產(chǎn)生1條邊。因此當(dāng)時，f(n, 4)= 4+4(1) =（第一個4表示連接源結(jié)點(diǎn)所需的邊數(shù)）。當(dāng)時，只需在上述廣播圖中減去相應(yīng)個數(shù)的最外圍的1結(jié)點(diǎn)即可得到邊數(shù)且f(n, 4)仍為n。那是不是對所有，f(n, 4)都等于n呢，我們來看第2種情形。（2）由該圖可知，對于一個①結(jié)點(diǎn)的信息來說，傳至②需一秒，傳至另兩個結(jié)點(diǎn)分別需2秒和3秒，
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1