Polytree

A simple polytree

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

The name "polytree" was coined by Rebane & Pearl (1987);^[1] polytrees have also been referred to as singly connected networks^[2] and oriented trees.^[3][4]

Related structures

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, y_i, and z_i (for i = 0, 1, 2) such that, for each i, either x ≤ y_i ≥ z_i, or x ≥ y_i ≤ z_i, with these six inequalities defining the polytree structure on these seven elements.^[5]

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.

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, ... (sequence A000238 in OEIS).

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 that tournaments with 3n − 3 vertices are universal in this sense.^[6][7]

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.^[1][2]

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.^[8]

References

1. ^ ^{a b} Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", Proceedings of UAI, pp. 222–228, ftp://www.cs.ucla.edu/tech-report/198_-reports/870031.pdf .
2. ^ ^{a b} 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 .
3. ^ Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences 5 (3): 184–187, MR603363 
4. ^ Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics 88 (1): 93–104, doi:10.1016/0012-365X(91)90061-6, MR1099270 .
5. ^ 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 .
6. ^ Sumner's Universal Tournament Conjecture, Douglas B. West, retrieved 2010-09-17.
7. ^ El Sahili, A. (2004), "Trees in tournaments", Journal of Combinatorial Theory. Series B 92 (1): 183–187, doi:10.1016/j.jctb.2004.04.002, MR2078502 
8. ^ 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, http://portal.acm.org/citation.cfm?id=338659 .