International
Tables for Crystallography Volume H Powder diffraction Edited by C. J. Gilmore, J. A. Kaduk and H. Schenk © International Union of Crystallography 2018 |
International Tables for Crystallography (2018). Vol. H, ch. 3.8, p. 331
Section 3.8.4.2.3. Powder data as a tree: the minimum spanning trees^{a}Department of Chemistry, University of Glasgow, University Avenue, Glasgow, G12 8QQ, UK |
The minimum spanning tree (MST) displays the MMDS plot as a tree whose points are the data from the MMDS calculation (in three dimensions) and whose weights are the distances between these points. The minimum-spanning-tree problem is that of joining the points with a minimum total edge weight. (As an example, airlines use minimum spanning trees to work out their basic route systems: the best set of routes taking into account airport hubs, passenger numbers, fuel costs etc. is the minimum spanning tree.) Because a tree is used, each point is only allowed a maximum of three connections to other points.
To do this Kruskal's (1956) algorithm can be used, in which the lowest weight edge is always added to see if it builds a spanning tree; if so, it is added or otherwise discarded. This process continues until the tree is constructed. An example is shown in Figs. 3.8.7 for the 13-sample aspirin data. A complete tree for this data set using three dimensions and the MMDS-derived coordinates is shown in Fig. 3.8.7(a). This has 12 links between the 13 data points. Reducing the number of links to 10 gives Fig. 3.8.7(b).
References
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48–50.Google Scholar