Polytree
Get Polytree essential facts below. View Videos or join the Polytree discussion. Add Polytree to your PopFlock.com topic list for future reference or share this resource on social media.
Polytree
A polytree.

In mathematics, and more specifically in graph theory, a polytree[1] (also called directed tree,[2]oriented tree[3][4] or singly connected network[5]) 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.

A polyforest (or directed forest or oriented 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.[6]

Related structures

Every arborescence (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) is a polytree, but not every polytree is an arborescence. 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 ) such that, for each i, either , or with these six inequalities defining the polytree structure on these seven elements.[7]

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

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 in the 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 for all sufficiently large values of n.[9]

Applications

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

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

See also

Notes

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

References


  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Polytree
 



 



 
Music Scenes