Graph reduction

Figure 2-36. Identification of the number of rings in adamantane after graph reduction (the different ring systems are highlighted with bold lines). Note that a graph does not car 3D information thus, the two structures on the upper right-hand side are identical.

Triptycene (151) is a simple example of a star topology for a bigraph. Harold Hart has built on this motif in his design of heptaiptycene (152) tritriptycene (153) and supertriptycene [230]. These rigid hyperbranched structures are among the first dendritic structures and show remarkable inclusion properties. Depicting these structures as their graph reductions evokes additional mole-... 

A second and complementary basis for chemical graph reduction is provided by differentiation between contiguous assembUes of carbon atoms and heteroatoms. This is illustrated in Figure 3 for the same structure. Once again, it is possible to ring the changes on the detail given. 

GRAPH REDUCTION BY HE.ANS OF CARBON AND HETERO ATOM AGGREGATION WITH ATOM RANGES... 

The complexity of the generic structures in the database, and the comparative strengths of each of the methods of chemical graph reduction are illustrated in Figure 10. 

The j-th measured variable is nonredundant if and only if arc j is deleted by the graph reduction (merging the nodes connected by unmeasured streams). 

Clearly, if the arc j closes a circuit with certain unmeasured streams then its both endpoints are merged by the graph reduction, being connected by a sequence of arcs 1 e J whose endpoints thus lie in one connected component G . Conversely if the endpoints of arc j lie in the same G then there exists a path in Gj between the endpoints, hence arc j closes a circuit with some arcs i e J . We thus have the criterion... 

One of the node balances has been eliminated by graph reduction (as the merged-nodes balance) and the remaining two read... 

Recall that a connected component can also consist of one (isolated) node, with empty subset of incident arcs. Having merged the nodes of each N,j in G we have the reduced graph G see Fig. 3-7. The K nodes of G correspond uniquely to the K subsets N, of N. By the graph reduction (merging), we have deleted all the arcs j e J°, and some arcs j g J in addition (subset J c J ). The arc set of G , denoted by J, consists of the remaining (not deleted) arcs j e J. Thus J"" is partitioned... 

Then in particular the graph reduction according to Chapter 3 (or any other equivalent elimination method according to Chapter 7) is governed by the operations on submatrix B, and corresponds to the matrix transformation... 

Let us consider the graph reduction. The corresponding matrix operation is summation of rows of the full incidence matrix over each subset of nodes constituting a connected component of G . The connected component containing the reference (environment) node is further not considered and the Af (= Af-1) rows of the submatrix (A/, A ) are thus sums of rows of (C, ) over the respective nodes of the remaining... 

The most efficient perception routines use a mix of breadth-first trace, linear algebraic combination of the resultant ring vectors, and graph reduction during processing. These routines perform ring perception in polynomial time rather than exponential. 

---