Reachability Matrix

In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s s can reach a vertex t t (and t t is reachable from s s) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s s and ends with t t.

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.