一种求网络所有回路的矩阵方法  

A Matrix Algorithm for Enumerating All Circuits of a Graph

作　　者：袁亚华[1] 李泳[1] 王自果[1] 

机构地区：[1]西北工业大学

出　　处：《西北工业大学学报》1992年第2期204-210,共7页Journal of Northwestern Polytechnical University

摘　　要：本文利用网络矩阵间的两种特殊运算,得到了一种求网络所有有向回路和所有无向回路的矩阵方法。由本方法所形成的计算机算法属多项式型算法,具有有效性,且对边数多、回路数多而节点相对少的网络更为适用。本文举例对方法进行了说明,并表明算法是收敛的。All circuits of a graph are widely used in the fields of Electrical Network, Signal-flow Graph and Computer Science [1-4]. Given an undirected graph, the problem of enumer- ating all its circuits has received much attention. The analogous problem for a digraph is to enumerate all its dicircuits. To solve the two problems, many algorithms have been pro- posed and every algorithm can be put into one of the following three main classes: circuits vector space algorithm, search algorithm, adjacency matrix algorithm[5-7]. In this paper, an algorithm that is faster under certain conditions than the above men- tioned algorithms is developed. It can successfully obtain all circuits of an undirected graph and all dicircuits of a digraph. Compared with the fastest Bachtrack algorithms [6-7] in the case of digraph, it is faster when the connectivity of the graph is complicated. It is proved that the developed algorithm has a polynomial upper bound on the time. Also, it can be easily implemented on computers. This algorithm uses a specially defined operation (?) between the known path matrix A_i [8] and known terminal matrix R, and then get the vector C_i: C_i=A_i (?) R (i=2, 3, …, n-1. n is the number of vertices of the graph). With C_2, C_3, …, C_(n-1) known, all circuits of an undirected graph and / or all dicircuits of a digraph can be found. The algorithm is illustrated by using an undirected graph example and a digraph ex- ample.

关 键 词：网络 有向回路 无向回路 算法 图论 

分 类 号：O157.5[理学—数学]