Small Diameters

Graphs in the real world tend to have small diameters. The diameter of a graph is the longest or shortest path across it depending on one's definition, or in other words, the length or the number of vertices traversed during the most direct route between its most distant vertices. In a closed circulation, blood follows the same circuit, but in a hemocoel routes may be direct or longer.

Only connected graphs have finite diameters. A connected graph is all in one piece, and it must have at least n — 1 edges so its largest possible diameter is n — 1. At the opposite extreme, a complete graph, having n2/2 edges, has a diameter of 1, because one can pass from any vertex to any other traversing a single edge. Graphs having edges closer to the minimum than the maximum number may be of large diameter. Clustering could increase the diameter even more, because edges used up to make local clumps leave fewer edges available for connections spanning longer distances as occurs with regulated airline routes. In a hub-and-spoke system, travel to many cities is not over the shortest distances because stopovers involve hub cities. Nevertheless, the diameter of the World Wide Web and other large graphs appears to hover about the logarithm of n, which is much smaller than n itself.

0 0