4.八卦消息傳播時間

1、4、八卦消息傳播時間一問題重述假如我們班有個，每一個都有一個獨家八卦消息。兩個可以通過電話聯(lián)系，一通電話將使得雙方都獲知到對方目前已知的全部消息。要想所有個都知道所有條八卦消息，最少需要多少通電話？請給出你們的通話方案。二假設(shè)1、每位，對打電話都沒有厭煩情緒，即多打、少打無所謂。三問題分析1當(dāng)很小時我們很容易通過枚舉的方法找出最佳通話方案：2下面對于比較大的情況做進一步分析：要想讓個共享所有條八卦消息，最笨的方法莫過于每兩個之間都通一次電話，這樣共需要通電話。但事實上完全沒有必要這樣做，因為在一次通話中如果通話雙方所掌握的八卦消息不止一條，那么通話所交換的消息就會有多條，從而提高通話的效率、減

2、少通話次數(shù)。解決這道題的關(guān)鍵所在就是如何設(shè)計通話方案，使得每次通話交換的信息量達到極大，使通話次數(shù)達到極小四.模型建立基于上面的想法，可以先把所有消息集中于一個或幾個人，然后再由這些消息匯總?cè)税严鹘o所有人。設(shè)個中有個消息匯總?cè)?，她們共享所有消息需要打通電話。通話方案如下：第一步，剩下的個每人從個消息匯總?cè)酥须S機選擇一個人通電話。這樣一來個消息匯總?cè)司驼莆樟怂袟l八卦消息，并且她們每人所掌握的消息互不重疊，是互補的。第二步，個消息匯總?cè)送ㄟ^打電話共享所有八卦消息。第三步，作為消息匯總?cè)说膫€再通過電話將自己新得知的八卦新聞告知最開始打電話給自己的，使她們也掌握所有條消息。通話示意圖如下：五模型

3、求解與結(jié)果分析按照上面的通話方案，第一步需要通電話，第二步需要通電話，第三步需要通電話。故有（），進一步化簡得即當(dāng)?shù)膫€數(shù)為時，共享所有八卦消息共需要（）通電話。若要使通話次數(shù)最小，就要求最大。因此取多少個作為消息匯總?cè)四苁沟米畲缶统蔀榻鉀Q這個問題的關(guān)鍵,它反映了M們之間通話的效率。記*當(dāng)有一個消息匯總?cè)思磿r，當(dāng)有兩個消息匯總?cè)思磿r，2時，3時，4時，5時，6由歸納法知當(dāng)時有最大值、有最小值，即當(dāng)有大于或等于個消息匯總?cè)藭r可通過上述通話方案使個通過最少的電話數(shù)共享所有八卦消息。此時共需要次通話。六.進一步討論下面我們證明，2，-已4經(jīng)是最少的了。證明方法很多，也都很復(fù)雜最常見的證明由和在年給出。

4、，證，明的關(guān)鍵在于這個引例：如果我們可以在2，-次5電話以內(nèi)達到要求，則整個過程中絕對不會有人在電話中聽到對方八卦自己的消息。我們將用反證法來證明這一點。首先找出最小的，使得，個人可以在次通話中傳遍消息。如果某個人聽到了自己的消息，表明整個過程中存在這么一條通話線路：?，F(xiàn)在，我們把這個人去掉，再重新安排一些通話線路，使得剩下的，-個1人同樣能在2（，-1次通-話5后傳遍信息，從而與，的最小性矛盾。直接忽略上述“通話環(huán)”中的和兩條邊。對于其他某個人和之間的通話-找出通電后最先出現(xiàn)的“通話環(huán)”中的其中一鏈（比如）。在新方案中，讓把電話打給。這樣，原方案中任何一條由帶給再帶給的消息，都由對應(yīng)的、以及

5、他們之間的鏈條來完成，即）新方案與原方案一樣滿足要求，且通話次數(shù)減少了兩次，同樣小于等于-5每個人都不會聽到自己的消息，這可以推出一個很有趣的東西：記一通電話的雙方為和，則要么和都還沒打完，要么這通電話對雙方來說都是最后一通。原因很簡單，假如這通電話是的最后一電，這表明和都知道了所有的消息，但還要給別人打電話，別人就會聽到自己的消息。類似地，一通電話的雙方要么都是第一次打，要么都不是第一次打：假如的第一通電話是跟打的，但之前已經(jīng)和通過話了，那的消息將永遠與的消息一起傳遞，因此最終聽到的消息時也會聽到她自己的。于是，對于所有電話次數(shù)不超過的5青況，只能是偶數(shù)。并且情況只可能是這樣：先兩兩配對撥打

6、通“處女電”，然后中間打很多“中介電話”，最后再兩個兩個地打個“最后一電”。由于所有的“處女電”和“最后一電”加起來恰好有通,那么“中介電話”最多只能有通。又由于連通所有個點至少要1條邊，可知這些“中介電話”構(gòu)成了至少5個連通分量。對于任何一個人來說，在任何“最后一電”撥打之前，她的消息最多只能夠在其中兩個連通分量內(nèi)傳遞（她所在的連通分量和她“處女電”的對象所在的連通分量）；類似地，所有“處女電”都打完了后，每個人都只能收到兩個連通分量內(nèi)的消息（她自己的和“最后一電”的對象的）。對于一個特定的人來說，除去她自己、“處女電”的對象和“最后一電”的對象所在的連通分量，至少還有兩個連通分量，里面的所有“中介電話”對她沒有任何意義：這些“中介電話”既不會把她的消息傳出去，也不會把別人的消息帶給她。設(shè)與不相干的電話通數(shù)為。反過來，又有多少通電話與有關(guān)呢？讓我們繼續(xù)把目光停留到身上。要想把她的消息傳給所有人，至少需要通電話；要想讓所有消息都傳到她那里，同樣也得要通電話。某些電話可以同時起到這兩種作用，但有一個前提條件：這些電話必需是她親自打的。否則，她自己的消息將“捆綁”進那些將會傳給她的消息里，從而與引理矛盾。假設(shè)她自己打了通電話，那么總共有通電話負責(zé)傳出她的消息并把別人的消息傳給她。由5三22v(G)+c可知v(G)三3+c(G)三3。既然每個人都打了至少3次電話，這表明每個人都