polytree

• 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$ {{nowrap|(for $i=0,1,2$)}} such that, for {{nowrap|each $i$,}} either $x\backslash le\; y\_i\backslash ge\; z\_i$ or $x\backslash ge\; y\_i\backslash le\; z\_i$, 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}}

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

{{bi|left=1.6|1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... {{OEIS|A000238}}.}}

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$.{{sfnp|Kühn|Mycroft|Osthus|2011}}

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.

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}}

• Glossary of graph theory

{{reflist|colwidth=30em}}

• {{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