View source for Polytree

[[File:Polytree.svg|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 (graph theory)|tree]]. In other words, if we replace its [[directed edge]]s with undirected edges, we obtain an undirected graph that is both [[Connectivity (graph theory)|connected]] and [[Cycle (graph theory)|acyclic]]. (It is required that no two undirected edges are replaced by the same directed edge; i.e. there must be no pair of vertices linked in the directed graph by edges in both directions.)

A '''polyforest''' (or '''directed forest''' or '''oriented forest''') is a directed acyclic graph whose underlying undirected graph is a [[Tree (graph theory)#Forest|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 [[Orientation (graph theory)|oriented graph]].

The term ''polytree'' was coined in 1987 by Rebane and [[Judea Pearl|Pearl]].<ref name="rp87">{{harvtxt|Rebane|Pearl|1987}}.</ref>

==Related structures==

* An [[Arborescence (graph theory)|arborescence]] is a directed rooted [[Tree (graph theory)|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 (mathematics)|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 [[tournament (graph theory)|tournaments]] are [[universal graph]]s 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 set]]s of the function. The nodes of the contour tree are the level sets that pass through a [[critical point (mathematics)|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 (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 (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]]