求简单有向图所有基本回路的强核图论算法

Strong Kernel Graphic Algorithm for Searching All Essential Circuits of Simple Directed Graph

求系统动力学模型的所有反馈环等价于求对应的简单有向图的所有基本回路,其核心问题是算法的时间复杂度.针对这一问题,提出强核的概念,基于强核概念设计了求简单有向图所有基本回路的算法,给出相应算例,并分析了算法复杂性.在时间复杂度上,本算法优于基于核概念的有向图的行列式算法.

The problem of searching all feedback loops of a system dynamics model is equal to calculating all essential circuits of a corresponding simple directed graph. The key of the problem is time complexity. A new concept named strong kernel was defined, and the algorithm based on strong kernel for searching all essential circuits of a simple directed graph was proposed. An illustrative example was presented and the complexity of the algorithm was analyzed. In terms of time complexity, the proposed algorithm is superior to that of the determinant algorithm based on the concept of kernel of directed graphs.