Mathematical name of this type of graph

90 Views Asked by At

If you have a tree that also might merge branches, but only in a directed way, i.e. all edges are one step either towards or away from the "root", what can we call it? It's a special case of a directed graph.

Version control systems with branches such as git have these graph structures. In git you have the forward/backward in time (with the epoch as the "root") with the possibility of branches being merged.

Example from the git page on wikipedia, 1 being the "root":
git-graph from the git-page on wikipedia
( https://commons.wikimedia.org/wiki/File:Revision_controlled_project_visualization-2010-24-02.svg )

1

There are 1 best solutions below

2
On BEST ANSWER

This is known as a directed acyclic graph. For this type of graph no path along the directed edges can meet itself again at another point, but different paths could possibly diverge and then merge again.

Section 3.5 in the same article linked above actually mentions version control systems.