求简单有向图所有基本回路的强核图论算法
Strong Kernel Graphic Algorithm for Searching All Essential Circuits of Simple Directed Graph
-
摘要: 求系统动力学模型的所有反馈环等价于求对应的简单有向图的所有基本回路,其核心问题是算法的时 间复杂度.针对这一问题,提出强核的概念,基于强核概念设计了求简单有向图所有基本回路的算法,给出相应 算例,并分析了算法复杂性.在时间复杂度上,本算法优于基于核概念的有向图的行列式算法.Abstract: 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 keyof the problem is time complexity. A newconcept 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 algorithmwas 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.
-
Key words:
- system dynamics /
- graph theory /
- feedback loop /
- essential circuit
点击查看大图
计量
- 文章访问数: 1548
- HTML全文浏览量: 67
- PDF下载量: 149
- 被引次数: 0