グラフ理論での定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/22 07:52 UTC 版)
典型的には次のような定義が用いられる。「二分木は連結された (connected) 閉路をもたない (acyclic) グラフで、各頂点 (vertex) の次数 (degree) （各頂点に出入りする辺の数）が3を超えないもの。」 次のことが証明可能である。いかなる二分木でも、次数1のノードの数（葉にあたる）は次数3であるノードの数よりちょうど2だけ多く、次数2であるノードはいかなる数にもなりうる。根付き二分木は、「根にあたる頂点が一つだけ決められており、各頂点の次数が2を超えないもの」をいう。 そのような根を一つ選ぶと、全ての頂点が各々ユニークな親と2つ以下の子を持つことになる。だがこれだけでは子供の左右を決めることができない。連結条件をはずしたもの（閉路をもたない無向グラフ）を森 (forest) と呼ぶ。森は木と異なり、互いに連結している要素が複数あってもよい。 もう一つの定義は有向グラフ上での再帰的定義である。二分木は次のいずれかを指す: 単一の頂点 二つの二分木 a, b と一つの頂点vを用意し、頂点vから二つの二分木a, bそれぞれの根に対して辺を引いたもの。 この定義では左右は決まらないが、唯一の根を決定することはできる。
※この「グラフ理論での定義」の解説は、「二分木」の解説の一部です。
「グラフ理論での定義」を含む「二分木」の記事については、「二分木」の概要を参照ください。
ウィキペディア小見出し辞書の「グラフ理論での定義」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- グラフ理論での定義のページへのリンク
