著者

河邊 昌彦 二村 良彦

出版者

一般社団法人日本ソフトウェア科学会

雑誌

コンピュータソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.20, no.4, pp.363-368, 2003-07-25

---

頂点にラベルの付いた連結グラフのランダム生成は,グラフアルゴリズムの評価のために重要である.本稿では,グラフのランダム生成に必要な構成比を近似する方法を提案し,それによって高速な生成が可能であることを示す.グラフアルゴリズムの評価には,特定の性質を有してランダムに生成されたグラフが多量に必要である.また,ネットワークのシミュレーション等に関しても,テストデータとしてランダムに生成されたグラフを必要とすることがある.その際,グラフ生成が高速であることと同時に,生成されるグラフのランダムネスに関しても高精度であることが要求される.例えば,[1]において最小全域木問題を線形時間で解く確率的アルゴリズムが示されているが,このアルゴリズムの検証を実際に行うためには,テストデータとしてランダムに生成された重み付き連結無向グラフが必要となる.このようなグラフは,ランダムに生成されたラベル付き連結無向グラフから生成可能である[6].指定された頂点数nと辺数mを持ち,頂点にラベルの付いた連結無向グラフをランダムに生成する既存の方法として,以下のものが挙げられる.頂点数nの木をランダムに生成し,これにm-m+1本の辺をランダムに付け加えることによって連結グラフを生成できる(全域木法).また,m本の辺をランダムに決定して生成されたグラフが連結となるまで繰り返して,連結グラフを生成する方法もある(生成検査法).或いは,構成比というグラフ総数に関する指標を用いて,ランダムにグラフを生成することができる(構成比法).しかし,全域木法に関してはランダムネスの精度に,生成検査法と構成比法に関しては生成時間に問題があり,必ずしも実用可能ではない.また,これら以外で効率的なグラフ生成を可能とする方法は,我々の調査では見出せなかった.本稿では,構成比を高い精度で近似する単純な近似式を提案する.それにより,構成比法によるグラフ生成の時間を改善し,大規模なグラフに関しても現実的な時間で生成できることを示す.