数理解析研究所講究録
第 1554 巻 2007 年 202-209

202

確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察
安藤映 (Ei Ando) 小野廣隆 (Hirotaka Ono)
定兼邦彦 (Kunihiko Sadakane) 山下雅史 (Masafumi Yamashita)

Department of Computer Science and Communication Engineering,

Graduate School of Information Science and Electrical Engineering,
Kyushu University
概要

本稿では枝重みが互いに独立な確率変数として与えられる場合の最小全域木問題に関して, その枝重み合計の分布を近似的に求める手法について考察する. アルゴリズムの設計に当たって, matrix-tree 定理を一般化した定理を証明し, 全ての全域木の重み分布についてその最小値のとる分布を行列式演算の一般化として表現する.
本稿では, 最小全域木の重み合計が高々 である確率 $F(x)$ に着目して, 与えられたパラが $F^{-1}(1-a)$ よりも小さいところで分布関数の上限を与えるような正についてメータを得るような近似アルゴリズムを目標とする. しかし, 正規分布関数
規分布関数を多項式時間で得るようなアルゴリズムとするにはもう一段階の工夫を加える必要がある.
$x$

$x$

$a$

$\tilde{F}(x)$1$\tilde{F}(x)$はじめに無向グラフの最小全域木を求める問題はグラフ上の問題としてもっとも古い部類に属する問題で, 枝重みが確定的な値として与えられる場合には高速な解法が提案されている. 現在
最速のアルゴリズムは Chazelle[l] によるものが知られている.
において校重みがある分布に従う確率変数として与えられる場合を考える.
無向グラフ
このとき, 最小全域木の枝重み合計もある確率変数となるが, 枝重みが正規分柘に従うと仮$G$定しても $G$ が閉路を含む場合には, 最小全域木の重み分布は正規分布ではなくなるため,一般にその分布を正確に求めることは難しい.
Kulklni[2] は枝重みが指数分布に従い, 互いに独立な確率変数と仮定し, その最小全域木の分柿および任意の枝が最小全域木に舎まれる確率を得る方法を提案している.
本稿では分布関数の上限を高速に近似する手法について考察する. 全域木の数を計算する項式の一般化に基づいて, matrix-tree 定理を一般化した定理を証明し, 全ての全域木の重み分布を行列式演算の一般化として表現する.

203
本稿では, 最小全域木の重み合計が高々メータ $a$ について $x$である確率 $F(x)$ に着目して, 与えられたパラが $F^{-1}(1-a)$ よりも大きいところで分布関数の上限を与えるような正$x$

規分布関数を得るような近似アルゴリズムを目標とする. しかし, 正規分布関数を多項式時間で得るようなアルゴリズムとするにはもう一段階の工夫を加える必要がある.

$\tilde{F}(x)$$\tilde{F}(x)$2$\Leftrightarrow\neg-rffi$

平均 , 分散$\mu$$\sigma^{2}$の正規分布$N(\mu, \sigma^{2})$の確率密度関数 $f(x)$ は次式で与えられる.

$f(x)= \frac{1}{2\pi\sigma}ex^{p}(-\frac{x^{2}}{2\sigma})$に従う場合は, その二つの確率変数がそれぞれ正規分布
和 $X_{1}+X_{2}$ は正規分布に従うことが知られている. このためグラフ$G$ が木である場合には枝重みの平均と分散の和をとることで最小全域木の厳密な分布を計算$N(\mu_{1}, \sigma_{1}^{2}),$$X_{1},$ $X_{2}$$N(\mu_{2}, \sigma_{2}^{2})$$N(\mu_{1}+\mu_{2}, \sigma_{1}^{2}+\sigma_{2}^{2})$できる.
グラフ $G$ が単一の閉路からなる場合, グラフ $G$ から任意のひとつの枝を取り除くことで全域木が得られるため, 次のような計算で最小全域木の分布関数 $F(x)$ は, 次の式で上限$Fu(x)$ を得ることができる.
$F_{U}(x)=1- \prod_{1\leq:\leq|E|}(1-F_{i}(x))$

ただし $F_{i}(x)$ は枝 $e\{\in E(1\leq i\leq|E|)$ 以外の枝重みの合計の分布関数とする. 各枝重みが正規分布に従う確率変数である場合でも $F_{U}(x)$ は正規分布関数ではない.

3 高速に分布関数の上限を近似する手法
関数 $F(x)$ を最小全城木の重み分布関数とする. 関数 $F(x)$ の上限を求めることは全ての全域木を列挙すれば可能であるが, 全域木の数は最大で $|V|^{|V|-2}$ 個あり, 効率的なアルゴリズムとは言えない. 本節ではより効率的に分布関数の上限を求めることを考える.

3.1 matrix-tree 定理の一般化
全ての全域木の数であれば行列式の計算によって得ることが知られている (matrix-tree定理). まず, matrix-tree 定理について説明し, 次に matrix-tree 定理の一般化から分布関数の上限を近似する手法を得ることを考える.

定理 1(matrix-tree 定理)
グラフ $G$ から任意の 1 頂点の隣接行列 $A$ と次の式によってを取り除いたグラフ
中での次数,は頂点 の定義される $(n-1)\cross(n\cdot-1)$ 行列 $D$ を考える. ただし$d:j$ は行列 $D$ の行 列目の成分である.
$v$$\tilde{G}_{v}$$d_{i}$$i$$j$$d_{i^{j}}=\{\begin{array}{ll}d_{i} i=j\circ\Leftrightarrow\square \wedge 0 t\neq j\mathcal{O}3B^{\Delta}D\end{array}$$i$$\tilde{G}_{v}$204
グラフ $G$ 中の全域木の集合を$\mathcal{T}$とすると$|\mathcal{T}|$は次の式で表され, 取り除かれる頂点$v$には依存しない.
$|\mathcal{T}|=\det(D-A)$

まず, グラフ $G$ から任意の 1 頂点

$v$を取り除いたグラフ$\overline{G}_{v}$のについて $E$ の部分集合に対して次の式で定義される $(n-1)\cross(n-1)$ 行列 $H^{E’}$ を考える. ただし
行 列目の成分であるとする.

$i$$h_{ij}^{E\prime}v$

は$E_{v}’$$H^{E^{J}}$の$j$$\{\begin{array}{ll}h_{i^{j’}}^{E}=\sum_{k=1}^{n}\delta_{ik} i=j \text{の場合}h_{i^{j}}^{E’}=-\delta_{i^{j}} i\neq J \text{の場合}\end{array}$

この式で $\{ij\}\not\in E_{v}’$ の場合のみ$\delta_{ij}^{E’v}=0$として,$\det(H^{E})$の計算を考える.

定理 2 (matrix-tree 定理の一般化)$\det(H^{E’v})$ を展開して積和の形に整理すると次式で表される.
$\sum_{T\in T}\prod_{e\in T}\delta_{e}^{B\prime_{v}}$ただし$\mathcal{T}$は $G$ の全域木の集合である.

証明 (棚略)
行列式演算の性質により, 積和形に展開した場合はどの項も各行各列からひとつ要素をの積を因数とする項は存在因数として持つ. また, 同じ行に属する二つの要素. の積を因数とする項も存在しない. 従って,せず, 同じ列に属する二つの要素$a_{i^{j}},a_{ik}$$a_{l^{i}}a_{k}$を考えると, そのの枝集合 $V\cross V$ への写像
$n-1$ 個の頂点からとを因数として持つ項と頂点 を枝 $\{i,j\}\in E$ へ写すような写像中でも特に対応付けることができる.
が閉路 $C\subseteq E$ をに着目する. いま,以下, 写像勉で写される先の枝集合中での頂点の順番の入れ換えは $\det(H^{E})$ の値を変含むと仮定する. すると, 行列であると化させないため, 一般性を失うことなく閉路 $C$ の内部頂点は$..,$$l:V\backslash \{v\}rightarrow V^{2}$$K_{n}$$l$$l_{E}$$i$$\delta_{i^{j}}^{E}$$E\iota\subseteq E$$E\iota$$H^{E}$$v_{1},$$\iota_{2},$$v_{|C|}$考えることができる.
ここで, $\det(H^{E})$ の閉路 $|C|$ に関わる部分だけを強調すると, 概観は次式 (1) のような形となる.

(1)

ただし,

$\Delta^{E}=\Sigma_{j=1}^{n}\delta_{i^{j}}^{E}$である.

205
ここで,$\det(H^{E})$の対角成分の積の中から, 閉路 $C$ の枝に対応する$\delta_{e}^{E}$を全て因数に持つ項だけ抜き出すことを考える. 共通の因数を小行列式を用いて括り出してそれらの項をまとめると次式 (2) のように書ける.

$-\delta_{|C,.|+1,|C|}^{E}\Delta_{|C|.+2}^{E}$.

$\delta_{|C|,1}^{E}\prod_{k=1}^{|C|}\delta_{k-1,k}^{E}|^{\Delta_{|C|+1}^{E}}-\delta_{|C,..\cdot.\cdot|+21}^{E}|-\delta_{n-11}^{E}$$-\delta_{1C+1|,n-1}^{E}-\delta_{n-2n-1}^{E}|(2)$$-\delta_{n-1,n-2}^{B}\Delta_{n-2}^{E}$

から閉路 $C$ への写像に対応する項が存在し, 対角成分に存在する項と符号が逆であることを示す. 閉路には枝 {1,2} が含まれるので,以下, 対角成分の積以外で,$V\backslash \{v_{n}\}$に着目し, これを因数として持つ部分を小行列式
行列式 (1) の 1 行 2 列目の要素として書 \langle と, 次式 (3) の通りとなる. この行列式の係数は負号が相殺して正である.
$\delta_{12}^{E}$(3)を因数に持つ部分を抜き出すと,同様に小行列式を使って次式 (4) によって表される.
$\delta_{23}^{E}\cdot\delta_{3\cdot 4}^{E}\ldots$$\prod_{k=1}^{|C|}\delta_{k-1k}^{E}$の因数を持つ項は$\cross\prod_{k=1}^{|C|}\delta_{k-1k}^{E}(4)$を因数として持つ部分を抜き出すと, 負号が相殺され1 行 1 列目のないため小行列式の係数は一 1 であることがわかる. 従って, 式 (2) と式 (4) を比較す
ここで,$\delta_{|C|-11}^{E}$

ると符号だけが異なり, 残りは全て同じ式であるためにこれら二つの項は互いに相殺する.

206
以上により,$\det(H^{E})$を積和形に展開して得られる式巾のひとつの項と対応する写像

が朗路を含む場合は必ず対角成分と, 対角成分以外にについて:ひとつずつ符号の違う成分が存在して互いに相殺することが示せた.
従って,から閉路のある珂への写像 }こ対応する項は全て互いに相役するたすなわち全域木に対応する項だけが残る.
め, 閉路の無いとすると定理 2 から全域木の数が得られるため定理 2 はある枝 $e\in E$ に関してlnatrix-tree 定理の一般化と考えることができる. 次節以降では, 確率分布を行列の要素と$l$$E\iota$$V\backslash \{\cdot\iota_{n}\}rightarrow E\iota$$l$$V\backslash \{t_{n}\}$$\blacksquare$$E_{l}$$\delta_{\epsilon}^{E}=1$して持つ行列を考え,行列式演算の一般化を適用することで最小全域木の分布を表現することを説明する.

3.2 行列式演算の一般化
本節では, 行列式演算を行列 $M$ , 加算記号田,乗算記号図の 3 つに対する一般化$DET$ ( $M$ , 田, 図) を考える.

定義 (行列式濱算の一般化)
行列式演算の一般化 $DET$ ( $M$ 田, 図) を次のように再帰的に定義する. ただし, 行列 $M$と書く. 減算”\Xi ’’ は加算は $mxm$ 行列と仮定し, 行列 $AI$ の 行 列目の要素をである.
田田. . . 田は合計演算の一般化で記号田の逆演算,$i$$j$$m_{i}j$$\Sigma_{i=1}^{n}A_{i}=A_{1}$$\Sigma$$DET(Mffl,$ 図 $)=\Sigma_{=1}^{\dot{m}}(B1)^{i-1}m_{1i}$ 図 $DET$ (小行列$hf_{i}$は行列 $AI$ から$i$行と$i$$A_{n}$$A_{2}$$M_{i}$es, 図)

列を削除して得られる行列である.

例えば, 行列 $M$ の行列式は DET を用いて $DET(M+, \cross)$ と書くことができる.

3.3 最小全域木の重み分布の定式化
確率分柿の計算をする演算子として図と田を定義する.
定義演算子図 (二つの槌率変数の和の分布)
ここから,は二つのについて,図の従う確率分布
二つの独立な確率変数確率変数の和 $X_{1}+X_{2}$ の従う分布である. 特に, 二つの確率分布の密度関数が $f1(x)$ ,の密度関数 $f(x)$ は, 畳み込み積分を用いて次式で表さ
図$f_{2}(x)$ であるとき,$X_{1},$$D_{1}$$D_{1},$$X_{2}$$D_{2}$$D_{1}$$D_{2}$$D_{2}$

れる.
$f(x)= \int_{-\infty}^{\infty}f_{1}(x-\tau)f_{2}(\tau)d\tau$

定義演算子田 (二つの穏率変数の最小値の分布)は二つの田について,二つの独立な確率変数 $X_{1}X_{2}$ の従う確率分布
確率変数の最小値 $\min\{X_{1}X_{2}\}$ の従う分布である. 特に, 二つの確率分布の分布関数$D_{1},$が $F_{1}(x),$$F_{2}(x)$であるとき,$D_{1}$

田$D_{2}$$D_{2}$$D_{1}$$D_{2}$の分布関数 $F(x)$ は次式で表される.

$F(x)=1-(1-F_{1}(x))(1-F_{2}(x))$
この関係は, 補分相関数 $F_{1}^{C}(x)=1-F_{1}(x),$ $F_{2}^{c}(x)=1-F_{2}(x),$ $F^{C}(x)=1-F(x)$を用いることによって次のように簡潔に書ける.
$F^{C}(x)=F_{1}^{C}(x)F_{2}^{C}(x)$207すなわち $\min\{X_{1}, X_{2}\}$ の補分布関数 $F^{C}(x)$ は補分布関数 $F_{1}^{C}(x),$$F_{2}^{C}(x)$の積である.

定理 2 及び DET, 図, 田を用いると最小全域木の枝重み和の分布を次のように matrix-tree定理と同様の形式で書き表すことができる.

定理 3(最小全域木の重み分布)と定義する. ただ枝 $\{i,j\}$ の枝重みが従う確率分布をとおき,し, $\{i,j\}\not\in E$ の場合, 枝重みはある確率分布 $Z$ に従う確率変数とし, $Z$ の確率分布に対して, $x<xz$ のとき $F_{z}(x)=0$ とする.
関数 $Fz(x)$ はある十分大きな実数値$\Delta_{ij}=\Sigma_{j}^{n}\delta=1iJ$$\delta_{i,J}$$x_{Z}$

次の式で表される確率分布の $(n-1)\cross(n-1)$ 行列 $P$ を考える. ただし,
$P$ の行 列目の要素とする.
$i$$P^{i^{j}}$

は行列

$j$

$p_{i^{j}}=\{\begin{array}{ll}\Pi_{j=1}^{n}\delta_{i^{j}}, i=j \text{の場合}B\delta_{i^{j}}, i\neq j \text{の場合}\end{array}$

ただし, 臼は田演算の逆演算,は積の一般化で $\Pi_{i=1}^{n}A_{i}=A_{1}$ 田ある. このとき, 最小全域木の重み分布は次式で表される.
$\Pi$$DET(P, ffl,$図$A_{2}$田.

..田$A_{n}$で$)$この定理においては, 演算田を加算の代わり, 図を乗算の代わりに使うことに気を付ける.
証明
定理 2 より, DET を展開して得られる各項は次式の形となる.
$\Pi_{T\in \mathcal{T}}\Sigma_{e\in r\delta_{c}}$これは全ての全域木を列挙して, その重み分布の最小値を取ることに対応する.
定理 3 から, 行列式計算の一般化である DET を計算できれば, 最小全域木の分布を求め$\blacksquare$ることができるとわかる 6 なお, 定理 3 は枝重みが正規分布の場合に限らず, 一般の分布で通用する. ただし, 一般に min 演算には補分布関数 (complementary distributio hnction)の積を取ることが必要であり, その計算には因数の補分布関数の数と同じだけの計算時間がかかる. 従って, 定理 3 による計算だけでは少なくとも全域木の数と同じだけの計算時間がかかるため効率的な方法とは言えない.

3.4 最小値演算の近似
グラフ $G$ の枝重みが互いに独立で正規分布に従う確率変数として与えられている場合, 定

理 3 に沿って最小全域木の枝重みを計算するには補分布関数の積を計算する際に全因数をリストとして保持しておく必要があり, 効率的な手法とはまだいえない. 以下では, 演算田を近似することによって, 次の方針を満たす正規分布関数を求め, 正規補分布関数の積を抑えること考える.
方針
グラフ $G$ の枝重みが互いに独立で正規分布に従う確率変数として与えられている場合,ある定数 $a(0\leq a\leq 1)$ に対して, 次式を満たす正規分布関数) を求める. ただ$\overline{F}\Leftarrow$208
し $F(x)$ はグラフ $G$ の全域木の重みの分布関数.
$x\leq F^{-1}(1-a)\Rightarrow F(x)\leq\tilde{F}(x)$方針で求められる関数の値は, 直観的に言えば確率$a$で最小全域木の重みよりも小さな値を見積もることに対応する.
二つの正規分布関数 $F_{1}(x),$ $F_{2}(x)$ の最小値演算結果をひとつのを考える. この手法は [3] と同じ手法であるので簡潔に説明する.

$\tilde{F}(x)$で置き換えること定理 4(正規分布関数による田演算の近似)の分布関数を $F_{1}(x),$とする.
般性を失うことなくくと, 正規分布の分布関数

正規分布$N(\mu_{1}, \sigma_{1}^{2})$の分布関数を $F_{2}(x)$ とおく.
田の分布関数を $F(x)$ とおはある定数 に対して次の式が成り立つ.

$N(\mu_{2}, \sigma_{2}^{2})$$N(\mu_{1}, \sigma_{1}^{2})$$\sigma_{1}\geq\sigma_{2}$$\tilde{F}(x)$$N(\tilde{\mu},\overline{\sigma}^{2})$

一$N(\mu_{2}, \sigma_{2}^{2})$$a$$(0\leq a\leq 1)$$x\leq F^{-1}(1-a)\Rightarrow F(x)\leq\tilde{F}(x)$ただし,かつ,$\tilde{\sigma}=\sigma_{1}$$\tilde{\mu}\geq\mu_{1}-\sigma_{1}(\Phi^{-1}(1-a)-F^{-1}(1-a))$とする.

$\Phi(x)$は標準正規分布 $N(0,1)$ の分布関数である.
定理 4 は正規分布関数の微分をうまく操作することによって証明できるが, 証明は紙面の都合から省略する.
は, 田演算を行うと方針の性
定理 4 に沿った方法で近似的に得られた正規分布質を満たすことができなくなる. 田濱算と図演算を任意順で繰り返し実行するために次の定理を用いることを考える.
定理 5(田濱算の近似の単調性)$N(\tilde{\mu},\tilde{\sigma}^{2})$定理 4 において,$\tilde{\mu}$をできるだけ小さく取った場合の$\tilde{F}(x)$と$N(\mu_{1}, \sigma_{1}^{2})$$N(\mu_{2)}\sigma_{2}^{2})$の関数とみて,の分布関数 $F(x)$ について,$F^{-1}(1-a)-\tilde{F}^{-1}(1-a)$ を$F^{-1}(1-a)-\tilde{F}^{-1}(1-a)$とする. すると, $a>1/2$ の場合は$\sigma_{1}$田$d(\sigma_{1})$は$\sigma_{1}$$d(\sigma_{1})=$に関してに関して単調減少である.
次に述べる手法で田演算を近似することにより, 近似として得られた正規分布に対し単調増加であり, $a<1/2$ の場合は$d(\sigma_{1})$は$\sigma_{1}$て図漬算を行っても方針の性質を保持できることが定理 5 から言える. パラメータ$1/2<a<1$ を満たす場合について説明すると,$a$がまず, 枝重みはそれぞれ正規分布の分散が確定的な枝重みである場合のことを考え, 分散が最大となるような全域木 Tmax を求めとの重みの分散をておく. 次に, 枝重みが確率的な場合に戻って考え, 全域木の代わりに,田田
おく. 演算図の計算を近似する際,との近似計算を定理 4 に沿って行う. 得られた分布をを採用する. パラメータ がの近似結果として
田
考え,とその分敢の代わりに分散最小の全域木$0<a<1/2$ を満たす場合に関しては.
$\sigma_{\max}^{2}$$T_{\max}$$N(\mu_{1}, \sigma_{1}^{2})$$N(\mu_{2}, \sigma_{2}^{2})$$N(\overline{\mu},\overline{\sigma}^{2})$$N(\mu_{2}, \sigma_{2}^{2}+(\sigma_{\max}^{2}-\sigma_{1}^{2}))$$N(\mu_{1}, \sigma_{1}^{2})$$N(\mu_{2}, \sigma_{2}^{2})$$N(\overline{\mu}, \sigma_{1}^{2})$$T_{ma3}$$\sigma_{\min}^{2}$$N(\mu_{1)}\sigma_{\max}^{2})$$a$$T_{\min}$を用いる.

35 未解決部分
以上により,

定理 3 の式から田演算の代わりに定理 4,5 による近似計算を行えぱ, 方針の条件を満たす正規分布関数を計算することができるが, 定理 3 によれば田演算の逆演算をDET の展開時に任意の順香で適用可能でなければならない. しかし, 定理 4,5 によって近209
似計算を行うと逆演算を方針の条件に合うように定義できるかどうかは本発表時点で未知である.

このため, 系統的に臼演算を DET から消去する方法または臼演算の適切な定義をすることが今後の課題である.

4 結論
枝重みが互いに独立な確率変数として与えられる場合の最小全域木問題に関して, 最小全域木の重み分布を行列式の一般化を用いて表現した.
枝重みが正規分布に従う確率変数として与えられる場合, 畳み込み積分を避けるために近似手法の設計を試みた. 方針として, 最小全域木の重み合計が高々 である確率 $F(x)$ に着目して, 与えられたパラメータ a について が $F^{-1}(1-a)$ よりも大きいところで分布関数の上限を与えることを目標とした. 提案手法を完成させるにはあと一段階の工夫が必要であり, 近いうちに解決したい.
$x$

$x$

$W$

参考文献
[1] B.Chazzele, “A Minimum Spanning Tree Algorithm with Inverse-Ackermann
Type Complexity”, JACM, Vol.47., No.6, November 2000, pp.1028-1047.
[2] V.G.Kulkarni, “Minimal Spanning Trees in Undirected Networks with
nentially Distributed Arc Weights”, NETWORKS, Vol. 18,1988, pp.111-124.
[3] E. Ando, M. Yamashita, T. Nakata, Y.Matsunaga, “The Statistical Longest
Path Problem and Its Application to Delay Analysis of Logical Circuits”,
proc.TAU, 2002, pp.134-139.
$Exp\triangleright$