On the Enumeration of Colored Trees 中野眞一群馬大学宇野毅明情報学研究所（総合研究大学院大学） 2004年5月21日アルゴリズム研究会モチベーション・あるグラフクラスに属するグラフを全部見つけたい（全部、は大変なので、ある程度以内の大きさのものに制限）・テスト問題用のカタログを作りたい・データマイニングや最適化問題の解候補を作りたい・単純かつ高速な列挙方法を見つけたい結果頂点数が k+1 ～ n、直径が k である色付き根無し木を１つあたり定数時間で出力するアルゴリズムを構築した－根無し木は、根が与えられていない木－色付き木は、各頂点に色（整数）が与えられた木・同型かつ頂点の色が等しい木を2回出力しない（重複を（効率良く）なくすのが難しい）関連研究家系図法根付き順序木有機化合物三角形分割マトロイド色付き根付き順序木根付き無順序木色付き根付き無順序木根無し木色付き根無し木フロアプラングラフ 2分木基本アルゴリズム・頂点数 1 の木から出発・頂点数 n の木に頂点を加え、頂点数が１つ大きな木を作る・この操作を用いて、バックトラック的に、重複なく木を生成する－根付き順序木ならば、「最右パスの右に葉をつける」ことで、重複なく列挙できる無順序木の列挙・順序木と同じ方法だと、同型な木が大量に出てくる ←複数の異なる順序木が、同一な無順序木に対応するから・深さ列を用いて、それらの代表を定義・代表になっているの順序木のみを列挙深さ列（順序木の）深さ列：左を優先して深さ優先探索し、訪れた頂点の深さをpre-orderで並べたもの・２つの順序木が順番も含めて同型 ⇔ 深さ列が等しい・子供の順序を入れ替えていろいろな木が作れる。その中で最大の深さ列を持つものを left heavy embedding と呼ぶ（これが代表）（各頂点の子供を子孫の深さ列の大きさでソート）・２つの無順序木が同型 ⇔ left heavy embedding が等しい 0,1,2,3,3,2,2,1,2,3 0,1,2,2,3,3,2,1,2,3 0,1,2,3,1,2,3,3,2,2 left heavy embedding の親 left-heavy embedding T の親： T の最も右の葉を取った木 ⇒ 親も left-heavy embedding T 0,1,2,3,3,2,1,2,3,2,1 親 0,1,2,3,3,2,1,2,3,2 親の親 0,1,2,3,3,2,1,2,3 ・Left heavy embedding の子は、最右パスの右に、コピー深さ以浅に葉を付けたものになる ⇒ 各頂点の子の深さ列の重みが逆転しない ⇒ コピー深さは O(1) で更新できる Family tree Left-heavy embedding の親子関係のグラフ根無し木の列挙・根がないので、深さ列で代表を決められない ⇒ センターを根と定義する（２つある場合は１つとして扱う）センター：最も遠い頂点までの距離が最も短い頂点・直径が偶数だと１つ、奇数だと２つ存在 left heavy embedding の親直径 k のleft-heavy embedding T の親： T の最も右の葉を取った木。ただし、直径が変化する場合は、右から2番目を取る ⇒ 親も直径 k のleft-heavy embedding T 0,1,2,3,3,2,1,2,3,2,1 親 0,1,2,3,3,2,1,2,3,2 親の親 0,1,2,3,3,2,1,2,3 Family tree ・Tの右端パスの右に、コピー深さより浅い位置に葉をつけると子供ができる・根の子供が2人で、2番目の子供の子孫がパスであるなら、 1番目の子供の木の最右パスの右につけても良い直径 4 の場合色深さ列（順序木の）色深さ列：左を優先して深さ優先探索し、訪れた頂点の色と深さをpre-orderで並べたもの left heavy embedding も同様に定義・２つの色付き根無し木が同型 ⇔ センターを根とした left heavy embedding が等しい a b c 0,b,1,b,2,c,2,c,1,a,1,a,2, left heavy embedding の親 T の最も右の葉を取った木。ただし、直径が変わる葉はのぞく ⇒ left-heavy embedding になるとは限らないしかたがないので、その木のleft-heavy embedding で T の親を定める a b c 0,b,1,b,2,c,3,a,2,c,1,a,2,c,1,a,2,b,3,c left heavy embedding でない場合・取り除く葉が、直径を達成するパスの直左にあるパスの葉であるときのみ（そうでないときは、それより左側で、深さ列の大小が決まっている） a b c 0,b,1,b,2,c,3,a,2,c,1,a,2,c,1,a,2,b,3,c 左右の子供の深さ列の大小の変化・大小が変化する場所は、高々一箇所子供の一覧・追加後に、「取り除いても直径が変わらない最も右の葉」になるように頂点を追加・コピー深さよりも浅い位置に追加・直径を達成するパスの左側につけるかつ、そのパスから始まるパスの末尾に追加するかつ追加するパスの深さ列が直径を達成するパスの prefix になっている場合に、左右の子の逆転を考慮・全ての子供は、１つあたり定数時間で生成できる ⇒全ての木を１つあたり定数時間で列挙できるまとめと今後の展開・頂点数 1～n 、直径 k の色付き根無し木を列挙する、１つあたり定数時間のアルゴリズムを提案した・順序木の列挙 ⇒ 無順序木 ⇒ 根無し木 ⇒ 色付き根無し木、と拡張した今後は：・木より大きなクラスのグラフの列挙がしたい