Reachability Matrix: Difference between revisions

Reachability Matrix (view source)

75 bytes added , 9 January 2022

no edit summary

602

edits

@@ Line 1: / Line 1: @@
-In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex
+In graph theory, reachability refers to the ability to get from one vertex to another within a graph.
-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.
+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 transitive multi-level
+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.