{{Short description|Type of graph in mathematics}} {{distinguish|MultiTree}} [[File:Butterfly multitree.svg|thumb|300px|The [[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]] and [[order theory]], a '''multitree''' may describe either of two equivalent structures: a [[directed acyclic graph]] (DAG) in which there is at most one directed path between any two [[Vertex (graph theory)|vertices]], or equivalently in which the [[Glossary of graph theory#subgraph|subgraph]] reachable from any vertex induces an [[Tree (graph theory)|undirected tree]], or a [[partially ordered set]] (poset) that does not have four items {{mvar|a}}, {{mvar|b}}, {{mvar|c}}, and {{mvar|d}} forming a diamond suborder with {{math|''a'' ≤ ''b'' ≤ ''d''}} and {{math|''a'' ≤ ''c'' ≤ ''d''}} but with {{mvar|b}} and {{mvar|c}} incomparable to each other (also called a '''diamond-free poset'''<ref name="gll">{{citation | last1 = Griggs | first1 = Jerrold R. | last2 = Li | first2 = Wei-Tian | last3 = Lu | first3 = Linyuan | title = Diamond-free families | year = 2010 | arxiv = 1010.5311| bibcode = 2010arXiv1010.5311G}}.</ref>).
In [[computational complexity theory]], multitrees have also been called '''strongly unambiguous graphs''' or '''mangroves'''; they can be used to model [[nondeterministic algorithm]]s in which there is at most one computational path connecting any two states.<ref>{{citation | last1 = Allender | first1 = Eric | author1-link = Eric Allender | last2 = Lange | first2 = Klaus-Jörn | contribution = StUSPACE(log ''n'') ⊆ DSPACE(log<sup>2</sup> ''n''/log log ''n'') | doi = 10.1007/BFb0009495 | pages = 193–202 | publisher = Springer-Verlag | series = Lecture Notes in Computer Science | title = Algorithms and Computation, 7th International Symposium, ISAAC '96, Osaka, Japan, December 16–18, 1996, Proceedings | volume = 1178 | year = 1996| isbn = 978-3-540-62048-8 }}.</ref>
Multitrees may be used to represent multiple overlapping [[Taxonomy (general)|taxonomies]] over the same ground set.<ref>{{citation | last1 = Furnas | first1 = George W. | author1-link = George Furnas | last2 = Zacks | first2 = Jeff | contribution = Multitrees: enriching and reusing hierarchical structure | doi = 10.1145/191666.191778 | pages = 330–336 | title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94) | year = 1994| s2cid = 18710118 | doi-access = free }}.</ref> 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.<ref>{{citation | last1 = McGuffin | first1 = Michael J. | last2 = Balakrishnan | first2 = Ravin | contribution = Interactive visualization of genealogical graphs | doi = 10.1109/INFOVIS.2005.22 | location = Los Alamitos, California, US | publisher = IEEE Computer Society | title = IEEE Symposium on Information Visualization | year = 2005 | pages = 3| isbn = 0-7803-9464-X | s2cid = 15449409 }}.</ref>
== 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]] relation is a diamond-free partial order. Conversely, in a diamond-free partial order, the [[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]] 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 :<math>2\le \lim_{n\to\infty} D(n) \Big/ \binom{n}{\lfloor n/2\rfloor}\le 2\frac{3}{11}</math>, and it is conjectured that the limit is 2.<ref name="gll"/>
== Related structures == A [[polytree]], a directed acyclic graph formed by [[Orientation (graph theory)|orienting]] 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 (graph theory)|arborescence]] 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]],<ref>{{citation | last = Jung | first = H. A. | title = On a class of posets and the corresponding comparability graphs | journal = Journal of Combinatorial Theory, Series B | volume = 24 | year = 1978 | issue = 2 | pages = 125–133 |mr=0491356 | doi = 10.1016/0095-8956(78)90013-8| doi-access = free }}.</ref> or to other structures formed by combining multiple trees.
== References == {{reflist|30em}}
[[Category:Order theory]] [[Category:Directed acyclic graphs]]