Mathematics for Computer Science

9.3. Adjacency Matrices 323

As would be expected, this definition of distance satisfies:

Lemma 9.2.5.[The Triangle Inequality]

dist.u;v/dist.u;x/Cdist.x;v/

for all verticesu;v;xwith equality holding iffxis on a shortest path fromutov.

Of course, you might 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.

Proof of the “iff” is in Problem 9.3. 

Finally, the relationship between walks and paths extends to closed walks and

cycles:

Lemma 9.2.6.The shortest positive length closed walk through a vertex is a cycle

through that vertex.

The proof of Lemma 9.2.6 is essentially the same as for Theorem 9.2.3; see

Problem 9.7.

9.3 Adjacency Matrices

If a graph,G, hasnvertices,v 0 ;v 1 ;:::;vn 1 , a useful way to represent it is with

annnmatrix of zeroes and ones called itsadjacency matrix,AG. Theijth entry

of the adjacency matrix,.AG/ij, is 1 if there is an edge from vertexvito vertexvj

and 0 otherwise. That is,

.AG/ijWWD

(

1 if

̋

vi!vj

̨

2 E.G/;

0 otherwise: