On graphs the labels move from vertex to adjacent vertex, step by step, along edges. A walk is a sequence x, y, z, ... w of vertices where any two consecutive vertices are adjacent. Its length is the number of edges travelled, one less than the number of vertices of the walk. If no vertex occurs repeatedly, the walk is called a path. The distance d(x,y) between two vertices in a graph is the smallest length of a path (or walk).
 |
In the example (where A, ... F denote the vertices, not the animals), the distances are given in the matrix to the right. |
|
A graph is connected if there is some path between every pair of vertices. For a connected graph, the average distance is the average of the distances occuring in the matrix of all distances. In our example, the average distance is 11/9, about 1.22. For the graph of the 15 Puzzle the average distance is 2.5 (please check both claims!).