有向木とは何？わかりやすく解説 Weblio辞書

有向木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/12 14:26 UTC 版)

詳細は「:en:Polytree」を参照「有向木 (polytree, directed tree, oriented tree, singly connected network)」とは、有向グラフの一種であって、その有向辺をすべて無向辺に置き換えたものが木グラフになるような有向非巡回グラフである。同様に、「有向森」は、その有向辺をすべて無向辺に置き換えたものが森グラフになるような有向非巡回グラフである。

※この「有向木」の解説は、「グラフ (離散数学)」の解説の一部です。
「有向木」を含む「グラフ (離散数学)」の記事については、「グラフ (離散数学)」の概要を参照ください。

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/24 13:38 UTC 版)

「木 (数学)」の記事における「有向木」の解説

一般に、無向木は任意の点を根とみなすことができる。それに対し有向木は、根である点をただ1つだけ持つ。辺の向きとして、根から葉に向かっている場合と、葉から根に向かっている場合とがある。混在はできない（混在してしまうと閉路ができてしまう）。閉路を持たない任意の有向グラフは有向非巡回グラフ（Directed Acyclic Graph、DAG）である。有向木は連結な有向非巡回グラフでもあるが、連結な有向非巡回グラフが必ずしも有向木とは限らない（DAGでは子孫あるいは親の共有がある場合がある。そうするとそれは木ではない）。

※この「有向木」の解説は、「木 (数学)」の解説の一部です。
「有向木」を含む「木 (数学)」の記事については、「木 (数学)」の概要を参照ください。

ウィキペディア小見出し辞書の「有向木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。


	Text is available under GNU Free Documentation License (GFDL). Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのグラフ (離散数学) (改訂履歴)、木 (数学) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。