从有向图的关联矩阵寻找其全部有向回路的机辅算法

A CAD Algorithm for Finding all Directed Circuits of a Digraph from Its Incidence Matrix

本文研究了有向图的有向回路、单连支有向回路、多连支有向回路等与其关联矩阵的关系,所有单连支有向回路通过“并”运算不能生成任何一个有向回路的性质,以及单向割集不构成任阿有向回路的性质等。在这些理论研究的基础上,本文提出了通过有向图的关联矩阵寻找图的全部有向回路的机辅算法。

In this paper, some relationship between the directed circuits, single-link directed circuits, multi-link directed circuits and the incidence matrix; and the. property that any directed circuit can not be generated among all of the single-link directed circuits by means of the 'union'and the property that monodirectional cutset can not form any directed circuit etc. are deeply studied. On the basis of the discussions, a CAD algorithm for finding all directed circuits from incidence matrix of a digraph is presented.