八卦消息传播时间

1、4、八卦消息传播时间一. 问题重述假如我们班有 n 个 MM 每一个 MMf8 有一个独家八卦消息。两 个 MMI 以通过电话联系，一通电话将使得双方都获知到对方目前已 知的全部消息。要想所有 n 个 M 邮 8 知道所有 n 条八卦消息，最少需 要多少通电话？请给出你们的通话方案。二. 假设1、每位 MM 寸打电话都没有厌烦情绪，即多打、少打无所谓。三. 问题分析1、当 n 很小时我们很容易通过枚举的方法找出最佳通话方案：A1=0,A2=1,A3=3, A4=4, A5=6, A6=82、下面对于 n 比较大的情况做进一步分析：要想让 n 个 MMtt 享所有 n 条八卦消息，最笨的方法莫过

2、于每两个M 此间都通一次电话，这样共需要 n*(n-1)/2 通电话。但事实上完 全没有必要这样做，因为在一次通话中如果通话双方所掌握的八卦 消息不止一条，那么通话所交换的消息就会有多条，从而提高通话 的效率、减少通话次数。解决这道题的关键所在就是如何设计通话 方案，使得每次通话交换的信息量达到极大，使通话次数达到极小。四. 模型建立基于上面的想法，可以先把所有消息集中于一个或几个人，然后再 由这些消息汇总人把消息传给所有人。设 n 个 M 时有 m 个消息汇总 人，她们共享所有消息需要打 An 通电话。通话方案如下：第一步，剩下的 n-m 个 M 通人从 m 个消息汇总人中随机选择一个人 通

3、电话。这样一来 m 个消息汇总人就掌握了所有 n 条八卦消息，并 且她们每人所掌握的消息互不重叠，是互补的。第二步，m 个消息汇总人通过打电话共享所有八卦消息。第三步，作为消息汇总人的 m 个 M 俩通过电话将白己新得知的八卦 新闻告知最开始打电话给白己的 MM 使她们也掌握所有 n 条消息。通话示意图如下:五. 模型求解与结果分析 按照上面的通话方案，第一步需要 n-m 通电话，第二步需要 Am 通电 话，第三步需要 n-m 通电话。故有 An=2* (n-m) +Am 进一步化简得An=2*n- (2*m-An)即当 MM 勺个数为 n 时，共享所有八卦消息共需要 2*n- (2*m-An

4、) 通电话。若要使通话次数最小，就要求 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=4 寸 Em 有最大值 4、An 有最小值 2*n-4 ,即当有 大于或等于 4 个消息汇总人时可通过上述通话方案使n 个 MM!过最少的电话数共享所有八卦消息。此时共需要2*n-4 次通话。六. 进一步讨论下面我们证明，2n-4 已经是最少的了。证明方法很多，

5、也都很复杂。最常见的证明由 Brenda Baker 和 Robert Shostak 在 1972 年给出。证明的关键在于这个引例：如果我们可以在2n-5 次电话以内达到要求，贝 U 整个过程中绝对不会有人在电话中听到对方八卦白己的消 息。我们将用反证法来证明这一点。首先找出最小的n 使得 n 个人可以在 2n-5 次通话中传遍消息。如果某个人 G 听到了白己的消息， 表明整个过程中存在这么一条通话线路：(G - GI)(GI- G2).(Gr- G)。现在，我们把 G 这个人去掉，再重新安排一些通话线路，使得 剩下的 n-1 个人同样能在 2(n-1)-5 次通话后传遍信息，从而与 n 的

6、 最小性矛盾。直接忽略上述“通话环”中的(G - G1)和(Gr- G)两条 边。对于其他某个人 P 和 G 之间的通话(P-G)，找出(P-G)通电后最 先出现的“通话环”中的其中一链(比如 (Gi- Gi+i)。在新方案中, 让 P 把电话打给 G。这样，原方案中任何一条由 Pi带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;给 G 再带给 R 的消息，都由对应的 G、G 以及他们之间的链条来完成，即(Pi-G)(Gi- Gi+i) . (Gj- P2)。新方案与原方案一样满足要求，且通 话次数减少了

7、两次，同样小于等于 2n-5。每个人都不会听到白己的消息，这可以推出一个很有趣的东西： 记一通电话的双方为 A 和 B,则要么 A 和 B 都还没打完，要么这通 电话对双方来说都是最后一通。原因很简单，假如这通电话是A 的最后一电，这表明 A 和 B 都知道了所有的消息，但 B 还要给别人打 电话，别人就会听到白己的消息。类似地，一通电话的双方要么都 是第一次打，要么都不是第一次打：假如 A 的第一通电话是跟 B 打 的，但 B 之前已经和 C 通过话了，那 A 的消息将永远与 C 的消息一 起传递，因此最终 C 听到 A 的消息时也会听到她白己的。于是，对于所有电话次数不超过 2n-5 的情

8、况，n 只能是偶数。并 且情况只可能是这样：先两两配对拨打 n/2 通“处女电”，然后中 间打很多“中介电话”，最后再两个两个地打n/2 个“最后一电”。由于所有的“处女电”和“最后一电”加起来恰好有n 通，那么“中介电话”最多只能有 n-5 通。又由于连通所有 n 个点至少要 n- 1 条边，可知这些“中介电话”构成了至少 5 个连通分量。对于任 何一个人来说，在任何“最后一电”拨打之前，她的消息最多只能 够在其中两个连通分量内传递(她所在的连通分量和她“处女电” 的对象所在的连通分量)；类似地，所有“处女电”都打完了后， 每个人都只能收到两个连通分量内的消息(她白己的和“最后一电” 的对象

9、的)。对于一个特定的人 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(G