graph distances, paths and other ideas …

The graph geodesics is a shortest path between two graph vertices of a graph. There may be more than one different shortest paths, all of the same length. Graph geodesics may be found using an existing famous algorithms such as: breadth-first traversal or Dijkstra’s algorithm.

The graph distance between two vertices denoted with is the length of the shortest, or minimal, path between them. (The notion of distance applies only to connected components of graphs see figure 1).

The graph diameter of a graph is the longest distance you can find in the graph. It is a measure of the length of the longest minimal path. (A path is not minimal if the two vertices at its endpoints could be connected by a shorter path). So the length of the maximum geodesic in a given graph is called the graph diameter, and the length of the minimum geodesic is called the graph radius.

The diameter of a graph stands the same way in Euclidean geometry (where the diameter of the circle is the largest distance inside a circle between any two points). Consider now the graph radius as the distance from the center to the outer edge. We can stretch and bend this concept into that of the radius of a graph.

The eccentricity of a vertex is the length of the longest minimal path from that vertex to some vertex in the graph. You can think of the eccentricity of a vertex as the longest distance in the graph from there to somewhere (see figure 2).

The graph center of a graph is the collection of vertices (called the central vertices) whose eccentricity is least. In other words, it’s the collection of vertices whose longest distance to all other vertices is the smallest.

The graph radius of a graph is the length of the shortest eccentricity in the graph. It’s the eccentricity of each central vertex.

Now the inspiration problem of the day is from an old russian graph theory problem that askes:

Problem: Given n points can one build n-1 roads, so that each road joins two points, the shortest distance between any two points along the roads belongs to {1, 2, 3, … , n(n-1)/2 }, and given any element of {1, 2, 3, … , n(n-1)/2 } one can find two points such that the shortest distance between them along the roads is that element? a) for n=6, b) for n=1986.

this is perhaps one of the coolest problems in graph theory I met so far. The problem states:

PROBLEM: There is a flu epidemic in elf city. The course of the disease is always the same. An elf is infected one day, he is sick the next, recovered and immune the third, recovered but not immune thereafter. Every day every elf who is not sick visits all his sick friends. If he is not immune he is sure to catch flu if he visits a sick elf. On day 1 no one is immune and one or more elves are infected from some external source. Thereafter there is no further external infection and the epidemic spreads as described above. Show that it is sure to die out (irrespective of the number of elves, the number of friends each has, and the number infected on day 1). Show that if one or more elves is immune on day 1, then it is possible for the epidemic to continue indefinitely. (All Russian Math Olympiad 1980)

As a first hint one shall think, what is really the difference of the following two graphs?

tree (no-cycle)

a cycle exists