Reachability Matrix

In graph theory, reachability refers to the ability to get from one vertex to another within a graph.

A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s and ends with t.

The Reachability Matrix can be derived from the Adjacency Matrix if the relation modeled is transitive and multilevel.

Usually, there are several Adjacency matrices that have the same Reachability Matrix. However, in forming a digraph from a Reachability Matrix, a valuable digraph uniqueness can be achieved by applying the criterion that the digraph have the minimum possible number of edges that maintains reachability,represented by entries of 1 in the Reachability Matrix.