有向基本割集矩阵的超图综合法

Hypergraph Synthesis Method for Directed Fundamental Cutset Matrices

本文应用超图理论提出了从有向基本割集矩阵Q_f的树路子阵Q_(fp)逐层判断其可实现性和综合出其对应有向图G的算法RFCMHGT。它的原理直观,计算复杂度为O(nl^2),μ和l为Q_(fp)的行和列数。例2表明:Tutte条件不是Q_f可实现的充分条件。

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.