地域間ネットワークにおける最短結合と近隣結合に関する理論的考察

Theoretical study on the shortest connectivity and neighborhood connectivity for the regional networks

日本都市計画学会

2008-04-09T09:23:04Z

2008-04-09T09:23:04Z

2003/10

The main theme of this paper is to show that almost 90% links of a minimum spanning tree are composed by the links of the shortest neighbor and the second shortest neighbor. More concretely, exactly 69% links of a minimum spanning tree are made up of the nearest neighbor links, about 22% links are made up of the second nearest neighbor and 9% links are made up of the third nearest and so on. From this information, if N point-facilities are located uniformly randomly in a 1x1 square, we can estimate the lower bound for the length of the minimum spanning tree on these N points far better than it has been. So that we can prove that the length of minimum spanning tree > 0.64√N when N points are located randomly in 1x 1 square.

Made available in DSpace on 2008-04-09T09:23:04Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-04-09

都市計画学会論文集「学術研究論文発表会論文」Vol. 38-3 (2003) 64 pp.379-384

http://hdl.handle.net/10212/1629

ja

本著作物の著作権は（社）日本都市計画学会に帰属します。

Journal Article

Article