On the Enumeration of Colored Trees

Presentation on theme: "On the Enumeration of Colored Trees"— Presentation transcript:

1 On the Enumeration of Colored Trees
中野 眞一　　　　宇野 毅明 　群馬大学 　　 　情報学研究所 　　　　　　　　　　　　（総合研究大学院大学） 2004年5月21日　アルゴリズム研究会

2 モチベーション ・あるグラフクラスに属するグラフを全部見つけたい ・ テスト問題用のカタログを作りたい
（全部、は大変なので、ある程度以内の大きさのものに制限） ・ テスト問題用のカタログを作りたい ・ データマイニングや最適化問題の解候補を作りたい ・ 単純かつ高速な列挙方法を見つけたい

3 結果 － 根無し木は、根が与えられていない木 － 色付き木は、各頂点に色（整数）が与えられた木
頂点数が k+1 ～ n、 直径が k である色付き根無し木を 　１つあたり 定数時間 で出力するアルゴリズムを構築した － 根無し木は、根が与えられていない木 － 色付き木は、各頂点に色（整数）が与えられた木 ・ 同型かつ頂点の色が等しい木を2回出力しない （重複を（効率良く）なくすのが難しい）

4 関連研究 家系図法 有機化合物 根付き順序木 三角形分割 マトロイド 色付き根付き 順序木 根付き 無順序木 フロアプラン グラフ
2分木 根無し木 色付き根無し木

5 基本アルゴリズム ・ 頂点数 1 の木から出発 ・ 頂点数 n の木に頂点を加え、頂点数が１つ大きな木を作る
・ この操作を用いて、バックトラック的に、重複なく木を生成する －根付き順序木ならば、 「最右パスの右に葉をつける」ことで、 重複なく列挙できる

6 無順序木の列挙 ・ 順序木と同じ方法だと、同型な木が大量に出てくる ←複数の異なる順序木が、同一な無順序木に対応するから
　←複数の異なる順序木が、同一な無順序木に対応するから ・深さ列を用いて、それらの代表を定義 ・ 代表になっているの順序木のみを列挙

7 深さ列 （順序木の）深さ列： 左を優先して深さ優先探索し、訪れた頂点の深さをpre-orderで並べたもの
・２つの順序木が順番も含めて同型　⇔ 深さ列が等しい ・子供の順序を入れ替えていろいろな木が作れる。その中で最大の深さ列を持つものを left heavy embedding と呼ぶ （これが代表） 　　（各頂点の子供を子孫の深さ列の大きさでソート） ・２つの無順序木が同型　⇔ left heavy embedding が等しい 0,1,2,3,3,2,2,1,2, ,1,2,2,3,3,2,1,2, ,1,2,3,1,2,3,3,2,2

8 left heavy embedding の親
left-heavy embedding T の親 ： T の最も右の葉を取った木 　　⇒ 親も left-heavy embedding T 親 親の親 0,1,2,3,3,2,1,2,3,2, ,1,2,3,3,2,1,2,3, ,1,2,3,3,2,1,2,3 ・Left heavy embedding の子は、最右パスの右に、コピー深さ以浅に葉を付けたものになる 　⇒ 各頂点の子の深さ列の重みが逆転しない 　⇒ コピー深さは O(1) で更新できる

9 Left-heavy embedding の親子関係のグラフ
Family tree Left-heavy embedding の親子関係のグラフ

10 根無し木の列挙 ・ 根がないので、深さ列で代表を決められない ⇒ センターを根と定義する（２つある場合は１つとして扱う）
　　⇒ センターを根と定義する（２つある場合は１つとして扱う） センター： 最も遠い頂点までの距離が最も短い頂点 ・ 直径が偶数だと１つ、奇数だと２つ存在

11 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,2,3,3,2,1,2,3, ,1,2,3,3,2,1,2,3

12 Family tree ・Tの右端パスの右に、コピー深さより 浅い位置に葉をつけると子供ができる ・根の子供が2人で、2番目の
子供の子孫がパスであるなら、 1番目の子供の木の 最右パスの右につけても良い 直径 4 の場合

13 色深さ列 （順序木の）色深さ列： 左を優先して深さ優先探索し、訪れた頂点の色と深さをpre-orderで並べたもの
left heavy embedding も同様に定義 ・２つの色付き根無し木が同型 　⇔ センターを根とした left heavy embedding が等しい a b c 0,b,1,b,2,c,2,c,1,a,1,a,2,

14 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

15 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

16 左右の子供の深さ列の大小の変化 ・ 大小が変化する場所は、高々一箇所

17 子供の一覧 ・ 追加後に、「取り除いても直径が変わらない最も右の葉」になるように頂点を追加 ・ コピー深さよりも浅い位置に追加
・ 直径を達成するパスの左側につける 　かつ、そのパスから始まるパスの末尾に追加する 　かつ　追加するパスの深さ列が 直径を達成するパスのprefix になっている 場合に、左右の子の逆転を考慮 ・ 全ての子供は、１つあたり 定数時間で生成できる ⇒全ての木を１つあたり定数時間で列挙できる

18 まとめと今後の展開 ・頂点数 1～n 、直径 k の色付き根無し木を列挙する、１つあたり定数時間のアルゴリズムを提案した
・ 順序木の列挙　⇒　無順序木　⇒　根無し木　⇒　色付き根無し木、と拡張した 今後は： ・ 木より大きなクラスのグラフの列挙がしたい