平面グラフの線形システムへの応用

点击翻译按钮获取中文摘要

実対称行列W=(w_<fj>)に対して,無向グラフG=(V,E)がE={(v_f,v_j)|w_<fj>≠0}を満たすとき,グラフGはWに付随したグラフと言う。Gが2連結平面グラフである場合に連立1次方程式Wx=cを効率よく解く問題を考える。2連結平面グラフに(1)直列辺の除去,(2)並列辺の除去,(3)YをΔに置き換える,(4)ΔをYで置き換える,という4つの変換(以後総称してΔ-Y変換という)をうまく繰り返すことにより一辺のみからなるグラフに縮約できることはすでに解っている。我々はこの事実を利用して上記の連立方程式を解くことを考えた。Wに付随するグラフGにおいてΔ-Y変換をおこなったときG'になったとすると,Wx=cの解とW'x'=c'の解が同じになるようにW',c'を決めかつG'がW 'に付随するグラフであるようにできる。従ってこの方法で解く場合,有効性は2連結平面グラフを1辺に縮約するΔ-Y変換列の長さに依存する。我々は次のような短い縮約Δ-Y変換列を求めるアルゴリズムを提案した。(1)GがG'のマイナ-でありかつG'はすべての頂点の次数が4以下になるようなグラフG'を求める。(2)G'をシリンダー上の格子グラフに埋め込む。(3)シリンダー上の格子グラフを1辺に縮約するΔ-Y変換列を求める。(4)(3)で求めたΔ-Y変換列の中からGの辺のみからなる変換列を求める。これが求める変換列である。各ステップの時間計算量は,頂点数nに対して,1)がO(n),3)が格子グラフの寸法k×mに対してO(k^2m)である。従ってこのアルゴリズムはステップ2)に依存する。多くのグラフでO(n)の大きさの格子グラフに埋め込むことができその場合全体の時間計算量はO(n√<n>)である。