Document

Bipartite Permutation Graphの
ランダム生成と列挙
○斎藤
大舘
山中
上原
寿樹(JAIST)
陽太(群馬大)
克久(電気通信大)
隆平(JAIST)
背景
計算機実験
入力

出力
入力のグラフ


Interval Graph
Permutation Graph
[Saitoh et. al 08]
Proper Interval Graph
Bipartite Permutation Graph

ランダム生成・列挙
数え上げ
提案アルゴリズム

連結なBipartite Permutation Graphのランダム生成


入力：自然数 n
出力：n頂点の連結なBipartite Permutation Graph




一様ランダムに生成(同型性を考慮)
数え上げを利用
O(n+m)時間
連結なBipartite Permutation Graphの列挙


入力：自然数 n
出力：n頂点の連結なBipartite Permutation Graphを列挙



漏れなく、重複なく（同型性を考慮）
逆探索法を利用
1つあたりO(1)時間
Permutation Graph

ライン表現を持つグラフクラス
1
2
3
4
5
6
1
6
4
3
3
6
4
1 5
ライン表現
2
2
5
Permutation Graph
Bipartite Permutation Graph

Bipartite Graph かつ Permutation Graph
1
2
3
4
5
6
7
8
3
5
6 1 2 8
ライン表現
4
7
6
3
4
2
1
8
7
5
Bipartite Permutation Graph
ランダム生成や列挙を行う
Bipartite Permutation Graph

補題
連結なBipartite Permutation Graphのライン表現は
Xの頂点に対応する線分（青線）：左上から右下へ
Yの頂点に対応する線分（赤線）：右上から左下へ
1
12
03
41 50 60 71 80
13
15
61 01 20 81 40 70
ライン表現
6
3
4
2
1
8
7
5
Bipartite Permutation Graph
0と1の文字列で，ライン表現を表せる
文字列 ⇒ パス

ライン表現を左からスイープ



ラインを上下交互に見る
1 ⇒ 右に1、上に1
0 ⇒ 右に1、下に1
1
1
0
1
0
1
1
0
0
0
0
(0, 0)
n頂点のBipartite Permutation Graph

パスの特徴

最後の座標は(2n, 0)


上でn個, 下でn個
1と0の数が等しい



1 1 0 1 0 1 0
1 1 0 0 0 1 0
上で1は下で0, 上で0は下で1
x軸より上
y座標が0で囲まれた領域が
コンポーネントに対応
0
(0, 0)
(2n, 0)
n頂点の連結なBipartite Permutation Graph

1 1 0 1 0 0 1 0
パスの特徴

最後の座標は(2n, 0)


上でn個, 下でn個
1と0の数が等しい



1 1 1 0 0 1 0 0
上で1は下で0, 上で0は下で1
x軸より上
(0, 0)と(2n, 0)を除くとy座標は1以上
1
0
n頂点の連結なBipartite Permutation Graph

1 1 0 1 0 0 1 0
パスの特徴

最後の座標は(2n, 0)


上でn個, 下でn個
1と0の数が等しい



1 1 1 0 0 1 0 0
上で1は下で0, 上で0は下で1
x軸より上
(0, 0)と(2n, 0)を除くとy座標は1以上
Dyckパス
(長さ2n-2)
1
Dyckパスを一様ランダムに生成すればよい？
ダメな理由


Bipartite Permutation Graphとライン表現は
1対1対応ではない
グラフによって対応するライン表現の数が
異なる
対応するライン表現
1
6
3

補題

4
2
8
5
連結なBipartite Permutation Graphはライン表現を高々４つ持つ
1 2 3 4 5 6 7 8
3 5 6 1 2 8 4 7
左右反転
回転
8 7 6 5 4 3 2 1
7 4 8 2 1 6 5 3
上下
反転
上下反転
この４つのライン表現しか持たない
3 5 6 1 2 8 4 7
1 2 3 4 5 6 7 8
左右反転
7 4 8 2 1 6 5 3
8 7 6 5 4 3 2 1
7
6
対応するライン表現

1
3
2
7
4
5
すべてのBipartite Permutation Graphが4つの
ライン表現を持つわけではない
1 2 3 4 5 6 7 8
左右対称
左右反転
4 6 1 2 7 8 3 5
18 27 3
6 45 54 63 72 81
54 36 81 72 27 18 63 4
5
上下反転
上下 2つのライン表現しかもたない
反転
左右対称
8
対応するライン表現

すべてのBipartite Permutation Graphが4つの
ライン表現を持つわけではない
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
4 5 7 1 2 8 3 6
4 1 5 6 8 2 3 7
回転対称なライン表現
上下対称なライン表現
2つのライン表現しかもたない
対応するライン表現

すべてのBipartite Permutation Graphが4つの
ライン表現を持つわけではない
1 2 3 4 5 6 7 8
1対1
3 5 1 7 2 8 4 6
上下・左右・回転対称なライン表現
3
2
7
6
1
5
4
8
Bipartite Permutation Graph
ライン表現を一様ランダムに生成
ライン表現
左右対称上下左右回転対称
回転対称
上下対称
ライン表現を一様ランダムに生成すると
ライン表現を4つ持つグラフが生成されやすい！
ライン表現を一様ランダムに生成
ライン表現
左右対称上下左右回転対称
回転対称
上下対称
解決するために
ライン表現を複数持つグラフの生成確率を下げる
標準形のみを生成する
うまくいかない！
生起確率の正規化
ライン表現
左右対称上下左右回転対称
回転対称
上下対称
左右対称上下左右
回転対称
上下対称上下左右
回転対称上下左右
回転対称
対応する数が等しい
回転対称
生起確率の正規化
ライン表現
左右対称上下左右回転対称
回転対称
上下対称
左右対称上下左右
回転対称
上下対称上下左右
回転対称上下左右
回転対称
数を数えればよい
回転対称
数え上げ

ライン表現全体

長さ2n-2のDyckパス
長さ2n-2のDyckパスの数=C(n-1)
カタラン数：
C (n) 
1  2n 
 
n 1  n 
1
0
数え上げ

回転対称


長さ2n-2のDyckパス
Dyckパスが左右対称
長さ2n-2で左右対称
なDyckパスの数
回転対称なライン表現
n 1 


 
 ( n  1) / 2 
1
数え上げ
1 1 1 0 0 1 0 0

上下対称


上の文字列と下の文字
列が等しい
長さn-2のDyckパス
1 1 1 0 0 1 0 0
上下対称なライン表現
長さn-2のDyckパスの数=C(n/2-1)
1
上原財団による懸賞問題
数え上げ

回転対称と対応
1 1 1 0 1 0 0 0
左右対称

回転対称と対応

2-Motzkinパスと対応
1 1 0 0 1 1 0 0
 n 1 
左右対称なライン表現

左右対称の数  回転対称の数  
 (n  1) / 2 
1 1 1 0 1 1 0 0
1 1 0 0 1 0 0 0
回転対称なライン表現
1
生起確率の正規化
ライン表現
左右対称上下左右回転対称
回転対称
上下対称
左右対称上下左右上下対称上下左右回転対称
回転対称
回転対称
ランダム生成アルゴリズム
1. これら4つの中からどれかを選択
2. 選択したものをランダムに生成
上下左右
回転対称
まとめと今後の課題

連結なn頂点のBipartite Permutation Graph




ランダム生成：O(n+m)時間
列挙：O(1)時間/Graph
Permutation Graphのランダム生成と列挙
Interval Graphのランダム生成と列挙

Download Report