In graph theory, polytree is a name for an oriented tree; that is, a polytree is a directed graph formed by giving a direction to each edge of a tree, forming an orientation of the tree. In other words, it is a directed graph with exactly one directed path between any two vertices; equivalently, it is a directed acyclic graph (DAG) for which there are no undirected cycles and for which the underlying undirected graph is connected.
Every directed tree (a directed acyclic graph 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, a directed acyclic graph in which the subgraph reachable from any node forms a tree.
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, yi, and zi (for i = 0, 1, 2) such that, for each i, either x ≤ yi ≥ zi, or x ≥ yi ≤ zi, 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 number of distinct polytrees on n unlabeled nodes, for n = 1, 2, 3, ..., is
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.
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.
- Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", Proceedings of UAI, pp. 222–228.
- Kim, J., J. H.; Pearl (1983), "A computational model for causal and diagnostic reasoning in inference engines", Proc. of the Eighth International Joint Conference on Artificial Intelligence, pp. 190–193.
- Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences 5 (3): 184–187, MR 603363
- Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics 88 (1): 93–104, doi:10.1016/0012-365X(91)90061-6, MR 1099270.
- Trotter, William T., Jr.; Moore, John I., Jr. (1977), "The dimension of planar posets", Journal of Combinatorial Theory, Series B 22 (1): 54–67, doi:10.1016/0095-8956(77)90048-X.
- Kühn, Daniela; Mycroft, Richard; Osthus, Deryk (2011), "A proof of Sumner's universal tournament conjecture for large tournaments", Proceedings of the London Mathematical Society. Third Series 102 (4): 731–766, arXiv:1010.4430, doi:10.1112/plms/pdq035, MR 2793448.
- Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Computing contour trees in all dimensions", Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 918–926.