Spanning-tree

A spanning tree in G is an edge-subgraph of G which has N — 1 edges and contains no circuits. 

B G) is often used to define the complexity of a graph G, (G), equal to the number of spanning trees of G. It turns out that... 

We conclude this section by mentioning two older definitions of complexity, each of which also depends on both the size and vertex structure of a graph G (1) the number of spanning trees in Gj and (2) the average number of independent paths between vertices in G. 

If B— [bij] is an N xN matrix in which bu equals the degree of vertex i, bij = —1 if vertices i and j are adjacent and bij = 0 otherwise, then the number of spanning tree of G is equal to the determinant of any principal minor of B [hararybO]. The extremes occur for totally disconnected graphs that have no spanning trees and thus a complexity of zero, and for complete graphs of order N that contain the maximum possible number of distinct trees on N vertices. ... 

Fig. 30.9. Examples of trees in a graph (a) is the minimal spanning tree [18],...

Hierarchical methods are preferred when a visual representation of the clustering is wanted. When the number of objects is not too large, one may even compute a clustering by hand using the minimum spanning tree. 

The edges in a spanning tree are called tree branches or branches. All other edges of G are called chords. Thus, with reference to Tu the chords are 6, 7, 8. Because there is one and only one path between any two vertices of Tj, the addition of any chord to Tx will create exactly one cycle. Such a cycle is called a fundamental cycle. It follows that there are as many fundamental cycles as there are chords (P — N + 1 = C). Thus for the graph in Fig. 1 the fundamental cycles are 3, 4, 6, 2, 4, 7, and 2, 4, 5, 8). Notice that the fundamental cycles are defined only with respect to a given spanning tree. If more than one chord is added to Tx at the same time, cycles which are not fundamental cycles will also be created. For instance, simultaneous addition of chords 7 and 8, will create not only the last two fundamental cycles but also 5, 7, 8 which is not a fundamental cycle. Since each chord occurs only once in a set of fundamental cycles, it should be evident that the rows of a cycle matrix corresponding to the fundamental cycles will be linearly independent and the rank of the cycle matrix will be (P — N + 1). Such a matrix will be referred to as a fundamental cycle matrix. 

Equations (16) and (17) show the important link between fundamental cycles and cut-sets of a graph. Thus, a spanning tree provides a convenient starting point for formulating a consistent set of governing equations for steady-state pipeline network problems. 

Cherition D, Tarjan RE (1976) Finding minimum spanning trees. SIAM J Computing 5 724... 

Another approach to the breach path problem is finding the path which is as far as possible from the sensor nodes as suggested in [26], where the maximum breach path and maximum support path problems are formulated. In the maximum breach path formulation the objective is to find a path from the initial point to the destination point where the smallest distance from the set of sensor nodes is maximized. In the former problem, the longest distance between any point and the set of sensor nodes is minimized. To solve these problems, Kruskal s algorithm is modified to find the maximal spanning tree, and the definition of a breach number tree is introduced as a binary tree whose leaves are the vertices of the Voronoi graph. 

Subramaniam, S. and S. B. Pope (1998). A mixing model for turbulent reactive flows based on Euclidean minimum spanning trees. Combustion and Flame 115,487-514. 

A very different approach to characterize clustering tendency is based on the frequency distributions of the lengths of the edges in the minimum spanning tree connecting the objects in the real data and in uniformly distributed data (Forina et al. 2001). 

The minimal spanning tree also operates on the distance matrix. Here, near by patterns are connected with lines in such a way that the sum of the connecting lines is minimal and no closed loops are constructed. Here too the information on distances is retained, but the mutual orientation of patterns is omitted. Both methods, hierarchical clustering and minimal spanning tree, aim for making clusters in the multi-dimensional space visible on a plane. 

Computer simulation in space takes into account spatial correlations of any range which result in Intramolecular reaction. The lattice percolation was mostly used. It was based on random connections of lattice points of rigid lattice. The main Interest was focused on the critical region at the gel point, l.e., on critical exponents and scaling laws between them. These exponents were found to differ from the so-called classical ones corresponding to Markovian systems irrespective of whether cycllzatlon was approximated by the spanning-tree... 

Figure 5. Transformation of a molecule with cycle into a spanning tree and labelling of the ring forming functionalities. (Reproduced with permission from Ref. 42. Copyright 1987 CRC Press).

The length obtained by the traversal of the minimum spanning tree (MST). 

---