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."
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:
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:
[R.C. Prim, Shortest connection networks and some generalizations, Bell System Technical Journal, vol. 36, 1er novembre 1957, p. 1389-1401]
Auteur : Hadrien Cambazard