Polytree

Quality 0.50 · 4 views · Updated 2 months ago

Type of graph in mathematics

title: "Polytree" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["trees-(graph-theory)", "directed-acyclic-graphs"] description: "Type of graph in mathematics" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Polytree" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Type of graph in mathematics ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/6/61/Polytree.svg" caption="A polytree"] ::

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

Related structures

  • An arborescence is 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. Every arborescence is a polytree, but not every polytree is an arborescence.
  • A multitree is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a multitree.
  • 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 such that, for each i, either x\le y_i\ge z_i or x\ge y_i\le z_i, 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 reachability ordering in a polytree has also been called a generalized fence.

Enumeration

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

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.

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.

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.

Notes

References

  • {{citation | last1 = Carr | first1 = Hamish | last2 = Snoeyink | first2 = Jack | last3 = Axen | first3 = Ulrike | contribution = Computing contour trees in all dimensions | pages = 918–926 | title = Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000) | contribution-url = http://portal.acm.org/citation.cfm?id=338659 | year = 2000| publisher = Association for Computing Machinery | isbn = 978-0-89871-453-1
  • {{citation | last1 = Dasgupta| first1 = Sanjoy | contribution = Learning polytrees | pages = 134–141 | title = Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999 | contribution-url = http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf | year = 1999}}.
  • .
  • {{citation | last1 = Harary | first1 = Frank | author1-link = Frank Harary | last2 = Sumner | first2 = David | author2-link = David Sumner | mr = 603363 | issue = 3 | journal = Journal of Combinatorics, Information & System Sciences | pages = 184–187 | title = The dichromatic number of an oriented tree | volume = 5 | year = 1980}}.
  • {{citation | last1 = Kim | first1 = Jin H. | last2 = Pearl | first2 = Judea | author2-link = Judea Pearl | contribution = A computational model for causal and diagnostic reasoning in inference engines | pages = 190–193 | title = Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 | contribution-url = http://www.ijcai.org/Proceedings/83-1/Papers/041.pdf | year = 1983}}.
  • {{citation | last1 = Kühn | first1 = Daniela | author1-link = Daniela Kühn | last2 = Mycroft | first2 = Richard | last3 = Osthus | first3 = Deryk | arxiv = 1010.4430 | doi = 10.1112/plms/pdq035 | issue = 4 | journal = Proceedings of the London Mathematical Society | series = Third Series | mr = 2793448 | pages = 731–766 | title = A proof of Sumner's universal tournament conjecture for large tournaments | volume = 102 | year = 2011}}.
  • {{citation | last1 = Rebane | first1 = George | last2 = Pearl | first2 = Judea | author2-link = Judea Pearl | contribution = The recovery of causal poly-trees from statistical data | pages = 222–228 | title = Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 | contribution-url = http://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf | year = 1987
  • {{citation | last = Ruskey | first = Frank | author-link = Frank Ruskey | doi = 10.1007/BF00563523 | issue = 3 | journal =Order | mr = 1048093 | pages = 227–233 | title = Transposition generation of alternating permutations | volume = 6 | year = 1989}}.
  • {{citation | last = Simion | first = Rodica | author-link = Rodica Simion | doi = 10.1016/0012-365X(91)90061-6 | mr = 1099270 | issue = 1 | journal = Discrete Mathematics | pages = 93–104 | title = Trees with 1-factors and oriented trees | volume = 88 | year = 1991
  • {{citation | last1 = Trotter | first1 = William T. Jr. | author1-link = William T. Trotter | last2 = Moore | first2 = John I. Jr. | doi = 10.1016/0095-8956(77)90048-X | issue = 1 | journal = Journal of Combinatorial Theory, Series B | pages = 54–67 | title = The dimension of planar posets | volume = 22 | year = 1977| doi-access = free

References

  1. {{harvtxt. Harary. Sumner. 1980; {{harvtxt. Simion. 1991.
  2. {{harvtxt. Kim. Pearl. 1983.
  3. {{harvtxt. Rebane. Pearl. 1987.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

trees-(graph-theory)directed-acyclic-graphs