Polytree

• 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==