Globally and locally minimal weight spanning tree networks

The competition between local and global driving forces is significant in a wide variety of naturally occurring branched networks. We have investigate d the impact of a global minimization criterion versus a local one on the s tructure of spanning trees. To do so, we consider two spanning tree structu res-the generalized minimal spanning tree (GMST) defined by Dror et al. (Eu r. J. Oper. Res. 120 (2000) 583) and an analogous structure based on the in vasion percolation network, which we term the generalized invasive spanning tree (GIST). In general, these two structures represent extremes of global and local optimality, respectively. Structural characteristics are compare d between the GMST and GIST for a fixed lattice. In addition, we demonstrat e a method for creating a series of structures which enable one to span the range between these two extremes. Two structural characterizations, the oc cupied edge density (i.e., the fraction of edges in the graph that are incl uded in the tree) and the tortuosity of the arcs in the trees, are shown to correlate well with the degree to which an intermediate structure resemble s the GMST or GIST. Both characterizations are straightforward to determine from an image and are potentially useful tools in the analysis of the form ation of network structures. (C) 2001 Published by Elsevier Science B.V.