Inmathematics, and more specifically in graph theory, a polytree[1] (also called directed tree,[2] oriented tree[3]orsingly connected network[4]) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.
Apolyforest (ordirected forestororiented 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.[5]
The number of distinct polytrees on unlabeled nodes, for , is
Sumner's conjecture, named after David Sumner, states that tournaments are universal graphs for polytrees, in the sense that every tournament with vertices contains every polytree with vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of .[8]
Polytrees have been used as a graphical model for probabilistic reasoning.[1] If a Bayesian network has the structure of a polytree, then belief propagation may be used to perform inference efficiently on it.[4][5]
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.[9]