Chapter 2c


Centrality and the Berlin Rohrpost


Technical Terms:

acyclic, cycle, geodesic, graph, node, edge, tree, root, rooted tree, branch, branch weight, path, eccentricity, radius, central node, complete graph, center, branch weight, centroid, centroid node

Link to Chapter 2.


Trees

There is one simple and important kind of a graph, known widely as a tree. Trees are important not only for sake of their applications to many different fields, but also to graph theory itself. One reason for the latter is that the very simplicity of trees make it possible to investigate conjectures for graphs in general by first studying the situation for trees.

Image

Theorem 2c.1. Tree characterization theorem. The following statements are equivalent for a graph G with n nodes and m edges:

Proof:

1 implies 2

Since G is connected, a path joins every two nodes of G. Let P1 and P2 be two distinct paths joining u and v in G, and let w be the first node on P1 (traversing P1 from u to v) such that w is on both P1 and P2 but its successor on P1 is not on P2. If w' is the next node on P1 which is also on P2, the segments of P1 and P2 which are between w and w' together form a cycle in G. Thus if G is acyclic, there is at most one path joining any two nodes.

2 implies 3

Clearly G is connected. Prove that n = m + 1 by induction. It is obvious for connected graphs of one or two nodes. Assume it is true for graphs with fewer than n nodes. If G has n nodes, the removal of any edge of G disconnects G, because of the uniqueness of paths, and in fact, this new graph will have exactly two components. By the induction hypothesis, each component has one more node than edge. Thus, the total number of edges in G must be n - 1.

3 implies 4

Assume that G has a cycle of length t. Then there are t nodes and t edges on the cycle and for each of the n - t nodes not on the cycle, there is an incident edge on a geodesic to a node of the cycle. Each such edge is different, so mn, which is a contradiction.

4 implies 1

Since G is acyclic, each component of G is a tree. Thus, each component has one more node than it has edges. Thus, since n = m + 1, there can be only one component, so G is connected and hence a tree.

Under some circumstances, a particular node of a tree may be singled out as most important. It is called the root, and the resulting tree is called a rooted tree. For example, genealogical trees usually focus on distance from a particular couple who form the root of the tree. Organization charts are also usually rooted trees. The Rohrpost, too, is a tree with a root at the central office.

Centers and Centroids

Theorem 2c.2. Jordan/Sylvester Center Theorem (Jordan, of the Jordan Curve Theorem (Jordan, 1869).)  Every tree has a center consisting of either one node or two adjacent nodes.

Proof: The result is obvious for the trees K1 and K2 (complete graphs on one and two nodes). Any other tree T has the same central nodes as the tree T' obtained by removing all endnodes of T (shown below in Figure 2c.1). Clearly, the maximum of the distances from a given node u of T to any other node v of T will occur only when v is an endnode.

Thus, the eccentricity of each node in T' will be exactly one less than the eccentricity of the same node in T. Hence the nodes of T which possess minimum eccentricity in T are the same nodes having minimum eccentricity in T', that is, T and T' have the same center. If the process of removing endnodes is repeated, successive trees having the same center as T are obtained. Since T is finite, a tree that is either K1 or K2 is eventually reached. In either case, all nodes of this ultimate tree constitute the center of T that thus consists of just a single node or two adjacent nodes.

The animated image below illustrates the proof of the Jordan/Sylvester Theorem on the graph of the Rohrpost (for more information on the Rohrpost, itself, please return to Chapter 2). There are seven stages in this reduction to a central node: r(G)=7 and the eccentricity of the single central node is 7.

Image

Figure 2c.1. 

Jordan also proved a theorem on the centroid of a tree analogous to his result for centers.

Theorem 2c.3. Jordan Centroid Theorem. (Jordan, 1869.)  Every tree has a centroid consisting of either one node or two adjacent nodes.

Proof: The result is obvious for the trees K1 and K2 (complete graphs on one and two nodes). Any other tree T has the same centroid nodes as the tree T' obtained by removing all endnodes of T of maximum branch weight (shown below). Clearly, the maximum of the branch weight values from a given node u of T to any other node v of T will occur only when v is an endnode.

Thus, the branch weight of each node in T' will be less than the branch weight of the same node in T. Hence the nodes of T which possess minimum branch weight in T are the same nodes having minimum branch weight in T', that is, T and T' have the same centroid. If the process of removing endnodes of maximum branch weight is repeated, successive trees having the same centroid as T are obtained. Since T is finite, a tree that is either K1 or K2 is eventually reached. In either case, all nodes of this ultimate tree constitute the centroid of T that thus consists of just a single node or two adjacent nodes.

In this case, the periphery is diminished in size by removing, successively, all nodes of equal branch weight (as suggested in the animation of Figure 2c.2). (The heavy black line on one branch is reminiscent, perhaps, of a snow-covered weight on a tree branch.) First, in the graph of the Rohrpost, nodes of branch weight 65 are removed, then nodes of branch weight 64, and so forth. (See Chapter 2 for more information on the Rohrpost.)

Image

Figure 2c.2.