ランダム有向グラフにおける到達可能性と推移閉包の大きさについて

概要

論文の詳細を見る
本論文では、節点数|V|が小辺集合Aにおける有向辺(u,v)の存在する確率が、他の辺の存在とは独立にp(n)で与えられるランダム有向グラフG=(V,A)に対して、Gにおける到達可能性やGの推移閉包の大きさ、およびそれらに関連する話題について論じる。はじめに、与えられたnとp(n)に対して、節点sからt(≠s)への厳密な到達可能性γ_<n,p(n)>を計算する方法を示す。しかし、この方法はO(n^3)の計算時間を要するのでγ_<n,p(n)>に対する簡単な上下界値γ^U_<n,p(n)>,γ^L_<n,p(n)>を導く。さらに,解析を容易にするためにγ^U_<n,p(n)>に対する上界値γ^^-_<n,p(n)>を導入し、その漸近的な性質を調べる。その結果、p(n)=の1/(n-1)のととき、lim__<n→∞>γ^^-_n,p(n)は1-x-e^<-αx>=0の一つの解に収束することがわかる。また、R^^-(n)とT^^-(n)をそれぞれ、ある節点から到達可能な節点数と推移閉包の大きさの上界値とする.このとき、もしp(n)=α/(n-1)(1≤α<1)であれば、lim__<n→∞>R^^-=α/(1-α),p(n)=α/(n-1)^2(α≥0)であればlim__<n→∞>T^^-(n)=αとなることを明らかにする。
社団法人電子情報通信学会の論文
1995-06-22