Development and application of a new method for detection of structural equivalence in graphs

Abstract

This thesis mainly concerns the isomorphism problem encountered in computerized structural synthesis of kinematic chains. The contributions of the thesis to the study of structural aspects of linkages are the following. 1. Development of a fast and reliable isomorphism test for simple-jointed kinematic chains. The proposed test is based on graph-theoretic modelling of visual inspection of chains/graphs. Using this model, the relative disposition of each link (vertex) in a chain (graph) is eventually reduced to a number which is referred to as the representation number. The collection of all such numbers for different links (vertices) of a chain (graph) is referred to as the representation set. This set is used as an isomorphii�m index. The new test based on the representation set has been applied to all known kinematic chains and several cospectral graphs to establish its reliability. It has been successful in detecting structural isomorphism in all these cases. For the typical case of 10-link,1- fj^eedom chain, the computation time taken by the proposed isomorphism test is about one-eighth of the time required by the existing test based on the characteristic polynomial of the adjacency matrix of the chain. Thus the new test has been found to be bestsuited for incorporating in computerized structural synthesis of kinematic chains. I 2. Development of a new isomorphism test for multiple-jointed kinematic chains. 'Fictitious links' are added to the multiple-jointed chain at all those locations where multiple joints occur to obtain an associated simple-jointed chain. The representation set of this simple-jointed chain is used as the index of isomorphism of the corresponding multiple-jointed chain. This test has been found to be successful in detecting isomorphism in chain with upto nine . links- 3. Development of an efficient method to derive distinct mechanisms from the given kinematic chain. The method essentially utilizes the representation set of the chain and subchains. All known kinematic chains have been considered for applying this test to successfully establish its reliability. 4. Application of the new tests referred to under items 1-3 above to structural synthesis of kinematic chains. The new isomorphism tests and the mechanism derivation method developed in the present work are combined with an existing method of structural synthesis to develop a computer program for structural synthesis of kinematic chains. The effectiveness of this synthesis program is established by applying it to some known cases of chains. Its application to the new caseof 11-link,2-freedom, simple-jointed chains showed that there are 839 chains in this category, giving rise to 7898 mechanisms. Of the 839 chains, 66 possess total freedom, 86 have fractionated freedom, and the remaining 687 have partial freedom. Further study revealed that there are 17 pairs and 1 triplet of cospectral chains in this category. These results are presented and discussed in the thesis.