Is there a name for a tree like graph, where nodes can have multiple parents, but still from only 1 level above

9
votes

Is there a name for a tree like graph, where nodes can have multiple parents, but still from only 1 level above.

Therefore the graph is directed and acyclic, but it has other constraints as well.

This will also mean that, all paths from any particular node back to the root are the same length.

1
graphtreeterminologydirected-acyclic-graphs
An aside - I think I can restate your extra rule as "all paths from any particular node back to the root are the same length". I'm not sure as I keep thinking "what if one node has a parent link that skips to a grandparent, but the grandparent has a parent link that links to a sibling?" but I'm fairly certain that's impossible. Given that the "level" of a node is (I assume) purely implicit in the structure, those relationships can't happen without violating the all-paths-same-distance-from-root rule for one node or another. – user180247
Thanks Steve. Also, why is their a close vote? – alan2here
Possibly off-topic. I upvoted because I'm curious, but just because a question is interesting doesn't mean it belongs here. Names of particular types of graphs may be a better fit on the mathematics stack exchange. – user180247

1 Answers

7
votes

I believe that this is called a layered graph. A graph of this sort is a graph where you can split the nodes into groups L1, L2, ..., Ln such that each edge (u, v) goes from some layer Li to a second layer Li+1.

Hope this helps!