Reachability Matrix: Difference between revisions
Jump to navigation
Jump to search
(Created page with "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) i...") |
No edit summary |
||
| Line 1: | Line 1: | ||
In graph theory, reachability refers to the ability to get from one vertex to another within a graph | In graph theory, reachability refers to the ability to get from one vertex to another within a graph. | ||
Usually there are several | 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. | |||
Revision as of 11:32, 9 January 2022
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 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.