Concept

Polytree

In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree or singly connected network) 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 polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic. A polytree is an example of an oriented graph. The term polytree was coined in 1987 by Rebane and Pearl. 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 , , and (for ) such that, for each , either or , with these six inequalities defining the polytree structure on these seven elements. 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. The number of distinct polytrees on unlabeled nodes, for , is Sumner's conjecture, named after David Sumner, states that tournaments are universal graphs for polytrees, in the sense that every tournament with vertices contains every polytree with vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of . Polytrees have been used as a graphical model for probabilistic reasoning.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.