|
In mathematics, and more specifically in graph theory, a polytree〔.〕 (also known as 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 polytree is an example of an oriented graph. The term ''polytree'' was coined in 1987 by Rebane and Pearl.〔.〕 ==Related structures== Every arborescence (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) is a polytree, but not every polytree is an arborescence. Every polytree is a multitree, a directed acyclic graph in which the subgraph reachable from any node forms a tree. 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'', ''yi'', and ''zi'' (for ) such that, for each ''i'', 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''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polytree」の詳細全文を読む スポンサード リンク
|