Reachability

Reachability

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

Definition

For a directed graph "D" = ("V", "A"), the reachability relation of "D" is its transitive closure, i.e. the set of all ordered pairs ("s", "t") of vertices in "V" for which there exist vertices "v"0 = "s", "v"1, …, "v"d = "t" such that ("v""i" - 1, "v""i" ) is in "A" for all 1 ≤ "i" ≤ "d".

See also

* "st"-connectivity
* Petri net


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • reachability — noun a) The condition of being reachable b) The extent to which a node in a graph is reachable from others …   Wiktionary

  • reachability — n. state of being reachable; attainability …   English contemporary dictionary

  • Maria (reachability analyzer) — Maria: The Modular Reachability Analyzer is a reachability analyzer for concurrent systems that uses Algebraic System Nets (a high level variant of Petri nets) as its modelling formalism. External links http://www.tcs.hut.fi/Software/maria/… …   Wikipedia

  • Subclass reachability — In Exact concept learning, given a class of concepts C, a subclass D is reachable if there exists a partial approximation S of some concept such that D contains exactly those concepts in C that are extensions to S (i.e., D=C|S).ee alsoExclusion… …   Wikipedia

  • OPTICS algorithm — OPTICS ( Ordering Points To Identify the Clustering Structure ) is an algorithm for finding density based clusters in spatial data. It was presented by Mihael Ankerst, Markus M. Breunig, Hans Peter Kriegel and Jörg Sander[1]. Its basic idea is… …   Wikipedia

  • Petri net — A Petri net (also known as a place/transition net or P/T net) is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions (i.e.… …   Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

  • SP-DEVS — abbreviating Schedule Preserving Discrete Event System Specification is a formalism for modeling and analyzing discrete event systems in both simulation and verification ways. SP DEVS also provides modular and hierarchical modeling features which …   Wikipedia

  • Border Gateway Protocol — BGP redirects here. For the Formula One Team, see Brawn GP. The Border Gateway Protocol (BGP) is the protocol backing the core routing decisions on the Internet. It maintains a table of IP networks or prefixes which designate network reachability …   Wikipedia

  • Finite & Deterministic Discrete Event System Specification — FD DEVS (Finite Deterministic Discrete Event System Specification) is a formalism for modeling and analyzing discrete event dynamic systems in both simulation and verification ways. FD DEVS also provides modular and hierarchical modeling features …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”