| 词条 | Polytree |
| 释义 |
In mathematics, and more specifically in graph theory, a polytree[1] (also known as oriented tree{{sfnp|Harary|Sumner|1980}}[2] or singly connected network[3]) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic. A polytree is an example of an oriented graph. The term polytree was coined in 1987 by Rebane and Pearl.[4] Related structuresEvery arborescence (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) is a polytree, but not every polytree is an arborescence. Every polytree is a multitree, a directed acyclic graph in which the subgraph reachable from any node forms a tree. 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, yi, and zi (for {{nowrap|1=i = 0, 1, 2}}) such that, for each i, either {{nowrap|x ≤ yi ≥ zi}}, or {{nowrap|x ≥ yi ≤ zi,}} 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.[5] EnumerationThe number of distinct polytrees on n unlabeled nodes, for n = 1, 2, 3, ..., is 1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... {{OEIS|A000238}}. Sumner's conjectureSumner'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}} ApplicationsPolytrees 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.[3][4] 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
Notes1. ^1 {{harvtxt|Dasgupta|1999}}. 2. ^{{harvtxt|Simion|1991}}. 3. ^1 {{harvtxt|Kim|Pearl|1983}}. 4. ^1 {{harvtxt|Rebane|Pearl|1987}}. 5. ^{{citation | last = Ruskey | first = Frank | doi = 10.1007/BF00563523 | issue = 3 | journal =Order | mr = 1048093 | pages = 227–233 | title = Transposition generation of alternating permutations | volume = 6 | year = 1989}} References
| last1 = Carr | first1 = Hamish | last2 = Snoeyink | first2 = Jack | last3 = Axen | first3 = Ulrike | contribution = Computing contour trees in all dimensions | pages = 918–926 | title = in Proc. 11th ACM-SIAM Symposium on Discrete Algorithms (SODA 2000) | url = http://portal.acm.org/citation.cfm?id=338659 | year = 2000}}
| last1 = Dasgupta| first1 = Sanjoy | contribution = Learning polytrees | pages = 134–141 | title = in Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999 | url = http://cseweb.ucsd.edu/~dasgupta/papers/poly.pdf | year = 1999}}.
| last1 = Harary | first1 = Frank | author1-link = Frank Harary | last2 = Sumner | first2 = David | 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}}.
| 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 = in Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 | url = http://www.ijcai.org/Proceedings/83-1/Papers/041.pdf | year = 1983}}.
| 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}}.
| 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 = in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987 | url = ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf | year = 1987}}.
| last = Simion | first = Rodica | authorlink = 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}}.
| last1 = Trotter | first1 = William T., Jr. | 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}}. 1 : Trees (graph theory) |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。