ランダムグラフの統計解析

概要

論文の詳細を見る
It is required to generate a great many random graph data by a computer when we try to test the efficiency of some algorithms for a graph of network problem. In this paper, we give two kind of computer algorithms to generate efficiently randomn (connected) graphs, and also show some statistic properties of random graphs by means of computer simulation. We find a remarkable structural feature of connected random graphs such that the most of connected random graphs generated consist of a large biconnected component and certain number of biconnected components having only one edge. And it follows that the divide-and-conquer method is not so effective when applied for a random graph. This fact is demonstrated for some numerical examples. Furthermore, we show that the directed random graphs also have the similar feature when they are decomposed into strongly connected components.
一般社団法人情報処理学会の論文
1978-08-15