Kruskal trees

Fig.1. Kruskal tree computed from Euclidean distances evaluated with overlap-like similarity measures for fluoro- and chloro-methanes. The classes identify two ranges of boiling or melting points...

In Figure 9 we present a Kruskal tree computed from euclidean distances for Cu(II)-P-diketone quelate compounds, on the plane of 3-6 principal components for the overlap-like similarity measure matrix. The quelate with acetylacetone as a ligand with constant value (-3.47) appears as a principal knot, acting as a bridge between more and less stable quelates. 

Figure 18 shows a Kruskal tree [2.c], computed from euclidean distances, showing the relationships between elements described in... 

In Figure 20 we have the Kruskal tree [2.c], computed from euclidean distances, showing the relationships between the elements on Table 5. In most cases we can see that elements with melting point values smaller than the average value are terminal branches of the tree. 

Figures 25 to 27 correspond to the set of ethereal odor molecules. As before, the elements of the set are divided into two classes. In figure 25 a Kruskal tree [2.c], computed from euclidean distances of the overlap similarity measure, is drawn. We can see that elements with low odor intensity are terminal branches of the tree. Figures 26 and 27 represent graphs computed using a nearest neighbor algorithm [2.e] from the overlap similarity measure matrix and a minimal order algorithm [2.e] obtained from the Coulomb similarity measure matrix, respectively. In both cases we can observe that elements in the same class have preference to link.

Figure 31 shows a nearest neighbor graph [2.e] computed using the overlap similarity measures, whereas figure 32 is a Kruskal tree [2.c] computed from the Coulomb measures using euclidean distances, for musky odor molecules. In both cases we can see a different trend to link related to different kind of elements. 

Figure 9.-Kruskal tree computed from euclidean distances for Cu(U)-beta-diketones quelate compounds, from overlap-like similarity measure.

Figure 18.-Kruskal tree, computed from euclidean distancies, of elements on Table 4.

We have already used similarity matrices to cluster molecules. As such, they provide the necessary data to investigate the construction of a molecular set taxonomy. The most common techniques to do so include the molecular point clouds previously described. There, the columns of the molecular quantum similarity matrix yielded coordinates of the molecules in the N-dimensional space. Often, the N dimensionality cannot yet be used for a graphical representation. However, several techniques exist to reduce the dimensionality of the data, which allow it to be represented graphically on common devices like a computer screen or a plotter. In addition to these plots, several instances have involved Kruskal trees and other algorithms. °... 

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. 

We use Kruskal s algorithm (13) to construct a minimum spanning tree (MST) ... 

Sankoff DD, Cedergren RJ (1983) Simultaneous comparison of three or more sequences related by a tree. In Sankoff D, Kruskal B (eds) Time Warps, String Edits, and Macromolecules The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA, p 253... 

For complex graphs the number of trees to be examined can be enormous. The special problem (A.14) has, nevertheless, a straightforward solution. It consists in the constraction of a tree by adding successively new arcs in the manner that in each step, the arc with least cost is added. TTie following variant is attributed to Kruskal Jr. (1956) cf. Christofides (1975), p.l37. We suppose again that G [N, J] is connected. 

Kruskal, J.B., Jr. (1956), On the shortest spanning tree of a graph and the traveling salesman problem, Proc. American Mathematical Soc. 7, 48... 

---