Genealogy and version history Directed acyclic graph

family tree of ptolemaic dynasty, many marriages between close relatives causing pedigree collapse

family trees may seen directed acyclic graphs, vertex each family member , edge each parent-child relationship. despite name, these graphs not trees because of possibility of marriages between relatives (so child has common ancestor on both mother s , father s side) causing pedigree collapse. graphs of matrilineal descent ( mother relationships between women) , patrilineal descent ( father relationships between men) trees within graph. because no 1 can become own ancestor, family trees acyclic.

for same reason, version history of distributed revision control system has structure of directed acyclic graph, in there vertex each revision , edge connecting pairs of revisions directly derived each other. these not trees in general due merges.

in many randomized algorithms in computational geometry, algorithm maintains history dag representing version history of geometric structure on course of sequence of changes structure. instance in randomized incremental algorithm delaunay triangulation, triangulation changes replacing 1 triangle 3 smaller triangles when each point added, , flip operations replace pairs of triangles different pair of triangles. history dag algorithm has vertex each triangle constructed part of algorithm, , edges each triangle 2 or 3 other triangles replace it. structure allows point location queries answered efficiently: find location of query point q in delaunay triangulation, follow path in history dag, @ each step moving replacement triangle contains q. final triangle reached in path must delaunay triangle contains q.