In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a polytree is a directed graph

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

 with at most one undirected path between any two vertices. In other words, a polytree is 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...

 (DAG) for which there are no undirected cycles either. Equivalently, a polytree is a directed graph formed by giving a direction to each edge of a forest

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

.

The name "polytree" was coined by ; polytrees have also been referred to as singly connected networks and oriented trees.

Related structures

Every directed 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...

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

 in which there exists a single source node that has a unique path to every other node) is a polytree, but not every polytree is a directed tree. Every polytree is a multitree

Multitree

In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set that does not have four items a, b, c, and d forming a diamond suborder...

, a directed acyclic graph in which the subgraph reachable from any node forms a tree.

The reachability

Reachability

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

 relationship among the nodes of a polytree forms a partial order that has order dimension

Order dimension

In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....

 at most three. If the order dimension is three, there must exist a subset of seven elements x, y_i, and z_i (for ) such that, for each i, either , or with these six inequalities defining the polytree structure on these seven elements.

A fence

Fence (mathematics)

In mathematics, a fence, also called a zigzag poset, is a partially ordered set in which the order relations form a path with alternating orientations:orA fence may be finite, or it may be formed by an infinite alternating sequence extending in both directions.A linear extension of a fence is...

 or zigzag poset is a special case of a polytree in which the underlying tree is a path and the edges have orientations that alternate along the path.

Enumeration

The number of distinct polytrees on n unlabeled nodes, for n = 1, 2, 3, ..., is

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... .

Sumner's conjecture

Sumner's conjecture, named after David Sumner, states that tournaments

Tournament (graph theory)

A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge....

 are universal graph

Universal graph

In mathematics, a universal graph is an infinite graph that contains every finite graph as an induced subgraph. A universal graph of this type was first constructed by R. Rado and is now called the Rado graph or random graph...

s for polytrees, in the sense that every tournament with 2n − 2 vertices contains every polytree with n vertices as a subgraph. Although it remains unsolved, it has been proven that tournaments with 3n − 3 vertices are universal in this sense.

Applications

Polytrees have been used as a graphical model

Graphical model

A graphical model is a probabilistic model for which a graph denotes the conditional independence structure between random variables. They are commonly used in probability theory, statistics—particularly Bayesian statistics—and machine learning....

 for probabilistic reasoning. If a Bayesian network

Bayesian network

A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph . For example, a Bayesian network could represent the probabilistic...

 has the structure of a polytree, then belief propagation

Belief propagation

Belief propagation is a message passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes...

 may be used to perform inference efficiently on it.

The contour tree of a real-valued function on a vector space

Vector space

A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...

 is a polytree that describes the level set

Level set

In mathematics, a level set of a real-valued function f of n variables is a set of the formthat is, a set where the function takes on a given constant value c....

s of the function. The nodes of the contour tree are the level sets that pass through a critical point

Critical point

Critical point may refer to:*Critical point *Critical point *Critical point *Construction point of a ski jumping hill-See also:*Brillouin zone*Percolation thresholds...

of the function and the edges describe contiguous sets of level sets without a critical point. The orientation of an edge is determined by the comparison between the function values on the corresponding two level sets.