Bipartite Permutation Graphの ランダム生成と列挙

Presentation on theme: "Bipartite Permutation Graphの ランダム生成と列挙"— Presentation transcript:

1 Bipartite Permutation Graphの ランダム生成と列挙
○斎藤　寿樹(JAIST) 　 大舘　陽太(群馬大) 　 山中　克久(電気通信大) 　 上原　隆平(JAIST)

2 背景 入力のグラフ Interval Graph Permutation Graph Proper Interval Graph
計算機実験 入力 出力 入力のグラフ Interval Graph Permutation Graph [Saitoh et. al 08] Proper Interval Graph Bipartite Permutation Graph ランダム生成・列挙 数え上げ

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

4 Permutation Graph ライン表現を持つグラフクラス 1 2 3 4 5 6 3 6 4 1 5 2
1 6 4 3 2 5 Permutation Graph ライン表現

5 Bipartite Permutation Graph
Bipartite Graph かつ Permutation Graph 1 6 3 4 8 7 2 5 Bipartite Permutation Graph ライン表現 ランダム生成や列挙を行う

6 Bipartite Permutation Graph
補題 連結なBipartite Permutation Graphのライン表現は Xの頂点に対応する線分（青線）：左上から右下へ Yの頂点に対応する線分（赤線）：右上から左下へ 1 6 3 4 8 7 2 5 Bipartite Permutation Graph ライン表現 0と1の文字列で，ライン表現を表せる

7 文字列 ⇒ パス ライン表現を左からスイープ ラインを上下交互に見る 1 ⇒ 右に1、上に1 0 ⇒ 右に1、下に1 1 1 0 1 0
文字列　⇒　パス ライン表現を左からスイープ ラインを上下交互に見る 1　⇒　右に1、上に1 0　⇒　右に1、下に1 (0, 0)

8 n頂点のBipartite Permutation Graph
パスの特徴 最後の座標は(2n, 0) 上でn個, 下でn個 1と0の数が等しい 上で1は下で0, 上で0は下で1 x軸より上 y座標が0で囲まれた領域がコンポーネントに対応 (2n, 0) (0, 0)

9 n頂点の連結なBipartite Permutation Graph
パスの特徴 最後の座標は(2n, 0) 上でn個, 下でn個 1と0の数が等しい 上で1は下で0, 上で0は下で1 x軸より上 (0, 0)と(2n, 0)を除くとy座標は1以上 1

10 n頂点の連結なBipartite Permutation Graph
パスの特徴 最後の座標は(2n, 0) 上でn個, 下でn個 1と0の数が等しい 上で1は下で0, 上で0は下で1 x軸より上 (0, 0)と(2n, 0)を除くとy座標は1以上 Dyckパス(長さ2n-2) 1 Dyckパスを一様ランダムに生成すればよい？

11 ダメな理由 Bipartite Permutation Graphとライン表現は1対1対応ではない
グラフによって対応するライン表現の数が異なる

12 対応するライン表現 この４つのライン表現しか持たない 補題 1 2 3 4 5 6 7 8 3 5 6 1 2 8 4 7
連結なBipartite Permutation Graphはライン表現を高々４つ持つ 左右反転 回転 上下 反転 この４つのライン表現しか持たない 上下 反転 左右反転

13 対応するライン表現 2つのライン表現しかもたない
1 2 6 7 8 3 4 5 すべてのBipartite Permutation Graphが4つのライン表現を持つわけではない 左右対称 左右反転 2つのライン表現しかもたない 上下 反転 上下 反転 左右対称

14 対応するライン表現 2つのライン表現しかもたない
すべてのBipartite Permutation Graphが4つのライン表現を持つわけではない 上下対称なライン表現 回転対称なライン表現 2つのライン表現しかもたない

15 対応するライン表現 すべてのBipartite Permutation Graphが4つのライン表現を持つわけではない
1対1 1 2 3 4 5 6 7 8 Bipartite Permutation Graph 上下・左右・回転対称なライン表現

16 ライン表現を一様ランダムに生成 ライン表現を4つ持つグラフが生成されやすい！ ライン表現 ライン表現を一様ランダムに生成すると 左右対称
上下左右 回転対称 回転対称 上下対称 ライン表現を一様ランダムに生成すると ライン表現を4つ持つグラフが生成されやすい！

17 ライン表現を一様ランダムに生成 うまくいかない！ ライン表現 解決するために ライン表現を複数持つグラフの生成確率を下げる
左右対称 上下左右 回転対称 回転対称 上下対称 解決するために ライン表現を複数持つグラフの生成確率を下げる 標準形のみを生成する うまくいかない！

18 生起確率の正規化 対応する数が等しい ライン表現 左右対称 回転対称 上下対称 左右対称 上下対称 回転対称 上下左右 回転対称

19 生起確率の正規化 数を数えればよい ライン表現 左右対称 回転対称 上下対称 左右対称 上下対称 回転対称 上下左右 回転対称

20 数え上げ ライン表現全体 長さ2n-2のDyckパス 長さ2n-2のDyckパスの数=C(n-1) 1

21 数え上げ 回転対称 長さ2n-2のDyckパス Dyckパスが左右対称 回転対称なライン表現 長さ2n-2で左右対称なDyckパスの数 1

22 数え上げ 上下対称 長さn-2のDyckパスの数=C(n/2-1) 上の文字列と下の文字列が等しい 長さn-2のDyckパス
上下対称 上の文字列と下の文字列が等しい 長さn-2のDyckパス 上下対称なライン表現 長さn-2のDyckパスの数=C(n/2-1) 1

23 数え上げ 左右対称 回転対称と対応 回転対称と対応 上原財団による懸賞問題 1 1 1 0 1 0 0 0 2-Motzkinパスと対応
左右対称 回転対称と対応 2-Motzkinパスと対応 左右対称なライン表現 回転対称なライン表現 1

24 生起確率の正規化 ライン表現 ランダム生成アルゴリズム 1. これら4つの中からどれかを選択 2. 選択したものをランダムに生成 左右対称
上下左右 回転対称 回転対称 上下対称 左右対称 上下左右 回転対称 上下左右 回転対称 回転対称 上下左右 回転対称 上下対称 ランダム生成アルゴリズム 1. これら4つの中からどれかを選択 2. 選択したものをランダムに生成

25 まとめと今後の課題 連結なn頂点のBipartite Permutation Graph
ランダム生成：O(n+m)時間 列挙：O(1)時間/Graph Permutation Graphのランダム生成と列挙 Interval Graphのランダム生成と列挙