Networks and Spanning Trees

Introduction

Left to right: Pioneers of graph theory Arthur Cayley, Heinz Prüfer, and Otakar Borůvka (Sources: Wikimedia Commons (Cayley and Prüfer), MacTutor History of Mathematics Archive (Borůvka))

In the 1889 publication, “A Theorem on Trees” [3], Arthur Cayley (1821–1895) discovered a pattern for the number of structures now called labeled trees. Although his proof in this paper is incomplete, the counting arguments leading to this pattern (today known as “Cayley’s formula”) allow the reader to make the same discovery. A rigorous proof of Cayley’s result can be gleaned from the work of Heinz Prüfer (1896–1934) [4, 5], although Prüfer phrased his counting arguments in terms of a rather applied problem without using the term “tree.” Prüfer wished to count all railway networks connecting n towns so that

1. the least number of railway segments was used; and
2. a person could travel from each town to any other town by some sequence of connected segments.

The conditions expressed here, that the least number of railway segments was to be used, yet travel would remain possible between any two towns, are recognized today as properties that characterize such a railway network as a (spanning) tree. Since the towns are fixed, their names (labels) are not interchangeable, and a labeled tree is an excellent model for this problem. Prüfer showed that there are nⁿ⁻² possible railway networks satisfying properties (1) and (2) above, a result that agrees with “Cayley’s formula.”

In 1926 Otakar Borůvka (1899–1995) published the solution to a problem of immediate benefit for constructing an electrical power network in the Southern Moravia Region, now part of the Czech Republic: Given n towns in a rural area, what spanning tree (or trees) has (or have) the least total edge length? Borůvka phrased the problem as follows [1]:

There are n points in the plane (in space) whose mutual distances are all different. We wish to join them by a net such that:

1. Any two points are joined either directly or by means of some other points.

2. The total length of the net is the shortest possible.

Borůvka offered a solution to this problem that is rather algorithmic in nature, and has become the basis for finding what today is called a minimal spanning tree. Both Prüfer and Borůvka wrote their seminal papers before graph theory was a separate subject of study, and many observations in these early works have become lemmas or theorems in graph theory.

The project Networks and Spanning Trees is ready for students, and the Latex source is also available for instructors who may wish to modify the project for students. The comprehensive “Notes to the Instructor” presented next are also appended to the project itself.

This primary source project module for students is part of a larger collection published in Convergence, and an entire introductory discrete mathematics course or combinatorics course can be taught from various combinations selected from these projects. For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Notes to the Instructor

The project is designed to motivate the modern definition of a “tree” found in textbooks covering graph theory, and then offer several applications of trees as well as one of the first algorithms for finding a minimal spanning tree. The term “tree” arises from the work of Arthur Cayley, whose enumeration of trees is discussed in short excerpts from “On the Theory of the Analytical Forms Called Trees” [2] and “A Theorem on Trees” [3]. This is contrasted with Heinz Prüfer’s counting of trees, although the word “tree” never appears in his work. Prüfer introduced the material via an applied problem, namely the counting of all possible railway networks satisfying certain properties. In hindsight, each of these networks represents a “labeled tree.” Finally an efficient algorithm for finding a minimal spanning tree is studied from the original work of Otakar Borůvka, who likewise discussed the problem without use of the term “tree.” Borůvka sought the most economical construction of an electrical power network across the rural region of Southern Moravia, now part of the Czech Republic. This problem can be understood today as finding the tree of shortest total edge length from all possible nⁿ⁻² labeled trees on n towns. The number nⁿ⁻² here agrees with “Cayley’s formula” for the number of labeled trees on n vertices. A prerequisite for the project is an introductory course in discrete mathematics covering such topics as induction and the concept of a one-to-one correspondence, needed for the Prüfer source. Also, Cayley’s first paper “On the Theory of the Analytical Forms Called Trees” [2] requires knowledge of partial derivatives, although this is not necessary for an understanding of “Cayley’s formula” found in the second paper “A Theorem on Trees” [3]. To cover the project in its entirety, allow about four weeks.

This curricular module requires no prior knowledge of graph theory. It is designed primarily for an advanced undergraduate course in combinatorics, graph theory or possibly algorithm design. The instructor may wish to cover the three main sections, highlighting source material from Cayley, Prüfer and Borůvka. Exercises from the Cayley source offer insight into the discovery of “Cayley’s formula,” while Prüfer’s work provides a clever and geometrically appealing proof of this formula. Finally, Borůvka’s algorithm offers a useful application of trees to solve a compelling problem in an efficient manner. For instructors seeking a hurried coverage of the project, study of Cayley’s first paper “On the Theory of the Analytical Forms Called Trees” [2] could be replaced with the simple statement that Cayley introduced the term “tree” in this paper. The work of Prüfer and Borůvka can be read independently of Cayley, although “Cayley’s formula” would appear without its historical origin, if the reading from the second paper “A Theorem on Trees” [3] is skipped. There are many exercises, some requiring simple recognition of a definition, and some requiring proofs of statements in the readings. The instructor is asked to work though the details of an exercise before assignment. Also, some knowledge of computer science is needed for exercises asking students to code a particular algorithm or exercises asking students to compare iteration with recursion. These may be omitted or further developed at the instructor’s discretion.

Download the project Networks and Spanning Trees as a pdf file ready for classroom use.

Download the modifiable Latex source for this project.

For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Bibliography

[1]  Borůvka, O., “Přisěvek k řešení otázky ekonomické stavby elektrovodních sítí” (“A Contribution to the Solution of a Problem on the Economical Construction of Power Networks”), Elecktronický obzor, 15 (1926), 153–154.

[2]  Cayley, A., “On the Theory of the Analytical Forms Called Trees,” Philosophical Magazine, 4, 13 (1857), 172–176.

[3]  Cayley, A., “A Theorem on Trees,” Quarterly Journal of Pure and Applied Mathematics, 23 (1889), 376–378.

[4]  Prüfer, H. “Neuer Beweis eines Satzes über Permutationen,” Archiv der Mathematik und Physik, 3, 27 (1918), 142–144.

[5]  Prüfer, H. “Neuer Beweis eines Satzes über Permutationen,” translation in Graph Theory 1736–1936, Biggs, N. L., Lloyd, E. K., Wilson, R. J. (editors), Clarendon Press, Oxford, 1976.

Acknowledgment



The development of curricular materials for discrete mathematics has been partially supported by the National Science Foundation's Course, Curriculum and Laboratory Improvement Program under grants DUE-0717752 and DUE-0715392 for which the authors are most appreciative. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.