combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

and

order-theoretic Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intro ...

mathematics, a multitree may describe either of two equivalent structures: a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...

(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 In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

(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 In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, multitrees have also been called strongly unambiguous graphs or mangroves; they can be used to model

nondeterministic algorithm In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave diffe ...

s 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 A family tree, also called a genealogy or a pedigree chart, is a chart representing family relationships in a conventional tree structure. More detailed family trees, used in medicine and social work, are known as genograms. Representations of ...

may contain multiple marriages from one family to another, but does not contain marriages between any two blood relatives, then it forms a multitree.

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 In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s an ...

relation is a diamond-free partial order. Conversely, in a partial order, if it is diamond-free, then its

transitive reduction In the mathematical field of graph theory, a transitive reduction of a directed graph is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed) path from to in exists if ...

identify 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 In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fam ...

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_ D(n) \Big/ \binom\le 2\frac

and it is conjectured that the limit is 2.

Related structures

polytree In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree; . or singly connected network.) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its ...

, 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. The word "multitree" has also been used to refer to a

series-parallel partial order In order theory, order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations... The series-parallel partial orders may be charact ...

,. or to other structures formed by combining multiple trees.

References

{{reflist, 30em Order theory Directed acyclic graphs