Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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:
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".
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".
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.
