Polytree

In mathematics, and more specifically in graph theory, a polytree[1] (also called directed tree,[2] oriented tree[3] or singly connected network[4]) is a directed acyclic graph whose underlying undirected graph is a tree.

, is Sumner's conjecture, named after David Sumner, states that tournaments are universal graphs for polytrees, in the sense that every tournament with

Although it remains unsolved, it has been proven for all sufficiently large values of

[8] Polytrees 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.

The orientation of an edge is determined by the comparison between the function values on the corresponding two level sets.