Polytree
From Wikipedia, the free encyclopedia
In graph theory, a polytree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either. Equivalently, a polytree is a directed graph formed by giving a direction to each edge of a forest.
The name "polytree" was coined by Rebane and Pearl (1987), and is sometimes referred to as "singly connected network" (Kim and Pearl, 1983)[1].
Every directed tree is a polytree, but not every polytree is a directed tree. The picture on the right shows a polytree which is not a directed tree.
Polytrees often are encountered in Bayesian networks. In fact, some problems can be solved in polytrees in polynomial time but take exponential time in general networks.
[edit] References
- ^ Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems, San Mateo, CA: Morgan Kaufmann.
 |
This computer science article is a stub. You can help Wikipedia by expanding it. |
