Document

コードレスサイクルを列挙する
線形時間アルゴリズム
宇野毅明
情報学研究所
2003年11月7日アルゴリズム研究会
結果
・与えられたグラフのコードレスサイクルを列挙するアルゴリズ
ムを構築した
（コードレスサイクル：ショートカットのないサイクル
・コードレスサイクル１つあたりの計算時間は、グラフの大きさ
に線形
・計算実験で、実際の計算時間は１つあたり、定数～頂点数で
あることを示した
（ついでにコードレスサイクルの数も調べた）
問題：コードレスサイクルの列挙
問題：与えられたグラフ G = ( V, E ) のコードレスサイクル
を列挙せよ
パス
コード
コードレスサイクル
このグラフの全コードレ
スサイクルを見つける
応用
化学構造の解析
・コードレスサイクル＝極小な環構造
・化学シフト値の予測において予測精度の向上に寄与
（局所的な環構造情報が似ているものを検索して予測）
その他
・サイクルより数が少ないため、トラクタブルなモデル
・サイクルによるモデル化をコードレスサイクルで置き換え
る？
パス／サイクル列挙の既存研究
2頂点 s と t を結ぶパスの列挙： 72年にRead＆Tarjan
・ 1つあたり O(|V|+|E|) 時間（出力数線形）
サイクルの列挙： 72年にRead＆Tarjan
・ s-t パスの列挙を用いて行う
1つあたり O(|V|+|E|) 時間（出力数線形）
s
t
このグラフの（シンプルな）
全ての s-t パスを見つける
記法
グラフ G、頂点集合 S に対し
G＼S： G から S の頂点を取ったグラフ
S
G
G＼ S
コードレスサイクルの分類１
・頂点 v を選ぶ
・ v を含まないコードレスサイクル
⇔ G＼{v} のコードレスサイクル
 再帰的に列挙できる（G＼{v} を渡す）
G＼{v}
G
v
v
コードレスサイクルの分類２
・ v に接続する枝 e=(v,t) を選ぶ
・ v と e 両方を含むコードレスサイクル
⇔ G＼{ｅ} の v-t コードレスパス
 G＼{ｅ} の v-t コードレスパスを列挙すればよい
G ＼ {ｅ }
G
v
v
e
t
t
コードレスサイクルの分類３
・ v を含むが e を含まないコードレスサイクル
⇔ G＼{t} の v を含むコードレスサイクル
 G＼{t} の v を含むコードレスサイクルを列挙すればよい
G ＼ {ｅ }
G
v
v
e
t
s-t コードレスパスの分類１
・ s と t が接続していたら、s-t コードレスパスは (s,t) のみ
N(v)：v に隣接する頂点の集合
・ s に接続する各枝 e=(s,v) を含む s-t コードレスパス
⇔ G＼(N(s)＼{v}) の v-t コードレスパス
 G＼{e} の v-t コードレスパスを列挙すればよい
G＼(N(s)＼{v})
G
s
s
e
v
t
e
v
t
分類まとめ
・コードレスサイクル
(1) v を含むコードレスサイクル
(2) （v を含まない）コードレスサイクル
・ v を含むコードレスサイクル (1) s-t コードレスパス
(2) v を含むコードレスサイクル
・コードレスパス
(1) （e を含む）コードレスパス
コードレス
サイクル
v を含むコード
レスサイクル
s-t コード
レスパス
以後、s-t コードレスパスの列挙を解説
コードレスパスの存在性
・ s の次に v を通る s-t コードレスパスが存在
⇔ G＼N(s) にv に隣接する頂点から t へのパスが存在
v
s
t
どの頂点の再帰呼び出しが空か O(|V|+|E|) 時間で判定
基本アルゴリズム
コードレスパス列挙（G, s, t ）
1. s と t が隣接するなら、（s, t）を出力して終了
2. G＼N(s) で t へ到達可能な頂点に印をつける
3. For each v∈ N(s) do
4. If v に隣接する N(s) 以外の頂点に印が付いている then
コードレスパス列挙（G＼( N(s)＼{v} ), v, t ）
5. End for
v
1反復O(|V|+|E|) ＋再帰の深さ|V|
 コードレスパス1つあたりO(|E|2)
2 以外は、v∈N(s) の次数の合計に比例
 コードレスパス1つあたり O(|V|+|E|)
s
t
アルゴリズムの式変形
・あらかじめ1つs-t コードレスパスを求めておき（親反復から受
け取り）、存在性のチェックを1回分サボる
コードレスパス列挙（G, s, t, P ）
1. s と t が隣接するなら、（s, t）を出力して終了
2. u := P での s の次の頂点
3. コードレスパス列挙（G＼( N(s)＼{u} ), u, t, P ）
4. G＼N(s) で t へ到達可能な頂点を全て調べる
5. For each v∈N(s), v≠u do
6. If G＼( N(s)＼{v} ) に v-t パスが存在 then
コードレスパス列挙（G＼( N(s)＼{v} ), s, t, P ）
7. End for
到達可能性のチェックを簡素化
・ 3 の再帰呼び出しの中で、G＼ N(s) の全ての頂点について
t への到達可能性を調べると、4 がさぼれる。
3. コードレスパス列挙（G＼( N(s)＼{u} ), u, t, P ）
4. G＼N(s) で t へ到達可能な頂点を全て調べる3.の再帰構造
これをサボる
s
u
w
t
到達可能性のチェックを簡素化
・ 3 の再帰呼び出しの中で、G＼ N(s) の全ての頂点について
t への到達可能性を調べると、4 がさぼれる。
3. コードレスパス列挙（G＼( N(s)＼{u} ), u, t, P ）
4. G＼N(s) で t へ到達可能な頂点を全て調べる3.の再帰構造
これをサボる
s
u
w
t
到達可能性のチェックを簡素化
・ 3 の再帰呼び出しの中で、G＼ N(s) の全ての頂点について
t への到達可能性を調べると、4 がさぼれる。
3. コードレスパス列挙（G＼( N(s)＼{u} ), u, t, P ）
4. G＼N(s) で t へ到達可能な頂点を全て調べる3.の再帰構造
これをサボる
消した頂点を使って行ける
所のみ調べればよい
s
u
w
t
到達可能性のチェックを簡素化
・ 3 の再帰呼び出しの中で、G＼ N(s) の全ての頂点について
t への到達可能性を調べると、4 がさぼれる。
3. コードレスパス列挙（G＼( N(s)＼{u} ), u, t, P ）
4. G＼N(s) で t へ到達可能な頂点を全て調べる3.の再帰構造
これをサボる
s
u
3. の再帰全体での計算時間が O(|V|+|E|)
w
t
アルゴリズムの再帰構造
s
a
a
c
b
d
e
d
s
g
f
c
e
g
j
t
i
e
g
f
h
f
t
h
h
i
j
i
＃青いパス＝＃コードレスパス
青いパス1つあたり O(|V|+|E|)
j
j
t
t
t
コードレスパス1つあたり O(|V|+|E|)
t
t
f
i
t
t
b
h
j
実験結果（計算時間）
・ランダムグラフを作り実験（1パターンあたり1回）
・ 1万個あたりの計算時間
100
200
400
800
1600
3200
頂点数
10%
40%
70%
80%
90%
0.17
0.18
0.17
0.2
0.24
0.29
0.09
0.09
0.09
0.13
0.13
0.19
0.09
0.09
0.10
0.13
0.21
0.25
0.10
0.11
0.15
0.26
0.29
0.61
0.12
0.17
0.26
0.54
1.30
1.79
密度
実験結果（コードレスサイクル数）
・コードレスサイクルと、普通のサイクルの数の比較
10
15
20
25
頂点数
10% 30%
50%
70% 90%
0
0
0
0
1
1
8
20
352
165
6620995
637
2099
45
3697
247
771
1775
3
4
34
1470
298
9114038
2049
81
108906
350
908
1928
密度
実験結果（コードレスサイクル数２）
・コードレスサイクル数
10%
30%
50%
70%
90%
50
64383
267435
82607
34137
18873
75
119379652 14504338
1158210
221990
73810
100
-
273504609 8269935
877466
199133
150
-
-
149022507 6641331
200
-
-
-
30334867 2466694
300
-
-
-
-
2167686
11457502
化学シフト値予測システムに組み込み
・化学シフト値：核磁気共鳴で原子核の解析をする際に得られ
る、原子の観測値の1つ
・局所的な、立体的な構造により、変化するため、化合物の構
造を解析する際に用いられる（化学シフト値から、経験と過去の
解析結果から、構造を予測する）
・化学シフト値を精度よく予測すると、立体構造を精度よく予測
できる
化学シフト値予測システムに組み込み
・ CASTシステム：佐藤寛子 (NII), 越野広雪 (理研)
立体構造も考慮した、化合物データベース
1. 化学シフト値を予測したい化合物の各原子に対して、
局所的な平面構造が等しく＆環構造が似ている
化合物の原子をデータベースから検索
2. 検索でヒットした原子の化学シフト値の平均で予測する
（環構造が類似＝各長さに対し、含まれる環の数が類似）
（局所構造のみ見たい＆全ての環を考慮すると、オーバー
フィット  コードレスサイクルが都合よい）
化学シフト値予測システムに組み込み
・実験結果
まとめと今後の展開
・グラフのコードレスサイクルを列挙する、解1つあたり入力の線形
時間のアルゴリズムを提案した
・計算実験により、ランダムグラフに対する実験的な計算時間は、
グラフが疎なら定数、密ならば頂点数に比例することを示した
・ランダムグラフではコードレスサイクル数はサイクル数に比べて
爆発的に増えないこと、密なグラフのコードレスサイクルはそれほ
ど多くないことを示した
・化学シフト値予測システムに組み込み、予測精度を上げた

Download Report