An isomorphism identification method of kinematic chain based on optimal arrangement and comparison of branch-chain matrix derived from dendrogram graph

Abstract

Isomorphism identification is an essential step in the structure synthesis of Kinematic Chain (KC), and needs a large amount of analysis and calculation. To find an isomorphism identification method with simple rules, scientific feasibility and less analysis and calculation has always been a research hotspot of mechanism scholars. In this paper, the structure information of KC is described by dendrogram structure graph with multiple joints, and Branch-chain Matrix (BM) is separated from the dendrogram structure. The characteristics of BM are analyzed, and the concepts of intimacy between branch-chains and Repeatability Matrix (RM) corresponding to BM are proposed. Based on fact that both dendrogram graph and BM can uniquely determine the structural information of one KC, a new isomorphism identification method for KC, based on row optimal rearrangement and comparison of BM, is proposed. The operation steps are discussed in detail, and several cases are analyzed to show this method has advantages such as easy rules, small calculation of retrieval and comparison, and easy to be programmed.

Introduction

Isomorphism identification is a basic problem that must be solved in the process of KC structure synthesis, and it’s C_n² n calculations between KCs so it need be optimized in each comparison, accompanying with the correction. It was a research hotspot in mechanism since the 1960s, with the development, several isomorphism identification methods were proposed by mechanism scholars.^1–10

The existing isomorphism identification methods can be roughly divided into the following categories.

Characteristic polynomial method, Uicker and Raicu ¹¹ proposed characteristic polynomial method of vertex adjacency matrix (CPAM) for isomorphism identification by calculating and comparing the characteristic polynomial coefficients of adjacency matrix; Krishnamurthy ¹² used the weighted KC links and replace the 1 in adjacency matrix with the weighted letter λ, then the isomorphism was determined by comparing the structure of determinant of adjacency matrix. The characteristic polynomial method based on parameter matrix which was proposed by Balasubramanian and Parthasarathy ¹³ is to replace 1 in the adjacency matrix with λ, replace 0 with 1, and then calculate and compare the determinant polynomial structure to determine isomorphism. Yan and Hwang ¹⁴ proposed a structural matrix characteristic polynomial method containing the adjacency relationship of edges, the adjacency relationship of vertices and the correlation information of vertices and edges. Dubey and Rao ¹⁵ modified the vertex adjacency matrix to obtain the distance matrix, and then characteristic polynomial method was used to judge the isomorphism. Mruthyunjaya and Balasubramania ¹⁶ proposed the degree matrix characteristic polynomial method to determine isomorphism by comparing the characteristic polynomials of the degree matrix composed of the sum of the degrees of two connected vertices and 1.

Coding method, Ambekar and Agrawal ¹⁷ proposed the maximum and minimum coding method, first the links in KC were numbered, the largest or smallest degree of vertex were selected as the main vertex, other vertices were rearranged according to their degree, the numbers of upper triangular matrix of the adjacency matrix were connected in series to form a binary code, the decimal value corresponding to the binary code were counted to determine isomorphism. Tang and Liu ¹⁸ proposed the degree code method, the vertices were arranged with their degrees in descending order, and then the numbers of upper triangular matrix were combined in binary code for isomorphism identification. Fang and Freudensein ¹⁹ simplified the topological embryo graph, inserted values on the edge to represent the path of the vertex, and the quadratic points corresponding to the path, then arranged the rows and columns of the hierarchical adjacency matrix to obtain the hierarchical code, at last the hierarchical code were used to determine the isomorphism.

Hamming string method, hamming code had been used to research the topology of KC for the first time by Rao, and had been improved three times. Rao and Rao ²⁰ used vertex adjacency matrix to establish hamming matrix. Then Rao defined second-order Hamming matrix and second-order Hamming string. In 1993, Rao further proposed the method of link-loop matrix to establish Hamming matrix. After that, many isomorphism identification methods based on Hamming number method were emerged. The representative split Hamming string was proposed by Dharanipragada and Chintada ²¹ to do isomorphism identification for KC with prismatic pairs. Zhao et al. ²² proposed a new method to get the Hamming matrix with the connecting link adjacency matrix as the known condition, then calculated the square matrix of the Hamming matrix and set the main diagonal elements in the square matrix to zero, then solved the eigenvalue of the square matrix, and finally summed the product of the eigenvalue and the topological factors to obtain the isomorphic identification code of the KC’s topological graph.

Eigenvalues and eigenvectors of adjacency matrix, Sunkari and Schmidt ²³ proposed isomorphism identification based on eigenvalues and eigenvectors of adjacency matrix in 2006. Zang and Li ²⁴ proposed a method later to calculate the eigenvectors corresponding to the eigenvalues of the two matrices respectively, on basis of constructing the adjacency matrix describing any graph, then found the possible isomorphic mapping according to their maximum independent groups, and the isomorphism of the graph by examining all eigenvalues can be judged one by one.

Other representative method, such as Ding and Huang’s ²⁵ maximum perimeter loop method, the maximum perimeter loop was obtained by merging the basic loop sets, further the canonical adjacency matrix can be got with all links in it, then determine the isomorphism by compare and analyze a limited number of possible canonical adjacency matrices. Wu and Nie ²⁶ got the longest loop in the reduced link adjacency matrix with the maximum pairs link taken as the first link to generate other loops, then determined the isomorphism by judging whether each loop corresponds to congruence one by one.

In 2012, Lohumi et al. ²⁷ proposed an expression for KC with weighted square shortest path distance matrix firstly, and turned into dendrogram graph with hierarchical clustering algorithm, inheritance relative coefficients of dendrogram graph were used as the basis of KC isomorphic identification. Hierarchical clustering approach was a widely used method, in which all samples were classified, and the distance between classes were defined, then two classes with smallest distance were merged into a new class, the above process should be implemented till only one class merged at last. The dendrogram graph is one visual expression for hierarchical clustering approach, there have two construct form: agglomerative hierarchical clustering and divisive hierarchical clustering, according to different construct method, one is from top to bottom, while the other is from bottom to top.^28,29

Most of the isomorphism identification methods proposed by scholars are based on the adjacency matrix. While adjacency matrix does not contain the information of polygonal links or multiple joints, not to mention that for a polygonal link, which pair links another link, so isomorphism identification methods based on adjacency matrix are not sufficiency and necessity. For example, the Hamming string method ³⁰ had been found a counter example, the fundamental reason is that Hamming string method only extracts the connection relationship between links, and the process of extracting information is very cumbersome and complex.

In this paper, the dendrogram graph derived from graph theory is introduced to express the KC, and the branch-chains is separated from dendrogram graph based on the connect relationships of links, then Branch-chain Matrix (BM) is generated. The characteristics of BM are analyzed, and the concepts of Repeatability Matrix (RM) and Intimacy between branch-chains are proposed. Based on fact that the KC structure information can be uniquely expressed by dendrogram graph or BM, a new KC isomorphism identification method based on row optimal rearrangement and comparison of BM is proposed. Finally, the effectiveness and reliability of this method are proved by several cases.

Relevant theory

Dendrogram structure graph of KC

There has no loop in the dendrogram graph in clustering class, and the degree of nodes in clustering class is no more than 2. But loops, multiple joints and polygonal links are common in the closed KC, so the dendrogram graph of KC proposed in this paper is different from that in hierarchical clustering approach, and some rules are added to fulfill the expression of KC. Figure 1(c) is a dendrogram graph with quaternary link 10 as the root node in KC1 shown in Figure 1(a), and Figure 1(d) is a dendrogram graph with quaternary link 12 as the root node in KC2 shown in Figure 1(b).

Figure 1.

KCs and their corresponding dendrogram graph: (a) KC1, (b) KC2, (c) dendrogram graph of KC1, and (d) Dendrogram graph of KC2.

The characteristics of KC’s dendrogram structure graph proposed in this paper are as follows.

• (1) The node in the first layer of the dendrogram graph is called root node, and there has only one root node. Maximum polygonal link or multiple joints is suggested to be selected as the root node to reduce the line-crossings.

• (2) The child nodes of the same parent node are arranged randomly according to the retrieved connection relationships, and they are in the same layer. When there has a connection relationship between the child nodes of the same layer, new connector Bi (i = 1, 2, …) is used to indicate their connect relationship.

In Figure 1(c), there is a connection relationship between child nodes 2 and 4 in the fourth layer, so B1 is used to represent their connection.

• (3) The multiple joints are regarded as links with geometric dimension 0 and expressed by Ji (i = 1, 2, …, i is the serial number of multiple joints) to distinguish with polygonal link, and its type can be obtained from the graph or connect information based on analysis.

One multiple joints which connecting links 1, 2, and 5 in Figure 1(a) is named as J1 in Figure 1(c) and regarded as a link.

• (4) Once the root node is selected, the child nodes in each layer is determined.

The dendrogram graphs of KC1 and KC2 are shown in Figure 1(c) and (d), corresponding to Figure 1(a) and (b), in which the quaternary link 10 in KC1 and the quaternary link 12 in KC2 are taken as the root nodes respectively, the layer of other child nodes are determined.

• (5) Due to the random locations of child nodes in each layer, the corresponding dendrogram graph are different.

For example, if the locations of link 9 and 11 are exchanged in Figure 1(c), then there would generate a new dendrogram graph.

• (6) For closed KCs, all links are in the loops. In the dendrogram graph, different branch-chains should be connected in two ways in a certain layer. The first is that more than two branch-chains connected with one same child node, and this child node has no its own child node, and the second is that two child nodes in the same layer are connected, then Bi is added to express their connection.

For example, in Figure 1(c), the child node 7 links two parent nodes 8 and 13 with two different branch-chains, while child nodes 2 and 4 are in the same layer and connect each other, so symbol B1 is added between them to indicate their connection relationship.

• (7) The multiple joints are regarded as polygonal link with geometric dimension of 0, and are placed in KC, so to reduce the line-crossings between child nodes and to enhance the visibility of the loops.

Branch-chain and branch-chain matrix (BM)

Definition of branch-chain: all links or multiple joints are retrieved from the root node till the end nodes or connect symbol Bi according to their connect relationships, there are two situations when a branch-chain is generated, one is that a child node is connected by two or more parent nodes, and this child node has no its own child nodes, the other is that two or more child nodes in the same layer have connect relationships.

All nodes in every one branch-chain are different, and these nodes are stored in an one-dimensional array. For example, in KC1, if the quaternary link 10 is taken as the root node, the dendrogram graph shown in Figure 1(c) can be obtained. According to the branch-chain definition proposed above, all branch-chains are retrieved from the dendrogram graph in turn and listed in Table 1.

Table 1.

All branch chains corresponding to KC1.

Number	Branched array
1	10-1-J1-2-B1
2	10-1-J1-5
3	10-1-3-4-B1
4	10-9-6-5
5	10-9-8-7
6	10-11-3-4-B1
7	10-11-12-7
8	10-12-6-5
9	10-12-13-7

If the dendrogram graph of one KC is obtained, such as dendrogram graph in Figure 1(c) and (d), or all branch-chains as shown in Table 1 are obtained, then the structure information of KC as shown in Figure 1(a) and (b) can be deduced and determined.

The branch-chains of KC have the following characteristics.

1. The dendrogram graph is composed by the root node and child nodes in each layer with the connection relationship, so the same child nodes of each branch-chain are on the same layer.

2. The number and length of branch-chains corresponding to different root nodes may be different, but for a certain root node, the above information is uniquely determined.

For the KC1, if multiple joint J1 is taken as the root node, its dendrogram graph is shown in Figure 2, it’s different from the dendrogram graph in Figure 1(c). All nine branch-chains shown in Table 1 should be unchanged on the basis that quaternary link 10 is selected as the root node.

Figure 2.

Another dendrogram graph of KC1.

All branch-chains are separated from the dendrogram graph, but the structural information of KC does not lose during separation, because the same numbers in different branch-chains keep the connection relationship between these branch-chains. The dendrogram graph is separated into finite branch-chains’ combination, and length of the longest branch chain is taken as the length of all branch-chains, 0 is appended for length deficiency. Each branch-chain is separated into link number which are the elements of one row in Branch-chains Matrix (BM), several branch-chains construct the rows of BM.

Taken link 10 and link 12 as the root nodes in KC1 and KC2 respectively, as shown in Figure 1(a) and (b), and their BMs are BM1 and BM2.

$$B{M}_1=\left(\begin{array}{ccccc}10\hfill & 1\hfill & J1\hfill & 2\hfill & B1\hfill \\ \multicolumn{1}{c}{10}& 1\hfill & J1\hfill & 5\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 1\hfill & 3\hfill & 4\hfill & B1\hfill \\ \multicolumn{1}{c}{10}& 9\hfill & 6\hfill & 5\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 9\hfill & 8\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 11\hfill & 13\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 11\hfill & 3\hfill & 4\hfill & B1\hfill \\ \multicolumn{1}{c}{10}& 12\hfill & 6\hfill & 5\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 12\hfill & 13\hfill & 7\hfill & 0\hfill \end{array}\right)B{M}_2=\left(\begin{array}{ccccc}12\hfill & 5\hfill & 4\hfill & 3\hfill & B1\hfill \\ \multicolumn{1}{c}{12}& 5\hfill & 6\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 8\hfill & 6\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 8\hfill & 9\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 10\hfill & 9\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 10\hfill & 11\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 13\hfill & J1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 13\hfill & J1\hfill & 2\hfill & B1\hfill \\ \multicolumn{1}{c}{12}& 13\hfill & 4\hfill & 3\hfill & B1\hfill \end{array}\right)$$

It can be deduced that BM has the following characteristics:

• (1) For the same root node, the branch-chains would have different positions in the BM because of random locations of child nodes.

KC3 is shown in Figure 3(a), link 9 of KC is taken as root node, its dendrogram graph is shown in Figure 3(b), if the locations of link 4 and link 10 are exchanged, then a new dendrogram structure graph is shown in Figure 3(c). There has no cross in Figure 3(c), while there have two line-crossings in Figure 3(b), they are 4-5, 4-3 with 10-8.

• (2) The number of rows and columns of BM are uniquely determined once the root node is confirmed, and they are the number of branch-chains and the maximum number of layers of child nodes respectively.

• (3) The exchange between rows in BM means the change of adjacent relationship between branch-chains. Each branch-chain represents the link connection relationship from the root node to the end, so the locations of elements in columns of the BM cannot be changed.

• (4) The first column elements of rows in the BM are the root node number, which are the same number. The number of each child node in other columns varies according to the selected root node, but the numbers of the same child nodes appear in the same column.

Figure 3.

Different dendrogram graph with links’ location exchange: (a) structure graph of KC3, (b) dendrogram graph, and (c) dendrogram graph.

For example, BM1′ with J1 as the root node of KC 1 is shown below, and BM1 with 10 as the root node, they have different numbers of child nodes in the second column, but each number only appears in the same column. For example, element 10 in the third column of BM1′ only appears in rows 3–5.

$${\mathrm{BM}}_1^{\prime }=\left(\begin{array}{cccccc}J1\hfill & 1\hfill & 3\hfill & B1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{J1}& 1\hfill & 3\hfill & 11\hfill & 13\hfill & 7\hfill \\ \multicolumn{1}{c}{J1}& 1\hfill & 10\hfill & 11\hfill & 13\hfill & 7\hfill \\ \multicolumn{1}{c}{J1}& 1\hfill & 10\hfill & 9\hfill & 8\hfill & 7\hfill \\ \multicolumn{1}{c}{J1}& 1\hfill & 10\hfill & 12\hfill & 13\hfill & 7\hfill \\ \multicolumn{1}{c}{J1}& 2\hfill & 4\hfill & B1\hfill & 0\hfill & 0\hfill \\ \multicolumn{1}{c}{J1}& 5\hfill & 6\hfill & 9\hfill & 8\hfill & 7\hfill \\ \multicolumn{1}{c}{J1}& 5\hfill & 6\hfill & 12\hfill & 13\hfill & 7\hfill \end{array}\right)$$

• (5) The same number in the same column between different rows in BM represents the coupling relationship between different rows or branch-chains.

For example, in BM1′ the numbers and symbols J1, 1 and 3 in the first three columns of the first and second branch-chain are the same, indicating that the two branch-chains are coupled together at the first three nodes.

The adjacency matrix of KC is the link-link connection relationships matrix, there are only 1 and 0 in the matrix corresponding to connect or not connect of any two links, so it’s a symmetrical matrix, and all the elements in diagonal are 0. If any two links’ position exchange, there should be two rows and two columns exchange in adjacency matrix. Scholars proposed that two topology graphs should be isomorphic under the conditions that after several exchanges of rows and columns, ³¹ but this is not a necessary and sufficient conditions that connection relationships of links are the same of two KCs. The branch-chain matrix (BM) proposed in this paper are obtained by separating all branch-chains from the coupled dendrogram graph, the same column elements in different rows represent the adjacent relationships of these rows, any two rows can be exchanged in BM. But all elements in one row represent the connections from the root node to the end node, so different columns can’t be exchanged in BM, it means that one element in BM has changeable row but unchangeable column.

Related properties of BM

Repeatability of link: the number of one link appears in one row can only appear in this column for other rows, according to properties of the dendrogram graph. The times of one element appeared in different rows and same columns are counted and taken as the repeatability of this link.

For example, in BM1, the root node 12 appears nine times in the first column of all rows, the repeatability of link 12 is 9. The child node 1 appears three times in the first three rows and second column of BM1, so the corresponding repeatability of link 1 is 3.

By searching the BM of the KC, the Repeatability Matrix (RM) corresponding to the BM of the KC is obtained. In Figure 1(a) and (b), the RMs of the two KC are RM1 and RM2 respectively.

$$R{M}_1=\left(\begin{array}{ccccc}9\hfill & 3\hfill & 2\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 2\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 1\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 2\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \end{array}\right)R{M}_2=\left(\begin{array}{ccccc}9\hfill & 2\hfill & 2\hfill & 2\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 3\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 1\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 2\hfill & 3\hfill \end{array}\right)$$

Intimacy between rows: if two rows share the same link number in one column, then the number of this column is used to represent the intimacy between these two rows. Regardless of the root node or the first column element, because all rows share the same root node in first column in BM. The smaller the number of column, the higher the intimacy.

For example, the second column of the first two rows in BM1 are the same, and the third column elements of the third row are the same with the seventh row.

If the mth column element in row i, j, k is the same, then (m + n)th column elements of these rows should be compared, while $m\ge 2$ , $\mathrm{n}\ge 1$ . If the former column elements are the same, then the later column element should be compared.

For example, the first row of branch-chain 1 (10-1-J1-2-B1) in BM1 is the same as the second column element 1 of branch-chain 2 (10-1-J1-5-0) and branch-chain 3 (10-1-3-4-B1), and the third column elements J1 and 3 of branch chain 2 and 3 continue to be used to compare with the third column element J1 of branch chain 1. The two branch chains with the same element J1 in the third column have a high degree of intimacy.

For most isomorphism identification, the KCs are coupling and closed in which branch-chains connect each other by intimacy. The proposition of intimacy is to find a sorting standard for all rows in BM, then rearrange the rows orderly.

Isomorphism identification principle based on BM

For two isomorphic KCs, whether one or more or all their structural properties are selected for comparison, it will get the same conclusion that they are same. A wrong isomorphism determination method and wrong result may be drawn because of only one or more but not sufficient and necessary information of KC are extracted for isomorphism identification. If the extracted structure information or expression of one isomorphism method can deduce the KC structure completely and uniquely, that is, the extracted KC information is sufficient and necessary, the isomorphism identification method is very intuitive and scientific.

Based on the above analysis, it is very clear that BM is composed of several branch-chains which are separated from the dendrogram graph, and the unique and complete KC structural information can be deduced by one BM, so BM can be used for isomorphism identification of KCs.

If two KCs are isomorphic and the relative positions of each row in BM are in the right position, the links’ mapping relationship of two KCs can be found quickly according to their positions. The key problem in isomorphism identification with BM is to formulate rules, obtain only one or a few possible BMs with possible assembly of rows, and compare whether all elements comply with the mapping relationship one by one to obtain the isomorphism identification result.

The isomorphism identification principle based on BM is as follow: the same type of polygonal link or multiple joints is selected as the root node in KC1 and KC2 respectively, assuming these two links or multiple joints have mapping relationship, then the corresponding BMs and RMs of 1 and 2 are obtained. One row with unique repeatability is selected as the first row of the two BMs, then all other rows are rearranged based on the intimacy comparing with the former row. If BM1 and BM2 which are rearranged according to the repeatability and intimacy are isomorphic, they should satisfy this condition: the position of any one link number i in BM1, according to the branch chain characteristic (4), these one or several same numbers should be in the same column, while the link number j in BM2 which has a mapping relationship with link number i should be in the same position. If all the numbers in BM1 and BM2 meet the above rules, it can be determined that this two KCs are isomorphic, and any two links in the same position between two BMs have one-to-one mapping relationship.

Note that in the above process, because of the diversity of root node selection, there may be several BMs generated by KC2 corresponding to all possible matching root nodes. Any one of BMs matches the mapping relationship, it can be determined that this two KCs are isomorphic. If all the possible BMs do not match the mapping condition, it can be determined that they are non-isomorphic.

Isomorphism identification examples and steps

According to the above theoretical analysis, the isomorphism identification process of KC1 and KC2 shown in Figure 1 is analyzed.

• Step 1: The structural parameters of the two KCs are retrieved and compared.

The structural parameters of the KC are described by a one-dimensional array $(n,p,F,L,n_2,n_3,J_3\cdots n_{L+1},J_{L+1})$ which composed by the total number of links n, the number of lower pairs P, the number of degrees of freedom F, the number of basic loop set L, the number of polygonal links and multiple joints $n_2,n_3,J_3\cdots$ . The structural parameters of KC1 and KC2 in Figure 1 are the same (13,18,0,6,5,7,1,1,0,0,0,0,0,0,0).

• Step 2: Find the smallest number of polygonal links or multiple joints in KC1 as the root node to reduce the matching possibility. If this number is greater than 1, there are several matching possibilities of BM2 later.

For example, if any one binary link in KC1 is selected as the root node, there should be five matching possibilities of binary links such as 123,711 in KC2. There have only one 4-joints and one quaternary link 10 in KC1, any one of them is suggested to be selected as the root node, here the quaternary link 10 is selected as the root node in KC1. Then in KC2, the unique quaternary link 12 is also selected as the root node, and these two quaternary links have mapping relationship if they are isomorphic.

• Step 3: All branch-chains are generated according to the root node, then BMs of KCs are constructed in which the number of rows in BM is the total number of branched-chains, and the number of columns in BM is the length of the longest branched-chain. For those branch-chains whose length is smaller than column of BM, 0 is appended later.

BM1 and BM2 corresponding to KC1 and KC2 are generated and showed above.

• Step 4: RM1 and RM2 of KC1 and KC2 are retrieved and obtained, rearrange the rows of RMs according to the column number from large to small, and compare whether the two RMs are the same.

By rearranging the rows of RM1 and RM2 of KC1 and KC2, it can be found that the final RMs of two KCs are the same after sorting, and RM1 and RM2 are obtained.

$$R{M}_1=R{M}_2=\left(\begin{array}{ccccc}9\hfill & 3\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 2\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 2\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 1\hfill & 3\hfill & 0\hfill \end{array}\right)$$

• Step 5: One row is selected whose elements is different from other rows in RM1. If there are several rows with same repeatability, select one row as the first row of a new BM3 corresponding to KC1.

Retrieve RM3, in which (9,3,2,2,3), (9,3,2,1,3), and (9,2,2,3) have the longest length and uniqueness. Randomly select the row (10-1-J1-2-B1) with the repeatability of (9,3,2,1,3) as the first row of BM3.

• Step 6: For the remaining rows in BM1, the following operations are done repeatedly: find one row in BM1 which has the maximum intimacy with the last row in BM3, and delete it from BM1, then append it to BM3. If there are at least two rows in BM1 have the same maximum intimacy with the last row in BM3, choose one at random.

In step 5, row (10-1-J1-2-B1) in BM1 is selected as the first row in BM3, then the row (10-1-J1-5-0) is selected as the second row in BM3, because its first three columns are the same with the first row and has the maximum intimacy with the first row in BM3. Then the row (10-1-3-4-B1) has the maximum intimacy with the second row in BM3 and is selected as the third row. The subsequent sequencing is a repetition of the above process and is not repeated here, the new BM3 is generated.

$$B{M}_3=\left(\begin{array}{ccccc}10\hfill & 1\hfill & J1\hfill & 2\hfill & B1\hfill \\ \multicolumn{1}{c}{10}& 1\hfill & J1\hfill & 5\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 1\hfill & 3\hfill & 4\hfill & B1\hfill \\ \multicolumn{1}{c}{10}& 11\hfill & 3\hfill & 4\hfill & B1\hfill \\ \multicolumn{1}{c}{10}& 11\hfill & 13\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 12\hfill & 13\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 12\hfill & 6\hfill & 5\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 9\hfill & 6\hfill & 5\hfill & 0\hfill \\ \multicolumn{1}{c}{10}& 9\hfill & 8\hfill & 7\hfill & 0\hfill \end{array}\right)R{M}_3=\left(\begin{array}{ccccc}9\hfill & 3\hfill & 2\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 3\hfill & 2\hfill & 2\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 2\hfill & 3\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 1\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{9}& 2\hfill & 2\hfill & 3\hfill & 0\hfill \end{array}\right)$$

• Step 7: After all rows of BM3 are confirmed, its Repeatability Matrix (RM3) can also be obtained easily.

• Step 8: One row in BM2 which has the same Repeatability comparing with the first row of RM3 is selected as the first row of new BM4.

In this case, the row is (12-13-J1-2-B1) and its repeatability is (9,3,2,1,3). Therefore, this row is selected as the first row of BM4.

• Step 9: Repeat the following operations for the remaining rows in BM2: first reference to the RM3 which is also the RM4 of the final BM4 if these two KC are isomorphic, find one or more rows in BM2 which has the same repeatability in the same position in RM3. If there has only one row fulfill this condition, then it’s no use to compare the intimacy with the last row in BM4, and delete it from BM2, then append it to BM4. If there are at least two rows in BM2 have the same repeatability with the last row in BM4, then find a unique row among them by intimacy. Even in this condition there still have more than two rows match, then all of them should be regarded as the possibilities and more BM4 are generated.

In this case, there has not at least two rows match both the repeatability and intimacy with the last row of BM4, and thus only one BM4 is obtained.

$$B{M}_4=\left(\begin{array}{ccccc}12\hfill & 13\hfill & J1\hfill & 2\hfill & B1\hfill \\ \multicolumn{1}{c}{12}& 13\hfill & J1\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 13\hfill & 4\hfill & 3\hfill & B1\hfill \\ \multicolumn{1}{c}{12}& 5\hfill & 4\hfill & 3\hfill & B1\hfill \\ \multicolumn{1}{c}{12}& 5\hfill & 6\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 8\hfill & 6\hfill & 7\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 8\hfill & 9\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 10\hfill & 9\hfill & 1\hfill & 0\hfill \\ \multicolumn{1}{c}{12}& 10\hfill & 11\hfill & 7\hfill & 0\hfill \end{array}\right)$$

• Step 10: Compare BM3 and BM4 and determine the isomorphism of two KCs according to the isomorphism identification principle based on BM.

If two KCs are isomorphic, the locations of one or more same number i in BM3 should appear at the same position of number j in BM4, the links corresponding to these numbers have mapping relationships. When all the numbers in BM3 and BM4 satisfy the above requirement, isomorphism of the KCs corresponding to the two BMs can be determined.

In this case, all numbers in BM3 and BM4 are compared, and they match the above rules, so this two KCs are isomorphic and mapping relationships between links are shown in Table 2.

Table 2.

Mapping relationships between links of KC1 and KC2.

KC	KC1 (KC2)
Mapping relationship between link numbers	1 (13), 2 (2), 3 (4), 4 (3), 5 (1), 6 (9), 7 (7), 8 (11), 9 (10), 11 (5), 12 (8), 13 (6)

The process of a new KC isomorphism identification method based on optimal rearrangement and comparison of BM is shown in Figure 4.

Figure 4.

Process route of isomorphism identification method.

Examples of isomorphism identification

The isomorphism identification method based on BM is used to analyze the 28-links cases in literature. ³² The topology graph and links’ number are shown in Figure 5.

Figure 5.

Isomorphism identification case of 28 links: (a) topology graph of KC3 and (b) topology graph of KC4.

The main steps and result are analyzed.

• Step 1: Retrieve and compare the structural parameters of two KCs, they are the same [28,1,40,13,4,24,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0].

• Step 2: Select the root node. In this case, the minimum polygonal link of KC3 shown in Figure 5(a) is binary link, which is 3, 16, 27, 28 respectively. The root node of KC3 can randomly selected from these four links, while there are four matching possibilities to be selected as root node for KC4 as shown in Figure 5(b), that is 3, 11, 20, and 28. Link 3 of KC3 and link 20 of KC4 are selected as the root node for example.

• Step 3: Obtain BM5 and BM6 corresponding to KC3 and KC4.

• Step 4: Retrieve and obtain the RMs of BM5 and BM6, they are the same, and then rearrange them as follow.

$$\begin{array}{c}\multicolumn{1}{c}{B{M}_5=\left(\begin{array}{ccccccc}3\hfill & 2\hfill & 1\hfill & 14\hfill & 13\hfill & 12\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 1\hfill & 14\hfill & 15\hfill & 16\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 1\hfill & 26\hfill & 19\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 1\hfill & 26\hfill & 25\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 8\hfill & 7\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 8\hfill & 21\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 10\hfill & 11\hfill & 12\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 10\hfill & 17\hfill & 16\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 18\hfill & 19\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 18\hfill & 17\hfill & 16\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 6\hfill & 13\hfill & 12\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 6\hfill & 7\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 22\hfill & 15\hfill & 16\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 22\hfill & 21\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 24\hfill & 25\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 24\hfill & 11\hfill & 12\hfill & 28\hfill \end{array}\right)B{M}_6=\left(\begin{array}{ccccccc}20\hfill & 7\hfill & 6\hfill & 5\hfill & 4\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 6\hfill & 5\hfill & 18\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 6\hfill & 25\hfill & 10\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 6\hfill & 25\hfill & 26\hfill & 27\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 1\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 1\hfill & 17\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 23\hfill & 12\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 23\hfill & 24\hfill & 27\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 13\hfill & 12\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 13\hfill & 18\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 22\hfill & 26\hfill & 27\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 22\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 9\hfill & 10\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 9\hfill & 17\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 21\hfill & 4\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 21\hfill & 24\hfill & 27\hfill & 28\hfill \end{array}\right)R{M}_5=R{M}_6=\left(\begin{array}{ccccccc}16\hfill & 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 8\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \\ \multicolumn{1}{c}{16}& 8\hfill & 4\hfill & 2\hfill & 2\hfill & 4\hfill & 0\hfill \end{array}\right)}\end{array}$$

• Step 5: Retrieve the RM3 of KC3 and determine the first row of BM7.The two KCs have high symmetrical structure, there have only two groups of number in RM5, they are (16,8,4,2,2,4,8) and (16,8,4,2,2,4,0), corresponding to each eight rows. The first row in RM7 can be selected randomly, such as [3-2-1-14-13-12-28], and its corresponding repeatability [16-8-4-2-2-4-8] is recorded.

• Step 6: Based on intimacy, rearrange and generate BM7. In this case, because of the high symmetrical structure, there have many matching possibilities with the same intimacy in process, the rows are selected randomly.

• Step 7: According to the new position of rows in BM7, refresh and obtain repeatability matrix RM7, here RM7 is the same with RM5 and RM6.

• Step 8: There have eight rows in BM6 which have the same repeatability with the first row in BM7, it means in this step there have eight BM8 generated. Here one row [20-7-6-5-18-19-28] is selected randomly as the first row in one RM8 for example.

• Step 9: Continue to repeat the following operations till obtain all rows in BM8: first find one or more rows with the same repeatability with the last row in RM8, and then find the maximum intimacy row if there have more than one rows with the same repeatability. If there have more than two rows have the same repeatability and intimacy with the last row in RM8, then record all possibilities. In this case, because of the high symmetrical structure, there have many matching possibilities with the same repeatability and intimacy in process, here only one case is listed.

$$B{M}_7=\left(\begin{array}{ccccccc}3\hfill & 2\hfill & 1\hfill & 14\hfill & 13\hfill & 12\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 1\hfill & 14\hfill & 15\hfill & 16\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 1\hfill & 26\hfill & 19\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 1\hfill & 26\hfill & 25\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 8\hfill & 7\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 8\hfill & 21\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 10\hfill & 11\hfill & 12\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 2\hfill & 9\hfill & 10\hfill & 17\hfill & 16\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 18\hfill & 17\hfill & 16\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 18\hfill & 19\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 6\hfill & 13\hfill & 12\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 5\hfill & 6\hfill & 7\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 24\hfill & 25\hfill & 27\hfill & 0\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 24\hfill & 11\hfill & 12\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 22\hfill & 21\hfill & 20\hfill & 28\hfill \\ \multicolumn{1}{c}{3}& 4\hfill & 23\hfill & 22\hfill & 15\hfill & 16\hfill & 0\hfill \end{array}\right)B{M}_8=\left(\begin{array}{ccccccc}20\hfill & 7\hfill & 6\hfill & 5\hfill & 18\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 6\hfill & 5\hfill & 4\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 6\hfill & 25\hfill & 26\hfill & 27\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 6\hfill & 25\hfill & 10\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 23\hfill & 12\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 23\hfill & 24\hfill & 27\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 1\hfill & 17\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 7\hfill & 8\hfill & 1\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 22\hfill & 2\hfill & 3\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 22\hfill & 26\hfill & 27\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 13\hfill & 18\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 14\hfill & 13\hfill & 12\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 9\hfill & 10\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 9\hfill & 17\hfill & 19\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 21\hfill & 24\hfill & 27\hfill & 28\hfill \\ \multicolumn{1}{c}{20}& 15\hfill & 16\hfill & 21\hfill & 4\hfill & 3\hfill & 0\hfill \end{array}\right)$$

• Step 10: Compare the final BMs, that is, BM7 with all BM8 if there have more, and determine whether isomorphic according to the isomorphism identification principle of BM.

The specific determination process is not repeated any more. It can be concluded that the two KCs are isomorphic and there have more than one mapping relationship between their links, and two cases is shown in Table 3.

Table 3.

Mapping relationships between links of KC 3 and 4.

KC	KC 3 (KC 4)
Mapping relationship between link numbers	1 (6), 2 (7), 3 (20), 4 (15), 5 (14), 6 (13), 7 (12), 8 (23), 9 (8), 10 (1), 11 (17), 12 (19), 13 (18), 14 (5), 15 (4), 16 (3), 17 (26), 18 (22), 19 (26), 20 (27), 21 (24), 22 (21), 23 (16), 24 (9), 25 (10), 26 (25), 27 (11), 28 (28)
	1 (9), 2 (10), 3 (11), 4 (12), 5 (23), 6 (24), 7 (27), 8 (26), 9 (25), 10 (6), 11 (5), 12 (4), 13 (21), 14 (16), 15 (15), 16 (20), 17 (7), 18 (8), 19 (1), 20 (2), 21 (22), 22 (14), 23 (13), 24 (18), 25 (19), 26 (17), 27 (28), 28 (3)

The isomorphism identification method based on optimal rearrangement and comparison of BM separated from dendrogram graph has a faster identification speed for non-isomorphic KCs, the result can be deduced with several steps quickly. For example, in Figure 6, the isomorphism identification of 15-links cases in literature ³⁰ is analyzed as followed.

• Step 1: Retrieve and compare the structural parameters of these two KCs, they are the same [15,27,−12,13,6,0,0,6,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0].

• Step 2: Select the root node. Link 8 with 6-pairs is selected as the root node of KC5, while there have three matching possibilities in KC6, they are link 1, 2, and 3 with 6-pairs, here link 1 is selected and analyzed for example.

• Step 3: Obtain BM9 and BM10 corresponding to KC5 and KC6.

• Step 4: By retrieving and arranging the RM, it is easy to find that the RM9 of KC5 and RM10 of KC6 are different. So non-isomorphic result in this matching possibility can be drawn.

$$B{M}_9=\left(\begin{array}{cccc}8\hfill & 2\hfill & 1\hfill & B_2\hfill \\ \multicolumn{1}{c}{8}& 2\hfill & 3\hfill & B_2\hfill \\ \multicolumn{1}{c}{8}& 2\hfill & 3\hfill & B_4\hfill \\ \multicolumn{1}{c}{8}& 2\hfill & 13\hfill & 0\hfill \\ \multicolumn{1}{c}{8}& 5\hfill & 4\hfill & B_3\hfill \\ \multicolumn{1}{c}{8}& 5\hfill & 4\hfill & B_5\hfill \\ \multicolumn{1}{c}{8}& 5\hfill & 6\hfill & B_3\hfill \\ \multicolumn{1}{c}{8}& 5\hfill & 12\hfill & 0\hfill \\ \multicolumn{1}{c}{8}& 7\hfill & 1\hfill & B_2\hfill \\ \multicolumn{1}{c}{8}& 7\hfill & 6\hfill & B_3\hfill \\ \multicolumn{1}{c}{8}& 7\hfill & 10\hfill & B_4\hfill \\ \multicolumn{1}{c}{8}& 7\hfill & 11\hfill & B_5\hfill \\ \multicolumn{1}{c}{8}& 7\hfill & B_1\hfill & 0\hfill \\ \multicolumn{1}{c}{8}& 9\hfill & B_1\hfill & 0\hfill \\ \multicolumn{1}{c}{8}& 9\hfill & 3\hfill & B_2\hfill \\ \multicolumn{1}{c}{8}& 9\hfill & 3\hfill & B_4\hfill \\ \multicolumn{1}{c}{8}& 9\hfill & 13\hfill & 0\hfill \\ \multicolumn{1}{c}{8}& 9\hfill & 4\hfill & B_3\hfill \\ \multicolumn{1}{c}{8}& 9\hfill & 4\hfill & B_5\hfill \\ \multicolumn{1}{c}{8}& 9\hfill & 12\hfill & 0\hfill \\ \multicolumn{1}{c}{8}& 14\hfill & 1\hfill & B_2\hfill \\ \multicolumn{1}{c}{8}& 15\hfill & 6\hfill & B_3\hfill \end{array}\right)B{M}_{10}=\left(\begin{array}{cccc}1\hfill & 2\hfill & 5\hfill & B_2\hfill \\ \multicolumn{1}{c}{1}& 2\hfill & B_1\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& 2\hfill & 8\hfill & B_3\hfill \\ \multicolumn{1}{c}{1}& 2\hfill & 8\hfill & B_4\hfill \\ \multicolumn{1}{c}{1}& 2\hfill & 13\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& 2\hfill & 15\hfill & B_5\hfill \\ \multicolumn{1}{c}{1}& 3\hfill & B_1\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& 3\hfill & 14\hfill & B_4\hfill \\ \multicolumn{1}{c}{1}& 3\hfill & 4\hfill & B_2\hfill \\ \multicolumn{1}{c}{1}& 3\hfill & 4\hfill & B_5\hfill \\ \multicolumn{1}{c}{1}& 3\hfill & 9\hfill & B_3\hfill \\ \multicolumn{1}{c}{1}& 3\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& 6\hfill & 5\hfill & B_2\hfill \\ \multicolumn{1}{c}{1}& 6\hfill & 4\hfill & B_2\hfill \\ \multicolumn{1}{c}{1}& 6\hfill & 4\hfill & B_5\hfill \\ \multicolumn{1}{c}{1}& 6\hfill & 11\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& 7\hfill & 8\hfill & B_3\hfill \\ \multicolumn{1}{c}{1}& 7\hfill & 8\hfill & B_5\hfill \\ \multicolumn{1}{c}{1}& 7\hfill & 13\hfill & 0\hfill \\ \multicolumn{1}{c}{1}& 7\hfill & 9\hfill & B_3\hfill \\ \multicolumn{1}{c}{1}& 10\hfill & 9\hfill & B_3\hfill \\ \multicolumn{1}{c}{1}& 12\hfill & 5\hfill & B_2\hfill \end{array}\right)R{M}_9=\left(\begin{array}{cccc}22\hfill & 7\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 7\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 7\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 7\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 7\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 7\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 7\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 5\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 5\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 5\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 5\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 5\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 2\hfill & 2\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 2\hfill & 2\hfill \\ \multicolumn{1}{c}{22}& 1\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 1\hfill & 3\hfill & 5\hfill \end{array}\right)R{M}_{10}=\left(\begin{array}{cccc}22\hfill & 6\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 6\hfill & 1\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 4\hfill & 3\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 4\hfill & 2\hfill & 0\hfill \\ \multicolumn{1}{c}{22}& 1\hfill & 3\hfill & 5\hfill \\ \multicolumn{1}{c}{22}& 1\hfill & 3\hfill & 5\hfill \end{array}\right)$$

Figure 6.

Isomorphism identification of 15 links in literature ³² : (a) topology graph of KC5 and (b) topology graph of KC6.

Due to space limitations, the following analysis processes of other two matching possibilities (link 2 and link 3 in KC6) are not repeated, but non-isomorphic results can be obtained quickly.

Based on the above examples’ analysis, for highly symmetrical graphs or KCs, there would be several same repeatability in RM, which leads to several matching possibilities for selection of one row in BM. However, for common KCs or graphs, the unique row in BM can be quickly found by means of RM. Even if the same intimacy occurs in the subsequent rearrange of rows, their different repeatability corresponding to the same intimacy can be used to make selection. Therefore, the result of isomorphism identification can be obtained quickly.

The isomorphism identification method of KC or graph based on BM has the advantages such as scientific and easy to be understood, simple and efficient judgment process. Only the connection relationships between links of KC are needed, dendrogram graph with one root node is selected, then all branch-chains can be separated from it, each row in BM are rearranged according to the intimacy with the former, the corresponding BM can be compared accompanied by RM. There has no counting but only comparison in isomorphism identification by using this method, so its counting labor is very less.

In literature, ³³ Luo pointed out that the complexity of his method is $O\left(L{\mathrm{n}}^3\right),1<L<n$ . Zhang et al. proposed a new isomorphism identification method using branch code method in literature, ³⁴ for n-bar with F degree of freedom and high pair KC, the maximum number of branch codes is $2\times [(n-F+4)!]$ , and the complexity is in order $O(\mathrm{n}!)$ . The isomorphism identification method of KC or graph based on BM proposed in this paper is simple, and mainly based on matrix analysis and comparison. First compare the RM in the Step 4 to see whether they are the same, then rearrange the BM according to the intimacy between the remainder rows in BM, at last compare the BMs obtained by the two KCs respectively to determine whether they conform to the matching rules. Therefore, the maximum complexity is $O\left(2{\mathrm{n}}^2\right)$ .

Conclusion

1. Dendrogram representation for graph is introduced to express the structure information of KC, in which it contains the information such as multiple joints and connect relationships between nodes in the same or different layers. The unique KC structure information can be deduced by its dendrogram graph with no information missed.

2. Branch-chains Matrix (BM) of KC is separated from its dendrogram graph, the concept of Intimacy between rows in BM, Repeatability of each row, and Repeatability Matrix (RM) are proposed to rearrange the rows in BM, then one or several BMs can be obtained according to intimacy and repeatability of each row.

3. A new isomorphism identification method is put forward based on the analysis that one BM can uniquely determine the structure of one KC, only connection information between links is needed in this method, and then rearrange and compare the BMs according to intimacy and repeatability of each row. It has the advantages of simple rules, no calculation, and less analysis and comparison. It greatly simplifies the isomorphism identification process which occupies the main analysis and calculation in KC synthesis.