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, a polytree is formed by assigning an orientation to each edge of a connected and acyclic undirected graph.

A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.

A polytree is an example of an oriented graph.

The term ''polytree'' was coined in 1987 by Rebane and Pearl..

Related structures

* An arborescence is a directed rooted tree, i.e. a directed acyclic graph in which there exists a single source node that has a unique path to every other node. Every arborescence is a polytree, but not every polytree is an arborescence.
* A multitree is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a multitree.
* The reachability relationship among the nodes of a polytree forms a partial order that has order dimension at most three. If the order dimension is three, there must exist a subset of seven elements $x$, $y_i$, and $z_i$ such that, for either $x\le y_i\ge z_i$ or $x\ge y_i\le z_i$, with these six inequalities defining the polytree structure on these seven elements.
* A fence 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. The reachability ordering in a polytree has also been called a ''generalized fence''.

Enumeration

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

Sumner's conjecture

Sumner's conjecture, named after David Sumner, states that tournaments are universal graphs 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 for all sufficiently large values of $n$.

Applications

Polytrees have been used as a graphical model for probabilistic reasoning. If a Bayesian network has the structure of a polytree, then belief propagation may be used to perform inference efficiently on it.

The contour tree of a real-valued function on a vector space is a polytree that describes the level sets of the function. The nodes of the contour tree are the level sets that pass through a critical point 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.

See also

* Glossary of graph theory

Notes

References

*
* .
* .
* .
* .
* .
* .
*.
* .
* {{citation
, last1 = Trotter , first1 = William T. Jr. , author1-link = William T. Trotter
, last2 = Moore , first2 = John I. Jr.
, doi = 10.1016/0095-8956(77)90048-X
, issue = 1
, journal = Journal of Combinatorial Theory, Series B
, pages = 54–67
, title = The dimension of planar posets
, volume = 22
, year = 1977, doi-access = free
.

Trees (graph theory)
Directed acyclic graphs