Next: Graph terminology
Let be a finite graph (directed or not).
We can associate a matrix , called the adjacency matrix of
to this graph, by letting be a 0-1 matrix
indexed by the vertex set of , where
if and only if there is an edge from to in .
The spectrum of the graph is by definition the spectrum
of the matrix .
This is certainly the right choice when is regular;
for not necessarily regular graphs the matrix with zero
row sums defined by
for is also
a useful tool. It is known as `the discrete Laplace operator'.
We want to connect graph properties to properties of the spectrum
of (or ).
First some graph terminology, linear algebra, and Perron-Frobenius theory.