In mathematics, and more specifically in graph theory, a **polytree**[1] (also called **directed tree**,[2]**oriented tree**[3][4] or **singly connected network**[5]) 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.[6]

## . . . Polytree . . .

- 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*x*,*y*, and_{i}*z*(for_{i}*i*= 0, 1, 2) such that, for each*i*, either*x*≤*y*≥_{i}*z*, or_{i}*x*≥*y*≤_{i}*z*, with these six inequalities defining the polytree structure on these seven elements.[7]_{i} - 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*.[8]

## . . . Polytree . . .

*
*

This article is issued from web site Wikipedia. The original article may be a bit shortened or modified. Some links may have been modified. The text is licensed under “Creative Commons – Attribution – Sharealike” [1] and some of the text can also be licensed under the terms of the “GNU Free Documentation License” [2]. Additional terms may apply for the media files. By using this site, you agree to our Legal pages . Web links: [1] [2]