One idea, one story: Prim's Network for the capitals of the American states

R. C. Prim publishes his work entitled "Shortest Connection Networks And Some Generalizations" in 1957:

"A problem of inherent interest in the planning of large-scale communication, distribution and transportation networks also arises in connection with the current rate structure for Bell System leased-line services. It is the following:

Basic Problem - Given a set of (point) terminals, connect them by a network of direct terminal-to-terminal links having the smallest possible total length (sum of the link lengths). (A set of terminals is "connected" of course, if and only if there is an unbroken chain of links between every two terminals in the set.) An example of such a Shortest Connection Network is shown in Fig. 1."

Prim in america

Section IV of the paper is devoted to "Abstraction and Generalization". In this section, Prim explains that the problem is easier to state using the graph langage. Let us hear him:

"When the construction of shortest connection networks is thus reduced to processes involving only the numerical distance labels on the various possible links, the actual location of the points representing the various terminals in a graphical representation of the problem is, of course, inconsequential.
[...]
The original metric problem concerning a set of points in the plane has now been abstracted into a problem concerning labbelled graphs. The correspondence between the terminology employed thus far and more conventional language of Graph Theory is as follows:
terminal ↔ vertex
possible link ↔ edge
length of link ↔ "length" (or "weigth") of edge,
[...]"


[R.C. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal, vol. 36,‎ 1er novembre 1957, p. 1389-1401]

Auteur : Hadrien Cambazard

Last modified: Friday, 4 August 2017, 7:02 AM