An undirected graph with labelled edges
All the examples so far have been given via diagrams. This works well for human viewers and small graphs, but becomes unwieldy for larger graphs or for machine processing. There are several alternative ways to describe graphs. As an example, consider the graph whose diagram has vertices labelled a to e and edges labelled 1 to 6.
One way to describe this is with what’s called an incidence table, as shown below \[ \begin{array}{c|cccccc} & 1 & 2 & 3 & 4 & 5 & 6 \cr \hline a & 1 & 1 & 0 & 0 & 0 & 0 \cr b & 0 & 0 & 1 & 1 & 0 & 0 \cr c & 1 & 0 & 1 & 0 & 1 & 0 \cr d & 0 & 0 & 0 & 0 & 1 & 1 \cr e & 0 & 1 & 0 & 1 & 0 & 1 \end{array} \] There is a row for each vertex and a column for each edge. There is a 1 in the row corresponding to a vertex and the column corresponding to an edge if that vertex is an endpoint of that edge, and a 0 otherwise. If we remove the row and column labels then we get an incidence matrix: \[ \left [ \begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 \cr 0 & 0 & 1 & 1 & 0 & 0 \cr 1 & 0 & 1 & 0 & 1 & 0 \cr 0 & 0 & 0 & 0 & 1 & 1 \cr 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} \right ] \] There isn’t a particularly good analogue of this for directed graphs. Sometimes people use an incidence matrix with a \({ - 1 }\) entry for the initial endpoint and \({ 1 }\) for the final endpoint.
An alternative way to describe a graph is with an adjacency table. This has a row and a column for each vertex. There is a 1 in a row and column if the graph has an edge from the vertex corresponding to that row to the vertex corresponding to that column and a 0 otherwise. \[ \begin{array}{c|ccccc} & a & b & c & c & e \cr \hline a & 0 & 0 & 1 & 0 & 1 \cr b & 0 & 0 & 1 & 0 & 1 \cr c & 1 & 1 & 0 & 1 & 0 \cr d & 0 & 0 & 1 & 0 & 1 \cr e & 1 & 1 & 0 & 1 & 0 \end{array} \] Again, we can remove the labels to get a matrix, the adjacency matrix: \[ \left [ \begin{matrix} 0 & 0 & 1 & 0 & 1 \cr 0 & 0 & 1 & 0 & 1 \cr 1 & 1 & 0 & 1 & 0 \cr 0 & 0 & 1 & 0 & 1 \cr 1 & 1 & 0 & 1 & 0 \end{matrix} \right ] \] This is a symmetric matrix, reflecting the fact that our graph is undirected. It has 0’s along the main diagonal, reflecting the fact that the graph has no loops.
This representation works well in the case of graphs which are not undirected as well. For our earlier example of a directed graph, the one with substrings of the word mathematics, the adjacency matrix is \[ \setcounter{MaxMatrixCols}{11} \left [ \begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \end{matrix} \right ] \]
For each representation, we need an order relation to determine the order of the rows and columns. For the adjacency matrix we need an ordering of the vertices. For the incidence matrix we need that and an ordering of the edges. Different choice of order relation will require permuting the rows and columns of the matrices. In the particular case above I chose to order the strings first by length and then lexicographically within those of each possible length. A more traditional choice for ordering words would be just to use lexicographic ordering, but this would disguise an important property of our graph: the fact that it is possible to order the vertices in such a way that all edges go from vertices earlier in the order to vertices later in the ordering. Graphs with this property are called directed acyclic graphs. The come up in a variety of contexts. With such an ordering the adjacency matrix is lower triangular.
As often happens there differing conventions here. For directed graphs I’ve chosen to make the rows of the adjacency matrix correspond to initial endpoints of an edges and make the columns correspond to the terminal endpoints. Roughly half the world seems to use that convention and half uses the reverse convention. The effect of changing conventions is to transpose the matrices.