4八卦消息传播时间

　　一．问题重述 假如我们班有 n 个 MM，每一个 MM 都有一个独家八卦消息。两 个 MM 可以通过电话联系，一通电话将使得双方都获知到对方目前已 知的全部消息。要想所有 n 个 MM 都知道所有 n 条八卦消息，最少需 要多少通电话？请给出你们的通线、每位 MM 对打电话都没有厌烦情绪，即多打、少打无所谓。 三．问题分析 1、当 n 很小时我们很容易通过枚举的方法找出最佳通线、下面对于 n 比较大的情况做进一步分析： 要想让 n 个 MM 共享所有 n 条八卦消息，最笨的方法莫过于每两个 MM 之间都通一次电话，这样共需要 n*(n-1)/2 通电话。但事实上完 全没有必要这样做，因为在一次通话中如果通话双方所掌握的八卦 消息不止一条，那么通话所交换的消息就会有多条，从而提高通话 的效率、减少通话次数。解决这道题的关键所在就是如何设计通话 方案，使得每次通话交换的信息量达到极大，使通话次数达到极小。 四．模型建立 基于上面的想法，可以先把所有消息集中于一个或几个人，然后再 由这些消息汇总人把消息传给所有人。设 n 个 MM 中有 m 个消息汇总 人，她们共享所有消息需要打 An 通电话。 通话方案如下： 第一步，剩下的 n-m 个 MM 每人从 m 个消息汇总人中随机选择一个人 通电话。这样一来 m 个消息汇总人就掌握了所有 n 条八卦消息，并 且她们每人所掌握的消息互不重叠，是互补的。 第二步，m 个消息汇总人通过打电话共享所有八卦消息。 第三步，作为消息汇总人的 m 个 MM 再通过电话将自己新得知的八卦 新闻告知最开始打电话给自己的 MM，使她们也掌握所有 n 条消息。
　　五．模型求解与结果分析 按照上面的通话方案，第一步需要 n-m 通电话，第二步需要 Am 通电 话，第三步需要 n-m 通电线*（n-m）+Am，进一步化简得 An=2*n-（2*m-Am）。 即当 MM 的个数为 n 时，共享所有八卦消息共需要 2*n-（2*m-Am） 通电话。若要使通线*m-Am 最大。因此取多少个 MM 作为消息汇总人能使得 2*m-Am 最大就成为解决这个问题的关键， 它反映了 MM 们之间通线*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 听到了自己的消息， 表明整个过程中存在这么一条通线)...(Gr G)。现在，我们把 G 这个人去掉，再重新安排一些通话线路，使得 剩下的 n-1 个人同样能在 2(n-1)-5 次通话后传遍信息，从而与 n 的
　　最小性矛盾。直接忽略上述“通线)和(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 的消息时也会听到她自己的。 于是，对于所有电线 的情况，n 只能是偶数。并 且情况只可能是这样：先两两配对拨打 n/2 通“电”，然后中 间打很多“中介电话”，最后再两个两个地打 n/2 个“最后一电”。 由于所有的“电”和“最后一电”加起来恰好有 n 通，那么 “中介电线 通。又由于连通所有 n 个点至少要 n1 条边，可知这些“中介电线 个连通分量。对于任 何一个人来说，在任何“最后一电”拨打之前，她的消息最多只能 够在其中两个连通分量内传递（她所在的连通分量和她“电” 的对象所在的连通分量）；类似地，所有“电”都打完了后， 每个人都只能收到两个连通分量内的消息（她自己的和“最后一电” 的对象的）。对于一个特定的人 G 来说，除去她自己、“电” 的对象和“最后一电”的对象所在的连通分量，至少还有两个连通 分量，里面的所有“中介电话”对她没有任何意义：这些“中介电 话”既不会把她的消息传出去，也不会把别人的消息带给她。设与 G 不相干的电话通数为 c(G)。 反过来，又有多少通电话与 G 有关呢？让我们继续把目光停留到 G 身上。要想把她的消息传给所有人，至少需要 n-1 通电话；要想 让所有消息都传到她那里，同样也得要 n-1 通电话。某些电话可以 同时起到这两种作用，但有一个前提条件：这些电话必需是她亲自 打的。否则，她自己的消息将“”进那些将会传给她的消息里， 从而与引理矛盾。假设她自己打了 v(G)通电线v(G)通电话负责传出她的消息并把别人的消息传给她。由 2n-5 ≥
　　2n-2-v(G)+c(G)可知 v(G) ≥ 3+c(G) ≥ 3。既然每个人都打了至 少 3 次电话，这表明每个人都打过“中介电话”，直接推出每个连 通分量都有至少一条边。前面说了，c(G)包含了至少两个连通分量 中的所有边，因此 c(G)≥2。因此，v(G)≥5。每个人都打了至少 5 次电话？这当然是不可能的，这将导致总的电线n 还大了。