4.八卦消息传播时间.doc

4、八卦消息传播时间一问题重述假如我们班有n个MM，每一个MM都有一个独家八卦消息。两个MM可以通过电话联系，一通电话将使得双方都获知到对方目前已知的全部消息。要想所有n个MM都知道所有n条八卦消息，最少需要多少通电话？请给出你们的通话方案。二假设1、每位MM对打电话都没有厌烦情绪，即多打、少打无所谓。三问题分析1、当n很小时我们很容易通过枚举的方法找出最佳通话方案：A1=0,A2=1,A3=3，A4=4，A5=6，A6=82、下面对于n比较大的情况做进一步分析：要想让n个MM共享所有n条八卦消息，最笨的方法莫过于每两个MM之间都通一次电话，这样共需要n*(n-1)/2通电话。但事实上完全没有必要这样做，因为在一次通话中如果通话双方所掌握的八卦消息不止一条，那么通话所交换的消息就会有多条，从而提高通话的效率、减少通话次数。解决这道题的关键所在就是如何设计通话方案，使得每次通话交换的信息量达到极大，使通话次数达到极小。四模型建立基于上面的想法，可以先把所有消息集中于一个或几个人，然后再由这些消息汇总人把消息传给所有人。设n个MM中有m个消息汇总人，她们共享所有消息需要打An通电话。通话方案如下：第一步，剩下的n-m个MM每人从m个消息汇总人中随机选择一个人通电话。这样一来m个消息汇总人就掌握了所有n条八卦消息，并且她们每人所掌握的消息互不重叠，是互补的。第二步，m个消息汇总人通过打电话共享所有八卦消息。第三步，作为消息汇总人的m个MM再通过电话将自己新得知的八卦新闻告知最开始打电话给自己的MM，使她们也掌握所有n条消息。通话示意图如下：非消息汇总人非消息汇总人非消息汇总人非消息汇总人DCBA消息汇总人汇总所有消息五模型求解与结果分析按照上面的通话方案，第一步需要n-m通电话，第二步需要Am通电话，第三步需要n-m通电话。故有An=2*（n-m）+Am，进一步化简得An=2*n-（2*m-Am）。即当MM的个数为n时，共享所有八卦消息共需要2*n-（2*m-Am）通电话。若要使通话次数最小，就要求2*m-Am最大。因此取多少个MM作为消息汇总人能使得2*m-Am最大就成为解决这个问题的关键，它反映了MM们之间通话的效率。记Em=2*m-Am。当有一个消息汇总人即m=1时，E1=2*1-A1=2;当有两个消息汇总人即m=2时，E2=2*2-A2=3； m=3时，E3=2*3-A3=3； m=4时，E4=2*4-A4=4； m=5时，E5=2*5-A5=4； m=6时，E6=2*6-A6=4； 由归纳法知当M=4时Em有最大值4、An有最小值2*n-4，即当有大于或等于4个消息汇总人时可通过上述通话方案使n个MM通过最少的电话数共享所有八卦消息。此时共需要2*n-4次通话。六进一步讨论下面我们证明，2n-4已经是最少的了。证明方法很多，也都很复杂。最常见的证明由Brenda Baker和Robert Shostak在1972年给出。 证明的关键在于这个引例：如果我们可以在2n-5次电话以内达到要求，则整个过程中绝对不会有人在电话中听到对方八卦自己的消息。我们将用反证法来证明这一点。首先找出最小的n使得n个人可以在2n-5次通话中传遍消息。如果某个人G听到了自己的消息，表明整个过程中存在这么一条通话线路：(G - G1)(G1 - G2).(Gr - G)。现在，我们把G这个人去掉，再重新安排一些通话线路，使得剩下的n-1个人同样能在2(n-1)-5次通话后传遍信息，从而与n的最小性矛盾。直接忽略上述“通话环”中的(G - G1)和(Gr - G)两条边。对于其他某个人P和G之间的通话(P-G)，找出(P-G)通电后最先出现的“通话环”中的其中一链（比如(Gi - Gi+1)）。在新方案中，让P把电话打给Gi。这样，原方案中任何一条由P1带给G再带给P2的消息，都由对应的Gi、Gj以及他们之间的链条来完成，即(P1 - Gi)(Gi - Gi+1) . (Gj - P2)。新方案与原方案一样满足要求，且通话次数减少了两次，同样小于等于2n-5。每个人都不会听到自己的消息，这可以推出一个很有趣的东西：记一通电话的双方为A和B，则要么A和B都还没打完，要么这通电话对双方来说都是最后一通。原因很简单，假如这通电话是A的最后一电，这表明A和B都知道了所有的消息，但B还要给别人打电话，别人就会听到自己的消息。类似地，一通电话的双方要么都是第一次打，要么都不是第一次打：假如A的第一通电话是跟B打的，但B之前已经和C通过话了，那A的消息将永远与C的消息一起传递，因此最终C听到A的消息时也会听到她自己的。于是，对于所有电话次数不超过2n-5的情况，n只能是偶数。并且情况只可能是这样：先两两配对拨打n/2通“处女电”，然后中间打很多“中介电话”，最后再两个两个地打n/2个“最后一电”。由于所有的“处女电”和“最后一电”加起来恰好有n通，那么“中介电话”最多只能有n-5通。又由于连通所有n个点至少要n-1条边，可知这些“中介电话”构成了至少5个连通分量。对于任何一个人来说，在任何“最后一电”拨打之前，她的消息最多只能够在其中两个连通分量内传递（她所在的连通分量和她“处女电”的对象所在的连通分量）；类似地，所有“处女电”都打完了后，每个人都只能收到两个连通分量内的消息（她自己的和“最后一电”的对象的）。对于一个特定的人G来说，除去她自己、“处女电”的对象和“最后一电”的对象所在的连通分量，至少还有两个连通分量，里面的所有“中介电话”对她没有任何意义：这些“中介电话”既不会把她的消息传出去，也不会把别人的消息带给她。设与G不相干的电话通数为c(G)。反过来，又有多少通电话与G有关呢？让我们继续把目光停留到G身上。要想把她的消息传给所有人，至少需要n-1通电话；要想让所有消息都传到她那里，同样也得要n-1通电话。某些电话可以同时起到这两种作用，但有一个前提条件：这些电话必需是她亲自打的。否则，她自己的消息将“捆绑”进那些将会传给她的消息里，从而与引理矛盾。假设她自己打了v(G)通电话，那么总共有2n-2-v(G)通电话负责传出她的消息并把别人的消息传给她。由2n-5 2n-2-v(G)+c(G)可知v(G) 3+c(