Document

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

Download Report