有向基本割集矩阵的超图综合法
Hypergraph Synthesis Method for Directed Fundamental Cutset Matrices
-
摘要: 本文应用超图理论提出了从有向基本割集矩阵Qf的树路子阵Qfp逐层判断其可实现性和综合出其对应有向图G的算法RFCMHGT。它的原理直观,计算复杂度为O(nl2),μ和l为Qfp的行和列数。例2表明:Tutte条件不是Qf可实现的充分条件。Abstract: By applying hypergraph theory, Algorithm RFCMHGT is presented for determing the realizability of a given directed fundamental cutset matrix Qf and synthesizing its corresponding directed graph G layer by layer from its tree path submatrix Qfp. Its principle is intuitive, and its computational complexity is O(nl2), where n and l are the numbers of rows and columns of Qfp. Example 2 shows that Tutte's condition is not the sufficient condition for Qf to he realizable.