木
ノードの連鎖から成るグラフでは、連鎖に沿ったメッセージの伝播によって、効率の良い推論ができることを確認しました。
実はより一般に、木と呼ばれる広いクラスのグラフでも同様の効率的な推論が可能です。
無向グラフの場合、木とは任意のノードの組の間に唯一の経路が存在するグラフとして定義されます。
したがって木はループを持ちません。
有向グラフの場合、木は根ノードと呼ばれる親を持たないノードをつだけ持ち、
他のすべてのノードはそれぞれ親をつずつ持つグラフとして定義されます。
親をつ以上持つノードが存在しないため、有向木を無向木に変換する際、
モラル化によってリンクを付け加える必要はありません。
したがって、有向木のモラルグラフは必ず無向木となります。
有向木で表現される分布は無向木で表現される分布に簡単に変換でき、その逆も可能であることに注意が必要です。
つ以上の親を持つノードが存在するが、任意の
ノード間の(矢印の方向を無視した)経路が
つしかない有向グラフは多重木と呼ばれます。
以下の図3に無向木と有向木と有向多重木の例を示します。
図1で(a)が無効木、(b)が有向木、(c)が有向多重木です。
図1
