635
edits
no edit summary
No edit summary |
No edit summary |
||
| (One intermediate revision 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. | ||
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 | 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. | ||