9.3. Adjacency Matrices 239
Of course you may expect this property to be true, but distance has a technical
definition and its properties can’t be taken for granted. For example, unlike ordinary
distance in space, the distance fromutovis typically different from the distance
fromvtou. So let’s prove the Triangle Inequality:
Proof. To prove the inequality, supposefis a shortest path fromutoxandr
is a shortest path fromxtov. Then by Lemma 9.2.2,fbxris a walk of length
dist.u;x/Cdist.x;v/fromutov, so this sum is an upper bound on the length of
the shortest path fromutovby Theorem 9.2.3.
To prove the “iff” from left to right, suppose dist.u;v/Ddist.u;x/Cdist.x;v/.
Then merging a shortest path fromutoxwith shortest path fromxtovyields a
walk whose length is dist.u;x/Cdist.x;v/which by assumption equals dist.u;v/.
This walk must be a path or it could be shortened, giving a smaller distance fromu
tov. So this is a shortest path containingx.
To prove the “iff” from right to left, suppose vertexxis on a shortest pathw
fromutov, namely,wis a shortest path of the formfbxr. The pathfmust be a
shortest path fromutox; otherwise replacingfby a shorter path fromutoxwould
yield a shorter path fromutovthanw. Likewisermust be a shortest path fromx
tov. So dist.u;v/DjwjDjfjCjrjDdist.u;x/Cdist.x;v/.
9.3 Adjacency Matrices
If a graph,G, hasnvertices,v 0 ;v 1 ;:::;vn 1 , a useful way to represent it is with
annmatrix of zeroes and ones called itsadjacency matrix,AG. Theijth entry,
.AG/ij, of the adjacency matrix is 1 if there is an edge from vertexvito vertexvj,
and 0 otherwise. That is,
.AG/ijWWD
(
1 if
̋
vi!vj
̨
2 V.G/;
0 otherwise:
cleFor example, letH be the 4-node the graph shown in Figure 9.1. Then its
adjacency matrixAHis the 4 4 matrix:
AHD
a b c d
a 0 1 0 1
b 0 0 1 1
c 0 1 0 0
d 0 0 1 0
