Multitree

, a multitree used in distributed computation, showing in red the undirected tree induced by the subgraph reachable from one of its vertices.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

, 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 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 , , , and forming a diamond suborder with and but with and incomparable to each other (also called a diamond-free poset ).

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. Multitrees may be used to represent multiple overlapping taxonomies over the same ground set.

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.

, 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 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 , , , and forming a diamond suborder with and but with and incomparable to each other (also called a diamond-free poset ).

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. Multitrees may be used to represent multiple overlapping taxonomies over the same ground set.

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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1323981624 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.