Proper Interval Graphsの ランダム生成と列挙 ○斎藤 寿樹(JAIST) 山中 克久(電気通信大) 清見 礼(JAIST)(祝・結婚) 上原 隆平(JAIST)
問題(1) 連結なProper Interval Graphのランダム生成 入力:自然数 n 出力:n頂点の連結なProper Interval Graph 一様ランダムに生成 同型性を考慮 例 n=5
問題(2) すべて出力 連結なProper Interval Graphの列挙 入力:自然数 n 出力:n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく 同型性を考慮 すべて出力 例 n=5
提案アルゴリズム 連結なProper Interval Graphのランダム生成 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graph 一様ガンダムに生成(同型性を考慮) 数え上げを利用 O(n+m)時間 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく(同型性を考慮) 逆探索法を利用 1つあたりO(1)時間
提案アルゴリズム 連結なProper Interval Graphのランダム生成 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graph 一様ランダムに生成(同型性を考慮) 数え上げを利用 O(n+m)時間 連結なProper Interval Graphの列挙 出力:n頂点の連結なProper Interval Graphを列挙 漏れなく、重複なく(同型性を考慮) 逆探索法を利用 1つあたりO(1)時間
Interval Graphs Interval表現を持つグラフクラス
Proper Interval Graphs Unit Interval表現を持つグラフクラス すべてのIntervalの長さが同じ カッコ列を用いた表現
Unit Interval表現のカッコ列表現 左端点 → “(” 右端点 → “)” 左端点が現れる順番に右端点も現れる Unit Interval表現 ( ( ( ) ) ( ( ) ) ) ( ( ( ) ) ( ( ) ) ) カッコ列表現
カッコ列表現 ( ( ( ) ) ( ( ) ) ) 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
カッコ列表現 ( ( ) ) ) ( n頂点のProper Interval Graphのカッコ列表現の特徴 カッコの数:2n “(”の数:n個 “)”の数:n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ) ) ) ( ? Interval表現が書けない
カッコ列表現 ( ( ) ) ( ) n頂点のProper Interval Graphのカッコ列表現の特徴 カッコの数:2n “(”の数:n個 “)”の数:n個 non-negative 左からスイープしたとき、どの地点を見ても、左カッコの数は右カッコの数よりも多いか等しい ( ( ) ) ( ) Unit Interval表現 グラフ表現
カッコ列表現 ( ( ( ( ) ) ) ( ( ) ) ) ) 連結なProper Interval Graphのカッコ列表現 左カッコと右カッコの数が等しいのは2箇所 左端と右端のみ 両端を除いたカッコ列がnon-negative ( ( ( ( ) ) ) ( ( ) ) ) )
カッコ列表現 Lemma 1. (X. Dell, P. Hell, J. Huang, 1996) 連結なProper Interval Graphは1つ、または2つのカッコ列表現を持つ このグラフは2つのカッコ列表現しかもたない ( ( ) ( ( ) ( ) ) ) ( ( ) ( ( ) ( ) ) ) 異なるカッコ列 Proper Interval Graph Unit Interval表現 カッコ列表現
カッコ列表現 Lemma 1. (X. Dell, P. Hell, J. Huang, 1996) 連結なProper Interval Graphは1つ、または2つのカッコ列表現を持つ このグラフは1つのカッコ列表現しかもたない ( ( ) ( ( ) ) ( ) ) ( ( ) ( ( ) ) ( ) ) カッコ列表現 Proper Interval Graph Unit Interval表現 reversible
ランダム生成アルゴリズム ( ( ( ( ) ) ( ) ( ) ) ) カッコ列をランダムに生成 Proper Interval Graphの数え上げを利用 一様ランダムにカッコ列を生成することができる ( ( ( ( ) ) ( ) ( ) ) ) reversibleなカッコ列に対応するグラフの出現確率が低い
生起確率の正規化 … … Case 1 … … … Case 2 … 一様にグラフを出力 … ( ( ) ( ( ) ( ) ) ) Sn: reversibleでないカッコ列の数 Rn: reversibleなカッコ列の数 せ い き か く り つ せ い き か non-negativeなカッコ列 reversibleでないカッコ列 … ( ( ) ( ( ) ( ) ) ) ( ( ( ) ( ) ) ( ) ) … Case 1 … reversibleなカッコ列 … ( ( ) ( ( ) ) ( ) ) … Case 2 … ( ( ) ( ( ) ) ( ) ) 一様にグラフを出力 …
ランダム生成 ( ( ( ) ) ( ( ) ( ) ) ) Case 1(一様ランダムなカッコ列) 構築時間 カタラン数の一般化 Case 1(一様ランダムなカッコ列) 左から順にカッコを一つずつ生成 確率に応じて, “(” と “)” のどちらかを選択 ( ( ( ) ) ( ( ) ( ) ) ) “(” : “)” : p = C(2n’ - k, hl) q = C(2n’ - k, hr) 構築時間 カッコ列:O(n) グラフ:O(n+m) k:生成したカッコの数 h:高さ
ランダム生成 ) ) ( ) ) ) ) ( ) ) ) ) Case 2( reversibleなカッコ列) 構築時間 真ん中の高さを決める 左から順にカッコを一つずつ生成 確率に応じて, “(” と “)” のどちらかを選択 ) ) ( ) ) ) ) ( ) ) ) ) p = C(n’ - k, hl) “(” : “)” : q = C(n’ - k, hr) 構築時間 カッコ列:O(n) グラフ:O(n+m) k:生成したカッコの数 h:高さ
まとめ・今後の課題 n頂点のProper Interval Graphのランダム生成と列挙 Interval Graphのランダム生成と列挙 ランダム生成:O(n+m)時間 列挙:1つあたりO(1)時間 高々n頂点に拡張できる Interval Graphのランダム生成と列挙