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 |
||
| (2 intermediate revisions by the same user not shown) | |||
| 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|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 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. | |||
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.