◎全域木：与えられたグラフ G のすべての頂点を含む部分グラフ T が木であるとき，T は G の全域木であるという。
辺に長さが与えられたラベル付きグラフ G において，G の全域木の中で含まれる辺の長さの和が最小であるものを最小全域木 minimum spanning tree という。
◎最小全域木を求める２つのアルゴリズム：
［アルゴリズムその１］
・辺を長さが大きい順（降順，descending order）に並べる。
・もとのグラフ G から出発し，並んでいる順番にグラフから辺を除いてみる。グラフが連結のままであれば，その辺を除く。グラフが非連結になるときは，その辺は除かない。
・残っている辺の本数が（頂点数−1）になれば終わり。
［アルゴリズムその２］
・辺を長さが小さい順（昇順，increasing order）に並べる。
・すべての辺を除いた頂点だけからなるグラフから出発し，並んでいる順番にグラフに辺をつけ加えてみる。グラフに閉路ができなければ，その辺を加える。グラフに閉路ができれば，その辺は加えない。
・つけ加えられた辺の本数が（頂点数−1）になれば終わり。
［注意］いずれのアルゴリズムを用いても，最終的に求められた全域木の長さの和は同じになる。ただし，同じ長さの辺がある場合，それらはどの順に並んでもいいので，その並べ方によって最終的に得られる全域木は異なる場合がある。
◎根付き木 rooted tree：木の一つの頂点を根 root として指定したもの。根は通常一番上に書くが，場合によっては一番左に書くこともある。
根からその他の頂点へ向かう道順に従って辺には方向を考える。根から距離 k にある頂点は，深さが k であるとか，レベルが k であると言う。
次数が１の頂点を特に葉 leaf という。
◎順序根付き木：それぞれのレベルの頂点に順序をつけた根付き木。
◎２項演算の代数的表現を順序根付き木で表現し，一般番地系の辞書式順序で演算子（＋とか＊など）と演算される値（変数や定数）を並べ直すと，カッコを使わない数式表現が可能になる。前置式ポーランド記法と後置式ポーランド記法がある。
x と y の和を表現するとき，数学では x ＋ y と書くが，これは演算子を演算される値の間に書く中間記法。＋ x y と書く形式が前置記法で，x y ＋ と書くのが後置記法。
☆“＋ x y”という前置記法は，英語表現 the sum of x and y に出てくる単語の順序に対応している。一方，“x y ＋”という後置記法は，日本語表現「x と y の和」の順序である。
英語では，David Greene という順序で名前が先，名字が後である。これは，Greene 家の David ということで，英語で書けば David of Greenes。一方，日本語で坂本明雄というのは，「坂本家の明雄」だから名字が先に来る。