Multitree

Encyclopedia

In combinatorics

and order-theoretic

mathematics, a

in which the set of nodes reachable from any node form a tree

, or a partially ordered set

(also called a

relation in

forms a DAG in which the successors of any node form a tree.

is a family

and it is conjectured that the limit is 2.

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 the context of computational complexity theory

, multitrees have also been called

s in which there is at most one computational path connecting any two states.

, a directed acyclic graph

formed by assigning an orientation to each edge of an undirected tree

, may be viewed as a special case of a multitree.

The word "multitree" has also been used to refer to a series-parallel partial order

, or to other structures formed by combining multiple trees.

Combinatorics

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...

and order-theoretic

Order theory

Order theory is a branch of mathematics which investigates our 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 introduces the field and gives some basic definitions...

mathematics, a

**multitree**may describe either of two equivalent structures: a directed acyclic graphDirected acyclic graph

In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

in which the set of nodes reachable from any node form a tree

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

, or a partially ordered set

Partially ordered set

In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

(also called a

**diamond-free poset**) that does not have four items*a*,*b*,*c*, and*d*forming a diamond suborder with and but with*b*and*c*incomparable to each other.## Equivalence between DAG and poset definitions

If*G*is a directed acyclic graph in which the nodes reachable from each vertex form a tree (or equivalently, if*G*is a directed graph in which there is at most one directed path between any two nodes, in either direction) then the reachabilityReachability

In graph theory, reachability is the notion of being able to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.- Definition :For a...

relation in

*G*forms a diamond-free partial order. Conversely, if*P*is a diamond-free partial order, its transitive reductionTransitive reduction

In mathematics, a transitive reduction of a binary relation R on a set X is a minimal relation R' on X such that the transitive closure of R' is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then R' is unique...

forms a DAG in which the successors of any node form a tree.

## Diamond-free families

A diamond-free family of setsFamily 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...

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 thatand it is conjectured that the limit is 2.

## Applications

Multitrees may be used to represent multiple overlapping taxonomiesTaxonomy

Taxonomy is the science of identifying and naming species, and arranging them into a classification. The field of taxonomy, sometimes referred to as "biological taxonomy", revolves around the description and use of taxonomic units, known as taxa...

over the same ground set. If a family tree

Family tree

A family tree, or pedigree chart, is a chart representing family relationships in a conventional tree structure. The more detailed family trees used in medicine, genealogy, and social work are known as genograms.-Family tree representations:...

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 the context of computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, multitrees have also been called

**strongly unambiguous graphs**or**mangroves**; they can be used to model nondeterministic algorithmNondeterministic algorithm

In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A concurrent algorithm can perform differently on different...

s in which there is at most one computational path connecting any two states.

## Related structures

A polytreePolytree

In graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either...

, a directed acyclic graph

Directed acyclic graph

In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

formed by assigning an orientation to each edge of an undirected tree

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

, may be viewed as a special case of a multitree.

The word "multitree" has also been used to refer to a series-parallel partial order

Series-parallel partial order

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

, or to other structures formed by combining multiple trees.