Enumeration tree

To make the ideas of this section more concrete we will use a specific example of a flowshop problem. The problem is a small one, only five batches will be considered, since this enables us to examine the enumeration tree by hand. 

Fig. 1 Samples of enumeration trees for (a) frequent subsequences and for (b) frequent subgraphs...

An important point of the enumeration tree is that we can enumerate all subsequences completely without any duplication by traversing an enumeration tree as a search space. This tree-shaped search space thus ensures the uniqueness of each subsequence attached to a node and the completeness on searching all frequent subsequences. 

The enumeration tree can be generated for subgraphs in a similar manner, as shown in Fig. lb, and these subgraphs are used in the next subsection (see Note 5). 

Fig. 2 An example of the search space. The search space (c) is defined as the graph product of two enumeration trees for subsequences (a) and for subgraphs (b). (c) Covers all possible frequent subgraph-subsequence pairs...

In practice, all combinations of frequent subgraphs and frequent subsequences may have a lot of infrequent subgraph-subsequence pairs, and so we can use the downward closure property on the product graph of the two enumeration trees, which can be clearly stated as follows ... 

The recursion rules in Proposition 2 make us keep all instances explicidy in the graph product T xTs. That is, Q SM must be kept and be passed to subsequent nodes. This is a space-consuming procedure, because two enumeration trees are practically very huge. Thus, we can consider a depth-first traversal of the graph product T x T by simplifying recursion rules in Proposition 2 into those in the following Proposition 4 (see Note 6). 

Fig. 3 A sample for enumerating all subgraph-subsequence pairs with the support of 3 or larger of 10 graph-sequence pairs (1,2,..., 10). This table corresponds to two enumeration trees of Fig. 2a, b...

We first build enumeration tree X, which corresponds to generating all subgraphs in the top row of Fig. 3, and then starts traversing enumeration tree Xjfrom the root. By traversing Xjin a... 

The support of a subgraph-subsequence pair is monotonically decreasing with increasing the size of the subgraph or the subsequence, meaning that a subgraph on a deeper level in an enumeration tree has a smaller support. 

It is also of interest to study the way accuracy changes as sensors are added. This is shown in Table 2 and Figure 5. This would correspond to the first branch of the enumeration tree (no branching criteria used). 

Rymon R, Zheng B, Chang YH et al (1998) Incorporation of a set enumeration trees-based classifier into a hybrid computer-assisted diagnosis scheme for mass detection. Acad Radiol 5 181-187... 

It is illustrated in Section 3.4.4 by tracing the paths for leaking engine compression and applied to fault tree construction for the FFTF reactor Fullwood and Erdmann, 1974). The method involves writing Boolean equations for all paths whereby hazardous material may be released. It is primarily useful for enumerating release paths, but not for what started the release It was used to enumerate the possible paths for stealing nuclear bomb material from a facility. 

Camphor, Cj HjgO, occurs in the wood of the camphor tree Laurus camphora) as dextro-camphor. This is the ordinary camphor of commerce, known as Japan camphor, whilst the less common laevo-camphor is found in the oil of Matricaria parthenium. Camphor can also be obtained by the oxidation of borneol or isoborneol with nitric acid. Camphor may be prepared from turpentine in numerous ways, and there are many patents existing for its artificial preparation. Artificial camphor, however, does not appear to be able to compete commercially with the natural product. Amongst the methods may be enumerated the following —... 

A paper in the same journal [PolG36b] elaborated on isomer enumeration and the corresponding asymptotic results. Here the functional equations for the generating functions for four kinds of rooted trees were presented without proof. They were, in a slightly different notation, formulae (8), (4), and (7) in the introduction to Polya s main paper, and one form of the functional equation for the generating function for rooted trees. From these results a number of asymptotic formulae were derived. These results were all incorporated into the main paper. 

A considerable part of Polya s paper is concerned with trees and their enumeration. Indeed, in his introduction, Polya states that his work is a continuation of that done by Cayley on this kind of enumeration. 

It was largely this chemical interpretation which led Cayley to enumerate various kinds of trees. He gave (without much of a proof) the formula for the number of trees on n labelled vertices [CayA89], and the equation... 

The use of Polya s Theorem in the enumeration of rooted trees is amply described in Polya s paper and needs little comment here. We shall note an important point in connection with the enumeration of alkyl radicals. A radical is a portion of a molecule that is regarded as a unit that is, it will be treated much the same as if it were a... 

Polya s main results on tree enumeration are summarized at the beginning of Section IV of his paper. His equation (4.8) gives the functional equation for the generating function of rooted labelled trees, from which Cayley s result, referred to above, follows... 

Both Cayley and Polya were able to enumerate unrooted trees and C-trees, but the methods they used were somewhat involved. A significant improvement in the enumeration of these trees, also known as "free" trees, was made by Otter [OttR48]. Otter s method depends on the concept of a dissimilarity characteristic, and deserves a brief description. 

The enumeration result that we want is obtained by summing the equation of the theorem over all unrooted trees with a given number p of vertices. Thus we have... 

A question which chemical enumerators should not ignore is that of the extent to which their results are realistic in the physical world. Thus in [BlaCSla] it is stated that the number of alkanes (paraffins) with 40 carbon atoms is 62,491,178,805,831. Can we really be sure that all these compounds can exist or could it be that factors not catered for in the enumeration render some of them chemically infeasible In this connection we should note the paper [KleD81], in which it is shown jthat because of such factors the chemical tree enumerations by Polya and others give numbers that are consistently higher than the number of compounds that are in fact chemically possible. This does not detract from the mathematical value of these results it merely shows that care is needed in relating them to problems of real life. 

A series of four papers by G. W. Ford and others [ForG56,56a,56b, 57] amplified this work by using Polya s Theorem to enumerate a variety of graphs on both labelled and unlabelled vertices. These included connected graphs, stars (blocks) of given homeomorphic type, and star trees. In addition many asymptotic results were derived. The enumeration of series-parallel graphs followed in 1956 [CarL56], and in that and subsequent years Harary produced... 

Further progress in asymptotic tree enumeration was made by Otter, who in [OttR48] considered the problem of rooted and unrooted trees with maximum degree m. Having enumerated unrooted trees by the method already described, he proceeded to derive asymptotic estimates, and after ten pages of analysis arrived at a number of results, of which the following is typical ... 

HarF70 Harary, F., Read, R. C. Enumeration of tree-like polyhexes. Proc. Edin. Math. Soc. Ser. II 17 (1970) 1-13. 

---