The Decomposition Method for Synthesizing Directed Graphs from Fundmental Cutset Matrices

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