Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by definin...Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.展开更多
基金Supported by the Natural Science Foundation of Hebei Province(61203142)
文摘Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.
基金partially supported by the Fundamental Research Funds for the Central Universities,Nankai Universitypartially supported by NSFC(Nos.12161141006,12111540249)+2 种基金the Natural Science Foundation of Tianjin(No.20JCJQJC00090)the Fundamental Research Funds for the Central Universities,Nankai Universitypartially supported by grant DFF-7014-00037B of Independent Research Fund Denmark。
