arXiv:math.GM/0205220 v1 21 May 2002Heuristic algorithm for solving the graph isomorphism problemR.T. Faizullin, A.V. ProlubnikovIn the paper we consider heuristic algorithm for solving graph isomorphismproblem. The algorithm based on a successive splitting of the eigenvalues ofthe matrices which are modifications (to positive defined) of graphs’ adjacencymatrices. Modification of the algorithm allows to find a solution for Frobeniusproblem. Formulation of the Frobenius problem is following one. Given a pairof two matrices with the same number of rows and columns. We must find outwhether one of the matrix can be acquired from another by permutation ofit’s rows and strings or not. For example, solution of Frobenius problem cangive to us efficient way for decrypting of double permutation cyphers problemfor high dimension matrices.The graph isomorphism problemGraph isomorphism problem is one of the problems for which we can’t say def-initely whether this problem is polynomial or not [1]. But it’s known that thisproblem is polynomial for some classes of graphs such as plane graphs, regulargraphs and some others [2], [3], [4]. Our algorithm is heuristic algorithm for solvingof the problem.We consider heuristic algorithm for solving the graph isomorphism problem.The algorithm based on successive splitting of eigenvalues of the matrices thatare modifications (to positive defined) of graphs’ adjacency matrices. During thework of the algorithm we solving the linear equations that defines inverse matricesof these matrices. Solutions of these systems gives to us a permutation which issought bijection.There are two nonoriented graphs in the graph isomorphism problem: graphGA= hVA, EAi and graph GB= hVB, EBi. VA, VBare sets of graphs’ vertices.EA, EBare sets of it’s edges. They are supposed to be the sets of the samepower: |VA| = |VB|, |EA| = |EB|. Graph isomorphism problem formulation isfollowing one: whether exists such bijection ϕ : VA→ VBthat if (i, j) ∈ EAthen(ϕ(i), ϕ(j)) ∈ EBor not?Algorithm works with modifications of adjacency matrices. Let A0be an adja-cency matrix of GA, that is to say that A0= (a0ij) anda0ij=(1, if (i, j) ∈ EA,0, else.Let B0be an adjacency matrix of graph GB.Construct matrix DA0according to A0:d10 . . . 00 d2. . . 0............0 0 . . . dn12DA0is a scalar matrix with following elements:di=nXj=1a0ij+ 1.Construct matrix DB0similarly according to B0. LetA = A0+ DA0, B = B0+ DB0. (1)Matrices A and B are further considerated matrices. They are matrices whichalgorithm works with. They are symmetric and positive defined.If graps GA= hVA, EAi and GB= hVB, EBi are isomorphic then we can acquirematrix A from matrix B by successive permutations of it’s rows with simultane-ous permutations of it’s columns with same numbers. So we can formulate thegraph isomorphism problem as a particular case of the Frobenius problem whichformulation is following one. Can we acquire matrix B from matrix A by successivepermutations of it’s rows and columns?Permutation of rows numbers i and number j for arbitrary matrix is equal toright multiplying matrix by permutation matrix Pij. Permutation of columns isequal to left multiplying matrix by the same permutation matrix. Permutationof vector’s components with numbers i and j take place for both left and rightmultiplying vector by permutation matrix Pij.Let us consider the following systems of linear equations:Ax = ej, By = ek. (2)The vectors ei= (0, . . . , 0, 1, 0, . . . , 0) are basis vectors in the space Rn, matricesA and B such as described above. Both systems are solvable and each solution isunique solution because of A and B are matrices with diagonal predominance andtheir determinants aren’t equal to zero. Let xjbe a solution of the system Ax = ejand ykbe a solution of the system By = ek.Note that solution of the systems of linear equations (1) gives to us inversematrices of matrix A and matrix B. So for i-th component of vector xjthe followingis true: xji= (−1)i+jAij/ det(A), where Aijare algebraic adjuncts for element aijof the matrix A. That is to say xj, j = 1, . . . , n are columns of inverse matrix forA.If B = PjkAPjkthen the following is true for solutions of the systems of linearequations (2):xi= yi, i 6= j, i 6= k;xj= yk, xk= yj.Indeed: (Ax = ej) ∼ (PjkAx = Pjkej) ∼ (PjkAxPjk= PjkejPjk) ∼ (PjkAPjkx =ej) ∼ (PjkAPjkxPjk= ejPjk) ∼ (BxPjk= ek). That is to say xPjk= y.If matrix B can be acquired from matrix A by successive permutations of it’srows with simultaneous permutations of it’s columns with same numbers then:B = Pjlkl. . . Pj1k1APj1k1. . .Pjlkl,and consequently xPj1k1. . .Pjlkl= y.So if we’ll change vector ekin the system of linear equations (2) with fixed jby changing index k from 1 to n then vectors xjand yk, which are correspondingsolutions of the systems (2), will be the same vectors correct to permutation oftheir components only if row with number j of matrix A corresponds to row with3number k of matrix B. That is to say elements of row number k of matrix B arepermutated elements of row number i of matrix A. The same is true for columnsof the matrices.We’ll accomplish the successive perturbations of its diagonal elements for findingunique row and unique column of the matrix B that is corresponds to row and col-umn with number i of the matrix A. The algorithm works with symmetric matriceswhich can be transformed into scalar matrices by orthogonal transformations. SoeA = UAAUTA,eB = UBBUTA,whereeA,eB are scalar matrices with eigenvalues on their diagonals and UA, UBare matrices of the orthogonal transformations. Diagonal elements ofeA andeB areeigenvalues of the matrices A and B.The spectrums of the isomorphic graphs’ adjacency matrices are the same [5].The same true for the matrices which algorithm works with because of describedabove procedure of changing of the diagonal elements of adjacency matrices leadsonly to shifting spectrums of the matrices. So if the matrices are corresponds to theisomorphic graphs then spectrums of the matrices will be congruent after shifting.It’s obvious that if the spectrums of the both matrices is simple or multiplicityof eigenvalues is not big then the problem of graph isomorphism can be solved bya comparison of rows of the matrices UA, UB,eA andeB [7].The main difficulties arise with consideration of graphs which spectrums containsmultiple eigenvalues. Perturbation of the matrices will allow us to