= Descendant in a directed graph
A vertex $v$ is a descendant of $u$ in a <directed graph> when a directed path leads from $u$ to $v$. Under the reflexive convention, a length-zero path makes $u$ its own descendant; a strict-descendant convention excludes that case and must be stated. An ancestor reverses this reachability relation.
For $a\to b\to c$, the descendants of $a$ are $a,b,c$ under the reflexive convention, while $a$ is not a descendant of $c$. In a directed cycle, distinct vertices can each be descendants of the other. Thus descendant reachability is transitive and reflexive but need not be antisymmetric.
In a <directed acyclic graph>, mutual reachability forces equality, so reachability defines a <partial order>. This makes descendant sets useful in dependency and causal graphs, while the graph alone still needs a specified interpretation before an arrow denotes causation.
Back to article page
