Proper Interval Graphsの ランダム生成と列挙

Presentation on theme: "Proper Interval Graphsの ランダム生成と列挙"— Presentation transcript:

1 Proper Interval Graphsの ランダム生成と列挙
○斎藤　寿樹(JAIST) 　 山中　克久(電気通信大) 　 清見　 礼(JAIST)(祝・結婚) 　上原　隆平(JAIST)

2 問題（１） 連結なProper Interval Graphのランダム生成 入力：自然数 n
出力：n頂点の連結なProper Interval Graph 一様ランダムに生成 同型性を考慮 例　n=5

3 問題（２） すべて出力 連結なProper Interval Graphの列挙 入力：自然数 n
出力：n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく 同型性を考慮 すべて出力 例　n=5

4 提案アルゴリズム 連結なProper Interval Graphのランダム生成 連結なProper Interval Graphの列挙
出力：n頂点の連結なProper Interval Graph 一様ガンダムに生成(同型性を考慮) 数え上げを利用 O(n+m)時間 連結なProper Interval Graphの列挙 出力：n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく（同型性を考慮） 逆探索法を利用 1つあたりO(1)時間

5 提案アルゴリズム 連結なProper Interval Graphのランダム生成 連結なProper Interval Graphの列挙
出力：n頂点の連結なProper Interval Graph 一様ランダムに生成(同型性を考慮) 数え上げを利用 O(n+m)時間 連結なProper Interval Graphの列挙 出力：n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく（同型性を考慮） 逆探索法を利用 1つあたりO(1)時間

6 Interval Graphs Interval表現を持つグラフクラス

7 Proper Interval Graphs
Unit Interval表現を持つグラフクラス すべてのIntervalの長さが同じ カッコ列を用いた表現

8 Unit Interval表現のカッコ列表現
左端点　→　“(” 右端点　→　“)” 左端点が現れる順番に右端点も現れる Unit Interval表現 ( ( ( ) ) ( ( ) ) ) ( ( ( ) ) ( ( ) ) ) カッコ列表現

9 カッコ列表現 ( ( ( ) ) ( ( ) ) ) n頂点のProper Interval Graphのカッコ列表現の特徴 1 2 3 2
“(”の数：n個　　　　“)”の数：n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ( ) ) ( ( ) ) ) +1 +1 +1 -1 -1 +1 +1 -1 -1 -1 1 2 3 2 1 2 3 2 1

10 カッコ列表現 ( ( ) ) ) ( n頂点のProper Interval Graphのカッコ列表現の特徴 カッコの数：2n
“(”の数：n個　　　　“)”の数：n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ) ) ) ( ？ Interval表現が書けない

11 カッコ列表現 ( ( ) ) ( ) n頂点のProper Interval Graphのカッコ列表現の特徴 カッコの数：2n
“(”の数：n個　　　　“)”の数：n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ) ) ( ) Unit Interval表現 グラフ表現

12 カッコ列表現 ( ( ( ( ) ) ) ( ( ) ) ) ) 連結なProper Interval Graphのカッコ列表現
左カッコと右カッコの数が等しいのは2箇所 左端と右端のみ 両端を除いたカッコ列がnon-negative ( ( ( ( ) ) ) ( ( ) ) ) )

13 カッコ列表現 Lemma 1. (X. Dell, P. Hell, J. Huang, 1996)
連結なProper Interval Graphは1つ、または2つのカッコ列表現を持つ このグラフは2つのカッコ列表現しかもたない ( ( ) ( ( ) ( ) ) ) ( ( ) ( ( ) ( ) ) ) 異なるカッコ列 Proper Interval Graph Unit Interval表現 カッコ列表現

14 カッコ列表現 Lemma 1. (X. Dell, P. Hell, J. Huang, 1996)
連結なProper Interval Graphは1つ、または2つのカッコ列表現を持つ このグラフは1つのカッコ列表現しかもたない ( ( ) ( ( ) ) ( ) ) ( ( ) ( ( ) ) ( ) ) カッコ列表現 Proper Interval Graph Unit Interval表現 reversible

15 ランダム生成アルゴリズム ( ( ( ( ) ) ( ) ( ) ) ) カッコ列をランダムに生成
Proper Interval Graphの数え上げを利用 一様ランダムにカッコ列を生成することができる ( ( ( ( ) ) ( ) ( ) ) ) reversibleなカッコ列に対応するグラフの出現確率が低い

16 生起確率の正規化 … … Case 1 … … … Case 2 … 一様にグラフを出力 … ( ( ) ( ( ) ( ) ) )
Sn: reversibleでないカッコ列の数 Rn: reversibleなカッコ列の数 せ　い　き　　か　く　り　つ せ　い　　き　　か non-negativeなカッコ列 reversibleでないカッコ列 … ( ( ) ( ( ) ( ) ) ) ( ( ( ) ( ) ) ( ) ) … Case 1 … reversibleなカッコ列 … ( ( ) ( ( ) ) ( ) ) … Case 2 … ( ( ) ( ( ) ) ( ) ) 一様にグラフを出力 …

17 ランダム生成 ( ( ( ) ) ( ( ) ( ) ) ) Case 1（一様ランダムなカッコ列） 構築時間
カタラン数の一般化 Case 1（一様ランダムなカッコ列） 左から順にカッコを一つずつ生成 確率に応じて, “(” と “)” のどちらかを選択 ( ( ( ) ) ( ( ) ( ) ) ) “(” : “)” : p = C(2n’ - k, hl) q = C(2n’ - k, hr) 構築時間 カッコ列：O(n) グラフ：O(n+m) k:生成したカッコの数 h:高さ

18 ランダム生成 ) ) ( ) ) ) ) ( ) ) ) ) Case 2（ reversibleなカッコ列） 構築時間
真ん中の高さを決める 左から順にカッコを一つずつ生成 確率に応じて, “(” と “)” のどちらかを選択 ) ) ( ) ) ) ) ( ) ) ) ) p = C(n’ - k, hl) “(” : “)” : q = C(n’ - k, hr) 構築時間 カッコ列：O(n) グラフ：O(n+m) k:生成したカッコの数 h:高さ

19 まとめ・今後の課題 n頂点のProper Interval Graphのランダム生成と列挙 Interval Graphのランダム生成と列挙
ランダム生成：O(n+m)時間 列挙：１つあたりO(1)時間 高々n頂点に拡張できる Interval Graphのランダム生成と列挙