| 翻訳と辞書 |
multitree
In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph in which the set of nodes reachable from any node form a tree, or a partially ordered set that does not have four items ''a'', ''b'', ''c'', and ''d'' forming a diamond suborder with and but with ''b'' and ''c'' incomparable to each other (also called a diamond-free poset〔.〕).
==Equivalence between directed acyclic graph and poset definitions==
If ''G'' is a directed acyclic graph ("DAG") in which the nodes reachable from each vertex form a tree (or equivalently, if ''G'' is a directed graph in which there is at most one directed path between any two nodes, in either direction) then the reachability relation in ''G'' forms a diamond-free partial order. Conversely, if ''P'' is a diamond-free partial order, its transitive reduction forms a DAG in which the successors of any node form a tree.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「multitree」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|