Maths(三)---Graphs and Trees(4)

Counting Walks of Length N

The adjacency matrix A(G) is

A={010}

{112}

{020}

Then  

A2={112}

{162}

{224}

Therefore,

one walk of length 2 connecting v1 to v1;

(v1e1v2e1v1)

one walk of length 2 connecting v1 to v2;

(v1e1v2e2v2)

two walks of length 2 connecting v1 to v3;

(v1e1v2e3v3, v1e1v2e4v3)

six walks of length 2 connecting v2 to v2;

(v2e1v1e1v2, v2e2v2e2v2, v2e3v3e3v2, v2e3v3e4v2, v2e4v3e4v2, v2e4v3e3v2)

two walks of length 2 connecting v2 to v3;

(v2e2v2e3v3, v2e2v2e4v3)

four walks of length 2 connecting v3 to v3.(v3e3v2e3v3, v3e3v2e4v3, v3e4v2e4v3, v3e4v2e3v3)

................................................................................

................................................................................