Suppose you have a non-directed graph, represented through its adjacency matrix. How would you discover how many paths of length link any two nodes?
For example, in the graph aside there is one path of length 2 that links nodes A and B (A-D-B). How can this be discovered from its adjacency matrix?
It turns out there is a beautiful mathematical way of obtaining this information! Although this is not the way it is used in practice, it is still very nice. In fact, Breadth First Search is used to find paths of any length given a starting node.
PROP. holds the number of paths of length
from node
to node
.
Let’s see how this proposition works. Consider the adjacency matrix of the graph above:
With we should find paths of length 2. So we first need to square the adjacency matrix: