木

%%{init: {"flowchart" : { "curve" : "basis" } } }%%
graph TD
  1((1)) --- 2((2))
  1 --- 5((5))
  2 --- 3((3))
  2 --- 4((4))
  5 --- 6((6))
  5 --- 8((8))
  5 --- 9((9))
  6 --- 7((7))

グラフのうち，連結でかつ閉路がないグラフを木という． また，その特徴から，次の条件を満たすものは木であると言える．

• 連結で閉路がない
• 閉路がなく\(|E| = |V| - 1\)
• 連結で\(|E| = |V| - 1\)
• 連結で全ての辺が橋
• 閉路がなく，辺を1つ加えると必ず閉路ができる
• 任意の2ノード間のパスが1本

また，任意の連結グラフについて，単一始点最短路を求めたとき，全ノードと，使われた辺の集合で構成されるグラフは木である．(ただし単一始点最短路存在するグラフに限る．)証明は省略する．

木でよく出る単語

根

木では，任意のノードを根と定めることができる．根が定められた木を根付き木という．

深さ

根と定めたノードからの距離を深さという．(ここでいう距離では，辺の重みは考慮しない．) 根付き木において，任意のノードについて，自分と接続された，自分より深さが1低いノードをそのノードの親という．根は親を持たず，根以外のノードは必ず親を1つだけもつ．また，自分と接続された親以外の全てのノードのことを子という．さらに，あるノードから子をたどってたどり着けるノードはそのノードの子孫といい，あるノード\(u\)があるノード\(v\)の子孫であるとき，\(v\)は\(u\)の下にあるという．また，\(u\)を\(v\)の祖先であるという．

部分木

木において，ある1辺を取り除くと，必ず2つの木となる．木から，ある1辺を取り除いて得られる木を全てその木の部分木という．根付き木においてあるノードとその下の部分を取り出した部分とも言える．

また，あるノードからその親

LCA

ある2つのノードが与えられたとき，その2つのノードを自分の下に持つノードを，共通祖先といい共通祖先のうち，最も深さが深い(大きい)ものをその2つのノードの**LCA(最小共通祖先)**という．

n分木

根付き木において，全てのノードが\(n\)個以下の子を持つとき，それをn分木という．また，全てのノードがちょうど\(n\)個の子を持つとき，それを完全n分木という．