Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Multitree
Summary
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).
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.
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.
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.
A polytree, a directed acyclic graph formed by 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 rooted in the vertex, that is a polytree in which all edges are oriented away from the root.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.