Polytree (original) (raw)

From Wikipedia, the free encyclopedia

Type of graph in mathematics

A polytree

In mathematics, and more specifically in graph theory, a polytree[1] (also called directed tree,[2] oriented tree[3] or singly connected network[4]) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, a polytree is formed by assigning an orientation to each edge of a connected and acyclic undirected graph.

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

The number of distinct polytrees on n {\displaystyle n} {\displaystyle n} unlabeled nodes, for n = 1 , 2 , 3 , … {\displaystyle n=1,2,3,\dots } {\displaystyle n=1,2,3,\dots }, is

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (sequence A000238 in the 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 2 n − 2 {\displaystyle 2n-2} {\displaystyle 2n-2} vertices contains every polytree with n {\displaystyle n} {\displaystyle n} vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of n {\displaystyle n} {\displaystyle n}.[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]

  1. ^ a b Dasgupta (1999).
  2. ^ Deo (1974), p. 206.
  3. ^ Harary & Sumner (1980); Simion (1991).
  4. ^ a b Kim & Pearl (1983).
  5. ^ a b Rebane & Pearl (1987).
  6. ^ Trotter & Moore (1977).
  7. ^ Ruskey (1989).
  8. ^ Kühn, Mycroft & Osthus (2011).
  9. ^ Carr, Snoeyink & Axen (2000).