Polytree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
A polytree

In mathematics, and more specifically in graph theory, a polytree[1] (also known as oriented tree[2][3] or singly connected network[4]) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed arcs with undirected edges, we obtain an undirected graph that is both connected and acyclic.

A polytree is an example of oriented graph.

The term polytree was coined in 1987 by Rebane and Pearl.[5]

Related structures[edit]

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 xyizi, or xyizi, with these six inequalities defining the polytree structure on these seven elements.[6]

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

Enumeration[edit]

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[edit]

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

Applications[edit]

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]

See also[edit]

Notes[edit]

  1. ^ a b Dasgupta (1999).
  2. ^ Harary & Sumner (1980).
  3. ^ Simion (1991).
  4. ^ a b Kim & Pearl (1983).
  5. ^ a b Rebane & Pearl (1987).
  6. ^ Trotter & Moore (1977).
  7. ^ Ruskey, Frank (1989), "Transposition generation of alternating permutations", Order 6 (3): 227–233, doi:10.1007/BF00563523, MR 1048093 
  8. ^ Kühn et al. (2011).
  9. ^ Carr et al. (2000).

References[edit]