A Problem with Telephones
A Problem with Telephones
复制标题
电话问题
DOI：
10.1137/0602002
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
R. Bumby
中科院分区：
文献类型：
--
作者：
R. Bumby
本文讨论的是“电话问题”，也称为“八卦问题”。假设n个人每人都有一条信息。他们两人可以通过打电话来分享他们所拥有的任何信息。问题来了，最少多少次通话才能让所有n个人获得全部n条信息。答案是 $2n - 4$。然后，人们可以询问这种最小调用集的属性。特别是，我们证明以调用为边的图必须包含四循环。
This paper deals with the “telephone problem,” also known as the “gossip problem”. Suppose n persons each have a piece of information. Pairs of them can share whatever information they possess by making a telephone call. The question arises, what minimum number of calls allows all n persons to obtain all n pieces of information. The answer is $2n - 4$. One can then ask about properties of such minimal sets of calls. In particular, we prove that the graph whose edges are the calls must contain a four-cycle.