4
$\begingroup$

What's the name for a DAG (directed acyclic graph) that has a unique root or source node from which every other node can be reached?

Alternatively, if you change the direction of the arrows, what's the name for a DAG that has some unique sink node that is reachable from every other node?

Here's an example graph:

example graph

$\endgroup$
5
$\begingroup$

There isn't a standard name for that, at least none I'm aware of. I've seen that structure being called "rooted DAG", by analogy with "rooted tree".

$\endgroup$
6
$\begingroup$

In a directed graph we do not speak of roots and leaves, but of sources and sinks.

I'm not aware of any term that designates a DAG with only a single source, but you could just call it that: "a DAG with a single source".

$\endgroup$
  • $\begingroup$ Thanks for the suggestion, and I've updated my question to say source and sink as well. $\endgroup$ – Jo Liss Dec 28 '16 at 14:57
3
$\begingroup$

If you think of the DAG as a graph whose reachability relation is a partial order relation, then an element with that property would be a minimum element in that relation.

I haven't seen the term "minimum element" used this way before, but I suspect that someone seeing that notation would likely be able to understand it if you included a quick explanatory sentence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.