９週　根付け木の同形判定アルゴリズム

すべての端末点に０をつける。特にレベルｋのすべての点に０がついている。

レベルiの点の処理が終わり、レベルiの各点には0以上の整数がついていると仮定する。レベルi-1の端末点でない点を｛x1,x2,・・・xm｝とする。 各点xiに対し、xiの子についている整数を小さい順に並べた列(a1,a2,・・・at),a1<=a2<=・・・<=at(t=t(xi))をxiに割り当てる。そしてレベルi-1の端末点でない点に割り当てられたm個の数列{(a1,a2,・・・,at)}を辞書式順序に並べる。これをレベルi-1の数列の列として保存する。 次に辞書式順序に並べた数列を用いて、レベルi-1の点{x1,x2,・・・,xm}に番号1,2,3・・・を付けていく。まず、最初の数列と同じ数列のついたすべての点にxiに１をつける。次の数列と同じ数列のついたすべての点に2をつける。以下同様に同じ数列のついた点は同じ番号になるように順に番号を付ける。

レベルk-1からレベル0までの数列の列を作れば終わる。2つの根付き木は、最大レベルが一致し、かつすべてのレベルにおける数列の列が一致するときに限り同形である。

(012),(02,13),(001,002,02),(0,00,00) (012),(012,34),(0,01,02,1),(00,00,000)

それぞれ中心を根とする根付き木とみなし、T1とT2が同形かどうか判定する。