The Communication Problem on Graphs and Digraphs.

摘要

The communication problem discussed in this article has been given various names in the literature, e.g. the 'gossip problem', and the 'telephone disease'. This is analogous to the well-known term 'the four color disease' which arose from the fact that the problem has so many features of an ailment. In the literature of psychology the 'common symbol problem' is equivalent to it, although in disguise. Recently, a probabilistic variation of the communication problem was studied in which the calls are made at random. In brief, the communication problem has as its setting the hypothesis that each of n individuals knows a unique item of information. The problem is what is the minimum number of communications between pairs of people needed to exchange all the information. It is assumed that these are two-way contacts such as a telephone conversation and that each individual can phone any other.