D0I:10.13374/i.issn1001-053x.1992.02.011 第14卷第2期 北京科技大学学报 Vol.14 No.2 1992年3月 Journal of University of Science and Technology Beijing March 1992 有向基本割集矩阵的超图综合法 黄汝激· 摘要：本文应用超图理论提出了从有向基本割集矩阵Q1的树路子阵Q1,逐层判断其可实 现性和综合出其对应有向图G的算法RFCMHGT。它的原理直观，计算复杂度为O(nl2),“ 和'为Q1p的行和列数。例2表明：Tutte条件不是Q,可实现的充分条件。 关键词：网络拓朴综合，超图，有向图 Hypergraph Synthesis Method for Directed Fundamental Cutset Matrices Huang Ruji ABSTRACT:By applying hypergraph theory,Algorithm RFCMHGT is presented for determing the realizability of a given directed fundamental cutset matrix Q,and synthesizing its corresponding directed graph G layer by layer from its tree path submatrix Q.Its principle is intuitive,and its computational com- plexity is O(nl2),where n and are the numbers of rows and columns of Q.Example 2 shows that Tutte's condition is not the sufficient condition for Q,to be realizable。 KEY WORDS:network topological synthesis,hy pergraph,directed graph 如何从已知有向基本割集矩阵Q,综合出其对应有向图G是有向开关网络拓朴综合中的重 要问题。文献〔1)和〔2)分别应用拟阵和PQ图理论提出了实现无向Q,的两个算法。文献〔3) 和〔4)给出了从有向Q,求关联矩阵A的元素和其符号的算法，但很繁琐，且未解决分解时分 1991一11一25收稿 、·自动化系(Dept,of Automatic Control) 185第 卷 第 期 年 月 北 京 科 技 大 学 学 报 。 匀 有向基本割集矩阵的超 图综合法 黄 汝 激 ， 摘 要 本文应 用 超图理论提出 了从 有 向基本割集矩阵 。 了的 树路子 阵 。 了， 逐层判断 其可 实 现性和综合出 其对 应有 向图‘ 的算法 。 它 的原理 直观 ， 计算复杂 度为 川 ， ， 和 为 。 厅 的 行和 列数 。 例 表明 条件不 是 可实 现 的充 分条件 。 关健 词 网 络拓 朴综合 ， 超图 ， 有向图 五 ， ，， ， ， ，， ’ ， 。 。 。 。 。 ， ， 八 ， 。 如何从已知 有 向基本割集矩阵 了综合 出其对应有 向 图 是有 向开关 网络拓 朴综合 中的 重 要问题 。 文献〔 和〔幻分别应用拟 阵和尸 图理论提 出 了实现无向 了 的两个算法 。 文献〔 〕 和 〔 〕给 出了从有 向 ，求关联矩阵 的元素和其符号的算法 ， 但很繁琐 ， 且未解决分 解时分 一 一 收稿 · 自动化 系 ， 鑫 砚 尽 〕 落母吞 DOI ：10．13374／j ．issn1001－053x．1992．02．011