Polytree

In graph theory, a polytree is a 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. The name "polytree" was coined by Rebane and Pearl (1987), and is sometimes referred to as "singly connected network" (Kim and Pearl, 1983).

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. For trees, if directed, every node should have indegree 0 or 1.

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.

References