# Multitree

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Multitree
> Markdown URL: https://mediated.wiki/source/Multitree.md
> Source: https://en.wikipedia.org/wiki/Multitree
> Source revision: 1323981624
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Type of graph in mathematics

Not to be confused with [MultiTree](/source/MultiTree).

The [butterfly network](/source/Butterfly_network), a multitree used in distributed computation, showing in red the undirected tree induced by the subgraph reachable from one of its vertices.

In [combinatorics](/source/Combinatorics) and [order theory](/source/Order_theory), a **multitree** may describe either of two equivalent structures: a [directed acyclic graph](/source/Directed_acyclic_graph) (DAG) in which there is at most one directed path between any two [vertices](/source/Vertex_(graph_theory)), or equivalently in which the [subgraph](/source/Glossary_of_graph_theory#subgraph) reachable from any vertex induces an [undirected tree](/source/Tree_(graph_theory)), or a [partially ordered set](/source/Partially_ordered_set) (poset) 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]).

In [computational complexity theory](/source/Computational_complexity_theory), multitrees have also been called **strongly unambiguous graphs** or **mangroves**; they can be used to model [nondeterministic algorithms](/source/Nondeterministic_algorithm) in which there is at most one computational path connecting any two states.[2]

Multitrees may be used to represent multiple overlapping [taxonomies](/source/Taxonomy_(general)) over the same ground set.[3] If a [family tree](/source/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.[4]

## Equivalence between DAG and poset definitions

In a directed acyclic graph, if there is at most one directed path between any two vertices, or equivalently if the subgraph reachable from any vertex induces an undirected tree, then its [reachability](/source/Reachability) relation is a diamond-free partial order. Conversely, in a diamond-free partial order, the [transitive reduction](/source/Transitive_reduction) identifies a directed acyclic graph in which the subgraph reachable from any vertex induces an undirected tree.

## Diamond-free families

A diamond-free [family of sets](/source/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

- 2 ≤ lim n → ∞ D ( n ) / ( n ⌊ n / 2 ⌋ ) ≤ 2 3 11 {\displaystyle 2\leq \lim _{n\to \infty }D(n){\Big /}{\binom {n}{\lfloor n/2\rfloor }}\leq 2{\frac {3}{11}}} ,

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

## Related structures

A [polytree](/source/Polytree), a directed acyclic graph formed by [orienting](/source/Orientation_(graph_theory)) the edges of an undirected tree, is a special case of a multitree.

The subgraph reachable from any vertex in a multitree is an [arborescence](/source/Arborescence_(graph_theory)) rooted in the vertex, that is a polytree in which all edges are oriented away from the root.

The word "multitree" has also been used to refer to a [series–parallel partial order](/source/Series%E2%80%93parallel_partial_order),[5] or to other structures formed by combining multiple trees.

## References

1. ^ [***a***](#cite_ref-gll_1-0) [***b***](#cite_ref-gll_1-1) Griggs, Jerrold R.; Li, Wei-Tian; Lu, Linyuan (2010), *Diamond-free families*, [arXiv](/source/ArXiv_(identifier)):[1010.5311](https://arxiv.org/abs/1010.5311), [Bibcode](/source/Bibcode_(identifier)):[2010arXiv1010.5311G](https://ui.adsabs.harvard.edu/abs/2010arXiv1010.5311G).

1. **[^](#cite_ref-2)** [Allender, Eric](/source/Eric_Allender); Lange, Klaus-Jörn (1996), "StUSPACE(log *n*) ⊆ DSPACE(log2 *n*/log log *n*)", *Algorithms and Computation, 7th International Symposium, ISAAC '96, Osaka, Japan, December 16–18, 1996, Proceedings*, Lecture Notes in Computer Science, vol. 1178, Springer-Verlag, pp. 193–202, [doi](/source/Doi_(identifier)):[10.1007/BFb0009495](https://doi.org/10.1007%2FBFb0009495), [ISBN](/source/ISBN_(identifier)) [978-3-540-62048-8](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-62048-8).

1. **[^](#cite_ref-3)** [Furnas, George W.](/source/George_Furnas); Zacks, Jeff (1994), "Multitrees: enriching and reusing hierarchical structure", *Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)*, pp. 330–336, [doi](/source/Doi_(identifier)):[10.1145/191666.191778](https://doi.org/10.1145%2F191666.191778), [S2CID](/source/S2CID_(identifier)) [18710118](https://api.semanticscholar.org/CorpusID:18710118).

1. **[^](#cite_ref-4)** McGuffin, Michael J.; Balakrishnan, Ravin (2005), "Interactive visualization of genealogical graphs", *IEEE Symposium on Information Visualization*, Los Alamitos, California, US: IEEE Computer Society, p. 3, [doi](/source/Doi_(identifier)):[10.1109/INFOVIS.2005.22](https://doi.org/10.1109%2FINFOVIS.2005.22), [ISBN](/source/ISBN_(identifier)) [0-7803-9464-X](https://en.wikipedia.org/wiki/Special:BookSources/0-7803-9464-X), [S2CID](/source/S2CID_(identifier)) [15449409](https://api.semanticscholar.org/CorpusID:15449409).

1. **[^](#cite_ref-5)** Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", *Journal of Combinatorial Theory, Series B*, **24** (2): 125–133, [doi](/source/Doi_(identifier)):[10.1016/0095-8956(78)90013-8](https://doi.org/10.1016%2F0095-8956%2878%2990013-8), [MR](/source/MR_(identifier)) [0491356](https://mathscinet.ams.org/mathscinet-getitem?mr=0491356).

---
Adapted from the Wikipedia article [Multitree](https://en.wikipedia.org/wiki/Multitree) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Multitree?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.