Reachability

From Wikipedia, the free encyclopedia

In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex.

[edit] Definition

For a directed graph D = (V, A), the reachability relation of D is the set of all ordered pairs (s, t) of vertices in V for which there exist vertices v₀ = s, v₁, …, v_d = t such that (v_{i - 1}, v_i ) is in A for all 1 ≤ i ≤ d.

[edit] See also

• st-connectivity