Matrix Algebraization Method And Application Of Graph Theory Problems

Connectivity problem,circle problem,matching problem and coloring problem in graph theory are widely used in engineering,technology and other fields.The existing algorithms are iterative algorithms.Algebraic formulaization of these problems is not only convenient for theoretical analysis,but also can be solved by equation form.In this paper,the cycles of simple connected graphs,the matching of simple connected graphs,the edge coloring scheme of hypergraphs and the algebraic formulaization of all adjacent edges in hypergraphs are studied by using the semi-tensor product of matrices.On this basis,the cycles of simple connected graphs are further applied to find cut edges and minimal spanning trees,the matching of simple connected graphs is applied to find perfect matches,the edge coloring scheme of hypergraphs is applied to cost list scheduling problem,and all adjacent edges of hypergraphs are applied to bus network transfer problem.The main research contents are as follows:(1)The characteristic logic vectors of cycles are defined.The necessary and sufficient conditions for the existence of cycles are obtained by using semi-tensor product of matrices.The cycles is further formulated.Based on the process of cycles algebra formulation,an algorithm for finding cut edges and minimum spanning trees is established.An example is given to illustrate the effectiveness of the algorithm.(2)Define matching feature logic vectors.Based on semi-tensor product of matrices,the necessary and sufficient conditions for the existence of matching are obtained.On this basis,the matching is formulated.Through the process of matching algebra formulation,all matching algorithms are established.Based on matching algorithm,the algorithm for finding perfect matching is established.An example is given to verify the effectiveness of the algorithm.(3)Define the 6)value characteristic logic vector of each edge of hypergraph.Through the method of Semi-tensor product of matrix,the necessary and sufficient conditions for the existence of hypergraph edge coloring schemes are obtained.Based on these conditions,the algebraic formulas of hypergraph edge coloring schemes are established.On this basis,an algorithm for finding hypergraph edge coloring schemes is established.The algorithm is applied to the cost list scheduling problem.(4)Define the characteristic logic vectors of adjacent edges of hypergraphs.By using the method of semi-tensor product of matrix,all adjacent edge in hypergraphs are formulated.The algebraic formulaization process is used to establish an algorithm for finding all adjacent edges in hypergraphs.Mapping the bus network to hypergraph.By using the algorithm of finding all adjacent edges in hypergraph and the correlation matrix of hypergraph,the algorithm of direct or multiple transfers between starting point and ending point is given.The effectiveness of the algorithm is verified by an example.