D0I:10.13374/j.issn1001-053x.1994.02.019 第16卷第2期 北京科技大学学报 Vol.16 No.2 1994年4月 Journal of University of Science and Technology Beijing Ap.1994 从基本割集矩阵综合有向图的分解法 黄汝激 北京科技大学自动化系，北京100083 摘要引人了有向基本割集矩阵2的二分解和分解树的概念，导出了Q可实现的充分必要条件 和所实现图G在有向二同构意义上的唯一性，应用超图理论解决了如何求2，的二分解问题，提 出了用分解法直接实现2的原理和算法，该原理可计算复杂度为0(P),)和1为2的树路子 阵2的行数和列数. 关键词网络综合，超图，有向图，Q矩阵 中图分类号0157.5 The Decomposition Method for Synthesizing Directed Graphs from Fundmental Cutset Matrices Huang Ruji Department of Automation,USTB,Beijing 100083,PRC ABSTRACT The concepts of the 2-decomposition and decomposition tree of a directed fundamental cutset matrix are introduced.The necessary and sufficient conditions for realizability of and the uniqueness of realized graph G in directed 2-isomorphic sense are deduced.The problem,how to find a 2-decomposition of C,is solved by hypergraph theory.The principle and algorithm for directly realzing 2,by decomposition method are pre- sented.The principle is intuitive.Its computational complexity is (P),where v and I are the numbers of rows and columns of the tree-path submatrix O of respectively. KEY WORDS network synthesis,hypergraph,directed graphy,2 matrix 从已知2，综合出其对应有向图G的问题是网络拓扑综合中的重要问题.文献[]提出了 有向单触点开关网络的拓扑综合方法，其中要求实现有向2，文献[2]给出了通过分解Q求 A矩阵的原理，但未解决两个关键问题：(1)当从Q移去一个基本割集后的分块数大于2 时，如何求？的二分解；(2)如何系统地确定A矩阵元素的正负号，本文目的是解决这些 问题， 1992-11-27收稿 第一作者男63岁数授第 61 卷 第 2期 1, 94 年 4 月 北 京 科 技 大 学 学 报 oJ ~ 1 o f U川 ve IS iyt o f S d en 优 a dn T eC h n o lo g y eB ij ign V o l . 16 N o . 2 A少 . 1 9 9 4 从基本割集矩 阵综合有 向图 的分解 法 黄 汝激 北 京科技 大学 自动化 系 , 北京 1X( 刃83 摘要 引入了 有向基本 割集矩阵 鸟 的二分解和分解树的概念 , 导出了 鸟可实现的充分必要条件 和所实现图 G 在有 向二 同构 意义 上的唯一性 · 应 用超 图理论解决 了如何 求 Q, 的二 分解 问题 , 提 出了用分解法直 接实现 鸟的原理 和算法 · 该原理可计算复 杂度 为 0 (护l , ) 、 。 和 l 为 鸟的树 路子 阵 乌 的 行数和列数 . 关键词 网 络综合 , 超 图 , 有向图 , Q 矩阵 中图 分类号 0 15 7 . 5 T h e L 犯co l n P 0 s it i o n M e t h o d of r S yn t hes i云gn D i r e ct de G r a P hS 斤o m F un d rne n at l C u ts e t M a tr i c e s 刀“ a gn Ruj i eD P斌~ t o f A u t o am t i o n , US T B , 欣石ign 10以粥3 , P R C A B S T R A C T hT e co n eC P ts o f ht e Z 一 d e e o m P o s it i o n a dn d e co m P o s it i o n t r e e o f a d im 沈刃 九n d a ~ atl tsCU et anT ixtr 鸟 a re In it D d u “ 过 . hT “ 一 ry an d s u if ` en t co dn it io ns of r are 腼b il it y o f 鸟 a n d t h e u n l q uenS o f “ l访月 g ar p h G in d ire tC de Z一is o om 印h i c s ens a re d de u “ 沮 . T卜e p or b】er .n h o w ot if n d a Z 一 d助卿 o s i iot n o f 鸟 , 15 so l v de b y h y p esr ar p h t h co w · 丁五e p inr ` p le a dn a glo ir t h m fo r d i田川y aer 恤9 fQ b y d助mP o s it i o n IT 犯 t h o d a er p er - 义泊让d . hT e p inr 以p le 15 i n t u lit ve . I st co mP u at iot n al co mP lex iyt 15 0 (护产) , w h e er U a n d 1 a er het m 】nI be IS o f or “ a dn co l nUIS 0 f het 膝 一 p a ht s u b aln ixtr Q 介 o f 乌 , esr p咖vel y · KE Y WO R DS n et wo kr s势l ht es is , h y p gfC ar p h , d i er Ct de g ar p h y , Q anr t ixr 从已 知 鸟综合出其对应有 向图 G 的 间题是 网络拓 扑综合 中 的重 要 问题 · 文 献 l[ ] 提 出 了 有 向单触 点开关 网络 的拓 扑综合 方法 , 其 中要 求 实现有 向 鸟 · 文 献 【2] 给出 了通 过 分解 鸟求 A 矩 阵的原理 , 但未解 决 两 个 关键 问题 : ( l) 当从 乌 移 去 一 个 基 本 割 集后 的 分 块 数大于 2 时 , 如何 求 Q f 的二分 解 ; (2 ) 如何 系 统地确 定 A 矩 阵元素 的正 负号 . 本文 目的是 解 决这 些 问题 . 1卯2 一 1 一 27 收稿 第一作者 男 63 岁 教授 DOI: 10. 13374 /j . issn1001 -053x. 1994. 02. 019