Problem1H

Problem1H: A graph on the vertex set {\left\{ 1,2,\ldots ,n\right\} } is often descried by a matrix {A} of size {n,} where {a_{ij}} and {a_{ji}} are equal to the number of edges with ends {i} and {j}. What is the combinatorial interpretation of the entries of the matrix {A^{2}}?

Solution: Let {A^{2}=\left( b_{ij}\right) ,} then easy to see that { b_{ij}} means the number of walks of length {2} from vertex {i} to vertiex {j}.

Note: Let {A^{k}=\left( c_{ij}\right) ,} then {c_{ij}} means the number of walks of length {k} from {i} to {j}. The edge can be repeated, thus we use ‘walk’ instead of ‘path’. How can we find the number of paths of length {k} from vertex {i} to vertex {j}?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: