An adjacency matrix is a compact way to represent the structure of a finite graph. If a graph has vertices, its adjacency matrix is an matrix, where each entry represents the number of edges from one vertex to another.
Some properties and computations in graph theory can be carried out efficiently and elegantly by using a graph's adjacency matrix. Moreover, certain questions about properties of the adjacency matrix correspond to interesting questions about the associated graph.
Given a graph with vertices, the adjacency matrix is an matrix where the value equals the number of edges from the vertex to the vertex If the graph is undirected, then for all that is, the adjacency matrix is symmetric.
When the graph is simple, the entries of the adjacency matrix are all or (there are no weights on the edges, or multiple edges) and the diagonal entries are all (there are no loops). More complicated types of graphs give rise to more kinds of matrices.
Create an adjacency matrix for the following weighted, undirected graph:
The weights on the edges go into the entries of the adjacency matrix, as follows:
This example suggests some follow-up questions, which will be addressed in a later section:
- Note that if the vertices were labeled differently, the adjacency matrix would change.
- How would it change, and how would the new adjacency matrix be related to the old one?
- Can this relationship be expressed in matrix language?
The adjacency matrix is an array of numbers that represents all the information about the graph. Some of the properties of the graph correspond to interesting properties of its adjacency matrix, and vice versa. Here is a simple example:
Let be a simple graph with vertices and edges: that is, is undirected, unweighted, and has no loops (edges from a vertex to itself).
Let be the adjacency matrix of and let be the matrix whose entries are all equal to Then is a matrix . What is ?
Notation: if is a matrix, denotes its transpose.
Powers: One of the most well-known ways to get information about the graph from operations on the adjacency matrix is via its powers. As the following example shows, the entries of the powers of the adjacency matrix give information about paths in the graph.
Let be the adjacency matrix of a simple graph with vertices. Suppose the entry of in the row and the column is What does this mean about the graph?
Suppose Then the entry of is
Consider This counts the number of paths from vertex 3 to 1, multiplied by the number of paths from vertex 1 to vertex 4. This is exactly the number of two-step paths from vertex 3 to vertex 4 which pass through vertex 1. The other terms count the number of two-step paths from vertex 3 to vertex 4 which pass through vertex So the sum counts all of the two-step paths from vertex 3 to vertex 4. The conclusion is that there are two-step paths from vertex 3 to vertex 4.
So the entries of count two-step walks from to This generalizes as follows:
Let be the adjacency matrix of a graph. The entry of counts -step walks from vertex to vertex
The proof is a straightforward induction on where the argument is essentially the same as the one given above for
Spectrum: The study of the eigenvalues of the adjacency matrix of a graph is called spectral graph theory. Here is a simple example of a correspondence between graph properties and eigenvectors of the adjacency matrix:
An undirected graph is -regular if the degree of each vertex is What can be said about the eigenvalues and eigenvectors of the adjacency matrix of a -regular graph?
Let be the adjacency matrix of a -regular graph. Let be the all-ones column vector in Then the entry of equals the sum of the entries in the row of This is the number of edges emanating from vertex which is exactly So i.e. is an eigenvector of with eigenvalue
Isomorphisms: Two graphs are said to be isomorphic if one can be obtained from the other by relabeling vertices. Note that isomorphic graphs need not have the same adjacency matrix, since the adjacency matrix depends on the labeling of the vertices. But the adjacency matrices of isomorphic graphs are very closely related.
Let and be graphs on vertices with adjacency matrices and Then and are isomorphic if and only if there is a permutation matrix such that
Recall that a permutation matrix is a square matrix whose entries are all or such that each row and each column contains exactly one