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