From: Matthew Hubbard <leofosse@crl.com>
Subject: possible help for a graph theory problem from a few weeks ago
Date: Sat, 25 Dec 1999 09:24:05 -0800
Newsgroups: sci.math
Keywords: average distance of the paths of a tree

The question was to find the total distance (or possibly the average
distance) of the paths of a tree; in the case mentioned, the tree had
about 4,500 vertices.  In the computer, the tree is represented by an
adjacency matrix.

	One way to find the total distance (also called the Wiener Index) is to
find the roots of the characteristic polynomial of the LaPlacian matrix,
which is like the adjacency matrix but has the negative of the degree
sequence along the diagonal instead of zeros.
(Here is an example.)

    G	1 2 3		Laplacian Matrix
	o-o-o		-1  1  0  0
	  |		 1 -3  1  1
	4 o	   L(G)= 0  1 -1  0
			 0  1  0 -1

	When we take the determinant of Ix-L(G), we get a fourth degree
polynomial, the roots of which are {4,1,1,0}  The total distance W(G) is

			n(sum)1/(non zero roots)

	If the graph is connected, only the smallest root will be zero.  In
this particular case the answer would be 4(.25+1+1)=9.

	This algorithm may not be fast enough in large cases.  I have an idea
for a deconstruction algorithm that looks to be on the order of n^2 or
less, but I haven't double checked it.

MattH