From Surf Wiki (app.surf) — the open knowledge base
Multitree
Type of graph in mathematics
Type of graph in mathematics
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 vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a 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{{citation
In 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.{{citation
Multitrees may be used to represent multiple overlapping taxonomies over the same ground set.{{citation
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 :2\le \lim_{n\to\infty} D(n) \Big/ \binom{n}{\lfloor n/2\rfloor}\le 2\frac{3}{11}, and it is conjectured that the limit is 2.
References
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about Multitree — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report