グラフの列挙 中野　眞一　　　 （群馬大学） 2019/9/14 列挙学校.

Presentation on theme: "グラフの列挙 中野　眞一　　　 （群馬大学） 2019/9/14 列挙学校."— Presentation transcript:

1 グラフの列挙 中野　眞一　　　 （群馬大学） 2019/9/14 列挙学校

2 列挙アルゴリズム設計技法 ・（新種発見） いつ終わる？ ・分割探索 タイプごとに ・辞書（Gray） 順番に ・逆探索 親戚関係で ・家系木
・（新種発見） いつ終わる？　 ・分割探索 タイプごとに　　　　　　　　　　 ・辞書（Gray） 順番に ・逆探索 親戚関係で ・家系木 ・etc. 2019/9/14 列挙学校

3 グラフのクラス ・木 　 ・平面グラフ　　　　　　　　　　 ・矩形描画 2019/9/14 列挙学校

4 木に関する用語 家系図とみなす 親、子、兄弟、先祖、子孫 根 点の高さ、深さ 　　　根は深さ０ 　　　葉は高さ０ 葉 2019/9/14 列挙学校

5 木 ・根つき木 or 自由木 ・順序木 or 順序なし木 ・子の個数 任意 or ちょうど２ or 高々2 or 少なくとも２ 対応 長男
すぐ下の弟 2019/9/14 列挙学校

6 木の列挙（辞書法） ・根つき順序木 ・深さ優先横断(downとupを記録) DUDUDDUDUDUUDU m辺の木を2m文字に符号化
・根つき順序木　　　　　　　　　 ・深さ優先横断(downとupを記録) DUDUDDUDUDUUDU m辺の木を2m文字に符号化　　　　　　　　　 2019/9/14 列挙学校

7 木の列挙（辞書法） ・５辺の順序木の辞書 　に最初に掲載されている木は？　　　　　　　　　 DDUDUDUU DDDUDUUU 2019/9/14 列挙学校

8 木の列挙（辞書法） ・５辺の順序木の辞書 に最初に掲載されている木は？ DDDDDUUUUU ・2番目の木は？ ・３番目の木は？
　に最初に掲載されている木は？　　　　　　　　　 DDDDDUUUUU ・2番目の木は？ ・３番目の木は？ ・次は？次は？　　　　　　　　　 2019/9/14 列挙学校

9 木の列挙（辞書法） ・５辺の順序木の辞書 DDDDDUUUUU DDDDUDUUUU DDDDUUDUUU DDDDUUUDUU
・５辺の順序木の辞書　　　　　　　　 DDDDDUUUUU DDDDUDUUUU DDDDUUDUUU DDDDUUUDUU DDDDUUUUDU DDDDUUUUUD だめ 2019/9/14 列挙学校

10 木の列挙（辞書法） ・５辺の順序木の辞書 DDDDDUUUUU DDDDUDUUUU DDDDUUDUUU DDDDUUUDUU
・５辺の順序木の辞書　　　　　　　　 DDDDDUUUUU DDDDUDUUUU DDDDUUDUUU DDDDUUUDUU DDDDUUUUDU DDDDUUUUUD だめ( ( ( ( ) ) ) ) ) ( U??? D D U D U U 2019/9/14 列挙学校

11 演習１ ・５辺の順序木の辞書を完成せよ ・ｍ辺の順序木の辞書を出力する アルゴリズムを設計せよ
　アルゴリズムを設計せよ ・ｍ辺かつL葉の順序木の列挙アルゴ　　　　　リズムを設計せよ ・ｍ辺かつ高さがｈの順序木の列挙アルゴリズムを設計せよ　　　　　　　　 2019/9/14 列挙学校

12 演習２ ・５辺の順序なし木の辞書を完成せよ ・ｍ辺の順序なし木の辞書を出力する アルゴリズムを設計せよ
　アルゴリズムを設計せよ ・ｍ辺かつL葉の順序なし木の列挙アルゴリズムを設計せよ ・ｍ辺かつ高さがｈの順序なし木の列挙アルゴリズムを設計せよ　　　　　　　　 2019/9/14 列挙学校

13 演習３ ・幅優先横断(子の個数を記録) 11110001110000 ・順序木の他の符号化法を設計せよ ・その符号に基づき順序木の辞書
・その符号に基づき順序木の辞書　 　を出力するアルゴリズム 　を設計せよ　　　　　　　 ・幅優先横断(子の個数を記録) 　　　　　　　　　　　 2019/9/14 列挙学校

14 もっと学びたい方へ The Art of Computer Programming,
                  The Art of Computer Programming, Fascicle 4: Generating All Trees -- History of Combinatorial Generation (Art of Computer Programming) Donald E. Knuth (2006/2/14)　Addison-Wesley　$19.99 　ISBN-10: 　 2019/9/14 列挙学校

15 木の列挙（家系木法） ・根つき順序木　　　　　　　　　 2019/9/14 列挙学校

16 木の列挙（家系木法） ・高々ｍ辺の 　順序木の 　集合には 　木の構造 　がある　　　　　　 ・深さｋ　 　ｋ辺の木　　　　　 2019/9/14 列挙学校

17 木の列挙（家系木法） 指定した 木の子を 再帰的に 列挙する　　　　　　 ・深さｋ　 　ｋ辺の木　　　　　 2019/9/14 列挙学校

18 順序木の列挙（家系木法） Shin-ichi Nakano "Efficient Generation of Plane Trees“ Information Processing Letters, Vol.84, no. 3, pp (2002). 子のリスト 親 2019/9/14 列挙学校

19 順序なし木の列挙（家系木法） Left Heavy のみ列挙 Left Heavy ？
Shin-ichi Nakano and Takeaki Uno, “Constant Time Generation of Trees with Specified Diameter”, Proc. of WG 2004　LNCS, 3353, pp (2004). Left Heavy のみ列挙 Left Heavy ？ 2019/9/14 列挙学校

20 演習４ ・Left Heavyを定式化せよ ・Left Heavyな順序木を列挙するアルゴリズムを設計せよ （順序なし木の列挙）
　（順序なし木の列挙）　　　　　　　 2019/9/14 列挙学校

21 （内部）極大平面グラフ ・内面がすべて三角 ・３Dワイヤモデル 外点 ｒ個 内点 ｖ個の グラフをすべて 列挙せよ 2019/9/14
外点　ｒ個 内点　ｖ個の グラフをすべて 列挙せよ 2019/9/14 列挙学校

22 極大平面グラフ　　対角スイッチ 2019/9/14 列挙学校

23 極大平面グラフ 対角スイッチ d c b v a ・点vの回りに ４点a,b,c,dがある ・辺vb もしくは vc は対角スイッチ できる
極大平面グラフ　　対角スイッチ ・点vの回りに 　４点a,b,c,dがある ・辺vb もしくは　vc は対角スイッチ できる ・Wagner定理[1936] 任意の２つの 極大平面グラフは 対角スイッチのみで互いに変換可能 d c b v a 2019/9/14 列挙学校

24 極大平面グラフ 対角スイッチ ・外面上の点vが４次以上のとき 対角スイッチでvの次数を減らす d d c c b b v v a a
極大平面グラフ　　対角スイッチ ・外面上の点vが４次以上のとき 　対角スイッチでvの次数を減らす　　　　　 d d c c b b v v a a 2019/9/14 列挙学校

25 ？ 極大平面グラフ 対角スイッチ ・外面上の点vが４次以上のとき 対角スイッチでvの次数を減らす 3次 3次 3次 3次 3次 3次 3次
極大平面グラフ　　対角スイッチ ・外面上の点vが４次以上のとき 　対角スイッチでvの次数を減らす　　　　　 3次 3次 3次 3次 ？ 3次 3次 3次 ?次 ?次 2019/9/14 列挙学校

26 ？ 極大平面グラフ 対角スイッチ ・外面上の点vが４次以上のとき 対角スイッチでvの次数を減らす 3次 3次 3次 3次 3次 3次 a
極大平面グラフ　　対角スイッチ ・外面上の点vが４次以上のとき 　対角スイッチでvの次数を減らす　　　　　 3次 3次 3次 3次 ？ 3次 3次 a 3次 ?次 ?次 2019/9/14 列挙学校

27 極大平面グラフ　　対角スイッチ ・外面上の点vが４次以上のとき 　対角スイッチでvの次数を減らす　　　　　 a 2019/9/14 列挙学校

28 極大平面グラフ　　対角スイッチ 最後の処理　　　　　 2019/9/14 列挙学校

29 極大平面グラフ　　対角スイッチ 任意の外点r個　内点ｖ個のグラフ　　　　　 根　　　　 2019/9/14 列挙学校

30 極大平面グラフの列挙 カノニカル順序 対角スイッチ+Wagner定理 Avis 96 O(n2) 時間/each
カノニカル順序　　　　　 Avis 96 O(n2) 時間/each Li & Nakano 01 O(1) 時間/each 2019/9/14 列挙学校

31 極大平面グラフのカノニカル順序 7 7 6 6 6 6 4 4 4 4 4 4 5 5 5 3 3 3 1 2 1 2 1 2 4 家系木 4 3 3 1 2 1 2 2019/9/14 列挙学校

32 演習5 直径ｋ 葉L個のキャタピラ （葉をすべて除くとパスになる木） を列挙するアルゴリズムを設計せよ 根なしに注意
(Kikuchi他 COCOON 03)　　　　　　 2019/9/14 列挙学校

33 フロアプラン ・すべての面が四角形 ・回転 同じ or 異なる ・４次点 あり or なし ・面積関係なし 左の２つの図は
90度 回転 ・すべての面が四角形 ・回転　　同じ　or 異なる ・４次点　　あり　or なし ・面積関係なし 左の２つの図は 矩形分割としては同じ フロアプランとしては異なる 上と同じ ４次点 2019/9/14 列挙学校

34 フロアプランの左上の面を順次除去 家系木　　　　　　 2019/9/14 列挙学校

35 フロアプランの左上の面を順次除去 親　　　　　　 子のリスト　　　　　　 2019/9/14 列挙学校

36 フロアプランの家系木 （S.Yoshii 2002 図) 2019/9/14 列挙学校

37 演習6 (Nakano ISAAC 01) 内面の個数がｎのフロアプラン を列挙するアルゴリズムを設計せよ O(1)時間/each
2019/9/14 列挙学校

38 フロアプランの列挙（回転を同じとする場合）
家系木　　　　　　 ９０度回転で得られる４つフロアプランの内１つのみを出力　　　　　　 2019/9/14 列挙学校

39 演習7 内面の個数がｎのフロアプラン を列挙するアルゴリズムを設計せよ ただし、９０度回転で得られる ４つのフロアプランは同一とみなす
O(n)時間/each （Nakano ISAAC 01)　　　　　　 2019/9/14 列挙学校

40 一様ランダム生成（順序木） 大量メモリ＋前処理 なら簡単 一覧辞書＋乱数でＯＫ メモリ小かつ前処理なしで 一様ランダム生成したい。。。
大量メモリ＋前処理　なら簡単 　　　　　一覧辞書＋乱数でＯＫ メモリ小かつ前処理なしで 一様ランダム生成したい。。。 2019/9/14 列挙学校

41 一様ランダム生成（順序木） Dyckパス　　　　　 2019/9/14 列挙学校

42 一様ランダム生成（順序木） サイクルシフト ・ｍ辺の順序木はm+1個の Dとm個のUの文字列に対応する
サイクルシフト　　　　　 ・ｍ辺の順序木はm+1個の　Dとm個のUの文字列に対応する ・各文字列をサイクルシフトして得られる2m+1個の文字列のうち１個だけが順序木に対応する 2019/9/14 列挙学校

43 順序木 サイクルシフト ３文字シフト 順序木に対応 ４文字シフト １文字シフト ５文字シフト ２文字シフト ６，７，８文字シフト
順序木　　サイクルシフト ３文字シフト 順序木に対応 ４文字シフト １文字シフト ５文字シフト ２文字シフト ６，７，８文字シフト 2019/9/14 列挙学校

44 順序木 サイクルシフト ・m+1個のDとm個のUの文字列を一様ランダム生成 ・サイクルシフトして得られる１個を選ぶ ・順序木として出力
順序木　サイクルシフト ・m+1個のDとm個のUの文字列を一様ランダム生成 ・サイクルシフトして得られる１個を選ぶ ・順序木として出力 選択 選択 ・1,2,…,2m+1の順列を一様ランダム生成 ・1,2,..m+1をDに, 他をUに 置き換え 選択 2019/9/14 列挙学校

45 演習8 m 辺 かつ L 葉の 順序木を一様ランダムに生成する アルゴリズムを設計せよ （理系への数学 ２００８年７月号掲載予定 中野）
（理系への数学　２００８年７月号掲載予定　中野） 2019/9/14 列挙学校

46 演習∞ 高速に列挙できる対象を列挙せよ 高速に一様ランダム生成できる対象を列挙せよ 2019/9/14 列挙学校