从基本割集矩阵综合有向图的分解法

The Decomposition Method for Synthesizing Directed Graphs from Fundmental Cutset Matrices

  • 摘要: 引入了有向基本割集矩阵Qf的二分解和分解树的概念,导出了Qf可实现的充分必要条件和所实现图G在有向二同构意义上的唯一性,应用超图理论解决了如何求Qf的二分解问题,提出了用分解法直接实现Qf的原理和算法.该原理可计算复杂度为O(v2l2)、vlQf的树路子阵Qfp的行数和列数.

     

    Abstract: The concepts of the 2-decomposition and decomposition tree of a directed fundamental cutset matrix Qf are introduced. The necessary and sufficient conditions for realizibility of Qf and the uniqueness of realized graph G in directed 2-isomorphic sense are deduced.The problem, how to find a 2-decomposition of Qf, is solved by hypergraph theory. The principle and algorithm for directly realzing Qf by decomposition method are presented. The principle is intuitive. Its computational complexity is O(v2l2), where v and l are the numbers of rows and columns of the tree-path submatrix Qfp of Qf, respectively.

     

/

返回文章
返回