Reachability Matrix: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
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''. | 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 | 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 | 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. | ||
Latest revision as of 12:56, 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 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.