A Simple Constant Time Enumeration Algorithm for Free Trees 中野眞一群馬大学宇野毅明情報学研究所 2003年9月19日アルゴリズム研究会結果頂点数が n、直径が k である根無し木を１つあたり定数時間で出力するアルゴリズムを構築した・同型な木を2回出力することはない・１つ出力してから次を出力するまで、定数時間「free tree」は、「根の無い木」のことです研究背景列挙の研究は面白い・キレイな結果の出る問題が残っている（アルゴリズム的な研究がされつくしていない）・近年、工学的な応用が増えた（計算機パワーの増大＆アルゴリズムの進展で、列挙という手法を使ったモデルを解けるようになった）－データの生成、解候補の作成、ものの特徴付け、など問題：根無し木の列挙問題：頂点数が n 、直径が k の根無し木を列挙せよただし、同型なものは同一視せよ。根無し木の列挙既存研究：・ 1つあたり定数時間。・ただし、複雑でよく分からない・ Delay（次の出力までの時間）は定数でない問題の難しさ・通常、この手の列挙問題にはバックトラック法が使われる・例えば、1頂点から子供を付け足していき、n頂点、直径k になったら出力して引き返し、他の位置に子供を付け足す。 ⇒ 木をメモリに蓄える際に、どうしても根（のようなもの）と兄弟の順番が決まる。 ⇒ 同型なものがたくさん出てしまう難しさを避ける作戦：根無し木に対して、ある標準的な「根の与え方」「子供の順序の与え方」を定める（標準形）－根無し木と標準形は1対1対応する・あとは、標準形を列挙しましょう（※ 以後、直径 k を偶数とする）根の与え方木のセンターを根とするセンター：最も遠い頂点までの距離が最も短い頂点（つまりは真ん中）直径が偶数だと、唯一的に定まる順番を与える：depth sequence depth sequence：左を優先して深さ優先探索し、訪れた頂点の深さをpreorderで並べたもの２つの木が順番も含めて同型 ⇔ depth sequence が等しい 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 L(v) ： v から下の部分木の depth sequence 辞書順： bro(v ) ： v の左隣の兄弟長いほうが大きい T が Left-heavy embedding ： ⇔ 任意の頂点v について、L(bro(v)) ≧ L(v) ・ 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 標準形ができました・根無し木に対して (1) センターを根にする (2) Left-heavy embedding になるように順番をつけるとして標準形（根付き順序木）が得られる・あとは、頂点数が n、直径がk である、標準形（left-heavy embedding）を列挙しましょう left heavy embedding の親 left-heavy embedding T の親： Tの（根の子供でない）最も右の葉を取り、根の子供にした木 ⇒ 親も left-heavy embedding ただし、直径が変わってしまう場合は、右から2番目をとる T 0,1,2,3,3,2,1,2,3,2,1 親親の親 0,1,2,3,3,2,1,2,3,1,1 0,1,2,3,3,1,2,3,1,1,1 Family tree Left-heavy embedding の親子関係をグラフで表現・これを深さ優先探索する・標準形Tの子供が作れれば探索できる頂点数 7、直径 4 の場合 left heavy embedding の子・ Tの子供 S は T の根の子供を1つとり、（深さ2以上の）最も右の葉になるように付けたもの O(1)時間で作れる・逆は、成り立つとは限らない。しかし、「ある頂点 v の深さ以下であれば子供になる」という性質が成り立つしかも、子供の v は、親の v の次か、加えた頂点の直左 T 子供 O(1)時間で更新できる１つ定数時間で列挙できる Delayを定数にする・「深さが奇数の反復は、再帰呼び出しの前に出力」「深さが偶数の反復は、再帰呼び出しの後に出力」とすると、次の出力までの計算時間が定数（３反復以下）になる再帰構造直径が奇数の場合・センターが２つになる 2つのセンターを１つの頂点のように扱い、同様の議論をする（根の子供の順番付けに関して例外処理が必要）まとめと今後の展開・頂点数 n 、直径 k の根無し木を列挙する、次の出力まで定数時間であるアルゴリズムを提案した・まず直径が偶数の場合のアルゴリズムを作り、直径が奇数の場合は、それを拡張した今後は：・平面に埋め込んだ木や、木以外のグラフオブジェクトも（簡単なアイディアで）列挙したい