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

and

order theory 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 intr ...

, 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 ...

(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 partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...

(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 explores the relationships between these classifications. A computational problem ...

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

nondeterministic algorithm In computer science and 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. Different models of computation ...

s in which there is at most one computational path connecting any two states. Multitrees may be used to represent multiple overlapping

taxonomies image:Hierarchical clustering diagram.png, 280px, Generalized scheme of taxonomy Taxonomy is a practice and science concerned with classification or categorization. Typically, there are two parts to it: the development of an underlying scheme o ...

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 a ...

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 In set theory and related branches of mathematics, a family (or collection) can mean, depending upon the context, any of the following: set, indexed set, multiset, or class. A collection F of subsets of a given set S is called a family of su ...

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

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. The word "multitree" has also been used to refer to a series–parallel partial order,. or to other structures formed by combining multiple trees.

References

{{reflist, 30em Order theory Directed acyclic graphs