木
提供: Mathpedia
定義
閉路を含まないグラフについて、これを林とよぶ。連結な林について、これを木と呼ぶ。
用語
- 木のなかの次数 $1$ の頂点を葉という。
- 根つき木とは、木 $T$ と $T$ のひとつの頂点 $r$ の組 $(T,r)$ のことである。すなわち、基点付きの木のことである。
- 根つき木 $(T,r)$ について、$(T,r)$ 上の木順序とは、$|T|$ 上に次のように定まる半順序である: $x,y \in |T|$ について $x$ を通る $r$ から $y$ への道が存在するときかつそのときに限り $x \leq_T y$ と定める。
information
情報源
- R. Diestel. "Graph Theory". Springer (2000).
