# Multitree

In combinatorics and order-theoretic mathematics, a **multitree** may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set that does not have four items *a*, *b*, *c*, and *d* forming a diamond suborder with *a* ≤ *b* ≤ *d* and *a* ≤ *c* ≤ *d* but with *b* and *c* incomparable to each other (also called a **diamond-free poset**^{[1]}).

## Contents

## Equivalence between directed acyclic graph and poset definitions

If *G* is a directed acyclic graph ("DAG") in which the nodes reachable from each vertex form a tree (or equivalently, if *G* is a directed graph in which there is at most one directed path between any two nodes, in either direction) then the reachability relation in *G* forms a diamond-free partial order. Conversely, if *P* is a diamond-free partial order, its transitive reduction forms a DAG in which the successors of any node form a tree.

## Diamond-free families

A diamond-free family of sets is a family *F* of sets whose inclusion ordering forms a diamond-free poset. If *D*(*n*) denotes the largest possible diamond-free family of subsets of an *n*-element set, then it is known that

and it is conjectured that the limit is 2.^{[1]}

## Applications

Multitrees may be used to represent multiple overlapping taxonomies over the same ground set.^{[2]} If a family tree may contain multiple marriages from one family to another, but does not contain marriages between any two blood relatives, then it forms a multitree.^{[3]} In the context of computational complexity theory, multitrees have also been called **strongly unambiguous graphs** or **mangroves**; they can be used to model nondeterministic algorithms in which there is at most one computational path connecting any two states.^{[4]}

## Related structures

A polytree, a directed acyclic graph formed by assigning an orientation to each edge of an undirected tree, may be viewed as a special case of a multitree.

The set of all nodes connected to any node *u* in a multitree forms an arborescence.

The word "multitree" has also been used to refer to a series-parallel partial order,^{[5]} or to other structures formed by combining multiple trees.

## References

- ↑
^{1.0}^{1.1}{{#invoke:citation/CS1|citation |CitationClass=citation }}. - ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=citation }}.