Section 6.1 Graphs and Their Representations
493
The adjacency matrix in Practice 16 is symmetric, which will be true for the
adjacency matrix of any undirected graph—if there are p arcs between n i and n j ,
there are certainly p arcs between n j and n i . The symmetry of the matrix means
that only elements on or below the main diagonal need to be stored. Therefore, all
the information contained in the graph in Figure 6.25 is contained in the “lower
triangular” array shown, and the graph could be reconstructed from this array.
(The “upper triangular” version could also be used.)
1
1
0
1
0
1
0
0
2
0
In a directed graph, the adjacency matrix a reflects the direction of the arcs.
For a directed matrix,
a ij = p where there are p arcs from n i to n j
An adjacency matrix for a directed graph will not necessarily be symmetric,
because an arc from n i to n j does not imply an arc from n j to n i .
example 17
The adjacency matrix for the graph in Figure 6.25 with respect to the ordering
1, 2, 3, 4 is a 4 × 4 matrix. Entry 1,1 is a 1 due to the loop at node 1. All other
elements on the main diagonal are 0. Entry 2,1 (second row, first column) is a 1
because there is one arc between node 2 and node 1, which also means that entry
1, 2 is a 1.
3
2
1
4
Figure 6.25
So far we have
a = D
1
1 − −
1
0 − −
− − 0 −
− − − 0
T
praCTiCe 16 Complete the adjacency matrix for Figure 6.25.
■