{{Short description|Type of graph in mathematics}} thumb|A polytree In mathematics, and more specifically in graph theory, a '''polytree'''{{sfnp|Dasgupta|1999}} (also called '''directed tree''',{{sfnp|Deo|1974|p=206}} '''oriented tree'''<ref>{{harvtxt|Harary|Sumner|1980}}; {{harvtxt|Simion|1991}}.</ref> or '''singly connected network'''<ref name="kp83">{{harvtxt|Kim|Pearl|1983}}.</ref>) 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.<ref name="rp87">{{harvtxt|Rebane|Pearl|1987}}.</ref>

==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 <math>x</math>, <math>y_i</math>, and <math>z_i</math> {{nowrap|(for <math>i=0,1,2</math>)}} such that, for {{nowrap|each <math>i</math>,}} either <math>x\le y_i\ge z_i</math> or <math>x\ge y_i\le z_i</math>, with these six inequalities defining the polytree structure on these seven elements.{{sfnp|Trotter|Moore|1977}} * 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''.{{sfnp|Ruskey|1989}}

==Enumeration== The number of distinct polytrees on <math>n</math> unlabeled nodes, for <math>n=1,2,3,\dots</math>, is {{bi|left=1.6|1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... {{OEIS|A000238}}.}}

==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 <math>2n-2</math> vertices contains every polytree with <math>n</math> vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of <math>n</math>.{{sfnp|Kühn|Mycroft|Osthus|2011}}

==Applications== Polytrees have been used as a graphical model for probabilistic reasoning.{{sfnp|Dasgupta|1999}} If a Bayesian network has the structure of a polytree, then belief propagation may be used to perform inference efficiently on it.<ref name="kp83"/><ref name="rp87"/>

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.{{sfnp|Carr|Snoeyink|Axen|2000}}

==See also== * Glossary of graph theory

==Notes== {{reflist|colwidth=30em}}

==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 |last=Deo |first=Narsingh |date=1974 |title=Graph Theory with Applications to Engineering and Computer Science |url=http://www.edutechlearners.com/download/Graphtheory.pdf |location=Englewood, New Jersey |publisher=Prentice-Hall |isbn=0-13-363473-6 }}. * {{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 }}.

Category:Trees (graph theory) Category:Directed acyclic graphs