从基本割集矩阵综合有向图的分解法

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

·186 北京科技大学学报 第16卷 1从有向2综合有向图的分解法原理 已知一元素为0、1、-1的o×e阶矩阵g=[U2pl,U为单位阵，2p为树路子阵.2n 的每列对应于树中一条通路，行（树支）号集t={1,,以，列（连支）号集下={和+1，e以 要求综合出一有向图G,并以2为其基本割集矩阵.设Q只含一块Q.令：Q(i:k)一Q的 i行k列元素；F-基本割集行号集；一关联集行号集；H=Q(L,F)一从Q取出行集I和F 组成的矩阵.注意：关联集行Q(-i;)=-;). 定义1矩阵H,x∈F,是指从H中移去行x并移去x中非零元素所在列得的矩 阵。 一般H,可按行划分成互不关联（即没有公共连支）的c个子阵（分块）.若c=2,称该 划分为Hx的二划分，记作H-x→[H,H].若c=1,则令H=Hx,H=Φ（空矩阵）.若 c≥3，可应用从超图理论导出的算法SHTMJE)(稍加修改)求得H和H.若H可实现成 图G,则H.对应于图G。即从G中移去割集x的所有边，得到两个分离的连通子图， G2 G Q 0=x G 0=-y =k d. P a.F G GR Ga P ● y G d G 0 6 Gu (a)G (b)G,G2 (c)G (d)Gu,Giu 图1对应于矩阵H之分解的图G的分解 Fig.1 Decomposition of graph G corresponding to decomposition of matrix H 定义2矩阵H缩减H,记作H,=H⊙H,是指从H中移去H,所在行（对应于在G 中缩减G)成一点B,称为缩点)，并把H所关联的基本割集行号x换成关联集行号a,=Sx, 若树支x射出点P,则s=1,否则s=一1.对应于H的图记作G=GOG,如图1b)所示. 定义3矩阵H按行x的二分解，记作H→(H,H2),是指从H按定义2产生一对子 阵H,=HΘH和H,=HOH,各含关联集行a和一a,(对应于图G分解成一对子图 G,=GoG和G,=G©G,如图1b)所示).H称为H,和H2的父阵. 开始分解H时由于树支x的方向未定，可任选s=1(对应于在G,中选x射出B)或s=1 (对应于在G,中选x射入P),两种情况下综合出的图G的边方向恰好相反， 子阵H,和H2可以分别进一步分解.例如，若在H,中找到与行a,共有连支k的另一基 本割集行y,则H,可按行y进一步分解成一对子阵H,和H2,行y变成一对关联集行a,和 一口，这时a,=sy的符号受到公共连支k的约束，不能任选.因为k与其两个端点P,和P

18 6 北 京 科 技 大 学 学 报 第 16 卷 1 从有 向 Qf 综合 有 向 图的分解法原 理 已 知一元 素 为 o 、 l 、 一 1 的 。 x 。 阶矩 阵 马二 【U Q别 , U 为单位 阵 , Q,P 为 树 路 子 阵 · 么 的每 列 对 应 于 树 中一条 通 路 , 行 (树 支 ) 号集 t = { 1 , … , v} , 列 (连 支 ) 号 集 厂二 { 。 十 l , … .e} 要 求综合出 一 有向图 G , 并 以 乌为其 基 本 割 集 矩 阵 · 设 乌只含 一块 .Q 令 : Q i( ’, k) 一 Q 的 i 行 k 列 元 素 ; 尹一基 本割集 行号 集 ; I一 关联集 行号集 ; H ! Q (I , r) 一从 Q 取 出行 集 I 和 F 组成 的矩 阵 . 注 意 : 关联集行 Q (一 ;i ) = 一 Q ;i( ) . 定 义 1 矩 阵 H _ 二 , x 任 F , 是 指 从 H 中移 去 行 x 并 移 去 x 中非 零 元 素 所 在 列 得 的 矩 阵 . 一般 H _ 二 可 按 行划 分成 互不 关联 (即没有公 共 连支 ) 的 c 个子 阵 (分块 ) . 若 。 = 2 , 称 该 划分为 H 一 二 的 二划 分 , 记作 H 一 、 一 【州 , 凡 ] . 若 。 = 1 , 则 令 拭 ` = H 一 二 , 城 = 。 ( 空矩 阵 ) . 若 。 ) 3 , 可应 用从超 图理论 导出的算法 s ll T M EJ ` ” ( 稍加 修改 ) 求得 斌 和 斌 . 若 H 可 实 现成 图 G , 则 H _ 、 对 应于 图 G _ 、 , 即从 G 中移去 割集 x 的所 有边 , 得 到两个分 离 的连通 子 图 . q 气二 k 民;6 O O G ,玉 心 6 口 `G , ; G二 O O ( e ) q ( d ) G : : , C , 2 一 ; 矛,凡环卜、T一I 一忆刀..IGU G 门lJG 工才军f口-伙,工司日卜Xl G Z, Q O - . · · · ~ · 1 ! - … { . 6 _ , 6 0 - ( a ) G 图 1 对应 于矩阵 H 之分解 的图 G 的分解 瑰 . I D墩” m 卯刻加 of 脚户 G co m 润 , o dn 吨 ot d助m p o 菌向 n of m a州 x H 定 义 2 矩 阵 H 缩 减 斌 , 记 作 H , = H O H ; , 是 指 从 H 中移 去 H ; 所 在 行 (对应于 在 G 中缩减 味成 一点 xP , 称 为缩点 ) , 并把 斌 所 关 联 的 基 本 割集行 号 x 换 成 关 联 集行 号 a 二 = 、 x, 若树 支 x 射 出点 xP 则 、 二 1 , 否则 、 = 一 1 . 对应于 H , 的 图记作 G一 6 O G毖如 图 l 山) 所示 . 定 义 3 矩 阵 H 按 行 x 的 二分解 , 记 作 H ~ (拭 , H Z ) , 是 指 从 H 按 定 义 2 产 生 一 对子 阵 H l = 月 O 斌 和 从 = H O H I , , 各 含 关 联 集 行 “ 二 和 一 a 二 ( 对 应 于 图 G 分 解 成 一 对 子 图 G l = G O G; 和 q ! 田G l ’ , 如 图 1伪) 所 示 ) . H 称为 H , 和 从 的 父阵 . 开始分解 H 时 由于 树支 x 的 方 向未定 , 可 任选 、 = l( 对应 于在 G , 中选 x 射 出 xP ) 或 、 = 1 ( 对应 于在 G , 中选 x 射 人 xP ) , 两种情 况 下综 合出的 图 G 的边方 向恰 好相反 . 子 阵 H , 和 H : 可 以分别进 一步 分解 . 例如 , 若在 H , 中找到 与行 a : 共 有 连 支 k 的另 一 基 本 割集行 y , 则 H , 可按 行 y 进一 步分 解成 一 对子 阵 H l . 和 城 2 , 行 y 变成 一 对 关联 集 行 a , 和 一 马 . 这 时 马二 sy 的符号 受到 公共 连 支 k 的 约束 , 不 能 任 选 . 因为 k 与 其两个端 点 xP 和 几

第2期 黄汝激等：从基木割集矩阵综合有向图的分解法 -187. 的关联关系是相反的，即Q(a;k)=-Q(a;k),若2(a;k)=土Q(y;k)则s=干1.H,可 实现的充要条件是对于割集x与y的所有公共连支k,乘积Q(x,k)Q(y,k)都相等，并且 它的子阵H,和H2都可实现.这是因为若Q(x,k)Q(y,)对于和x和y的所有公共连支k 都相等，则可唯一确定s和a,若H,可实现成G,(图1(c),则H,分解成H,和H2将对应 于G分解成G,和G2(图1(@)，它们分别是H,和H2的实现.反之，若H,和H2可实现 成G,和G,则从图1@)中消去两个缩点P,可以返原到图1(c)中的G,它就是H,的实 现.推广到一般情况，可得下面引理. 引理1若已知矩阵H=Q(I,F)a.∈I,y∈F,a.与y有公共连支k,H,有一个二划 分：H,→[H,H],H=0(I,F),H,=0,F),a.∈I,IUI2=1,FiUF=F-y 乘积(x,k)2少，k)对于割集x与y的所有公共连支k都相等，则(1)H有一个二分解： H(H),H=(I,F),H2=2(,F2),=Ia,F=F,=I2(-a F2=F2, a,=sy,若Q(ax;k)=土Q(y,k)则s=干1；(2)H可实现成含关联集族1的有向图G的充分 必要条件是存在H的一个二分解H→(H,H),使得H,和H2分别可实现成含关联集族I, 的有向图G,和含关联集族的有向图G2, 定义4基本割集矩阵Q的分解树DT是指根据定义3和引理1把H=Q(I,F)从I=Φ， F={1,…,}开始逐步分解直到所有行y∈F都变成关联集行a,为止所得表示该分解过程的 一个二元树.树根H=Q,它的一对子点H和H2表示Q的一对子阵，余类推.若Q有v 行，则DT有U+1个叶点.叶点表示全由关联集行组成的矩阵，称为叶阵.分解树DT称为 可行的，若所有叶阵都是关联矩阵，即每列至多含一个“1”和一个“一1”元素。 定理1基本割集矩阵Q可实现的充分必要条件是它有一个可行分解树DT.若Q可实 现，则它的所有叶阵的参考行（每个叶阵的所有行之代数和反号后得到的行）组成的矩阵就 是实现Q的一个有向图G的关联矩阵A. 证设Q的所有叶阵都是关联阵，则每个叶阵可实现一个图，称为叶图，从v+1个叶 图沿分解树DT回溯上去，逐步消去所有缩点，可得一图G,它就是Q的一个实现.反之， 设Q可实现，实现的一个图为G,则Q的逐步分解到叶阵对应于G的逐步分解到叶图，每 个叶阵是其对应叶图的关联阵.所以？可实现的充要条件是它有一可行分解树DT,因叶阵 中每个关联集仅含一条树支，叶图中的树必为星树，叶阵的参考行就是星树中心（图G的 一个顶点)的关联集行，所以从+1个叶阵产生的v+1个参考行组成了图G的关联矩阵A. 定义5两个有向图G和G'称为有向二同构的，如果它们的边一一对应，回路也一一 对应，而且对应边与对应回路的关联关系（包括方向关系）相同· 定义5是文献[4]中定义4-1-2关于无向图的二同构定义的推广.显然文献[4]中关 于无向图的定理4一1-2也可以推广到有向图，即有下面的定理· 定理2两个有向图G和G'为有向二同构图的充分必要条件是它们有相同的基本割集 矩阵。 推论若Q可实现，则Q的不同分解过程（不同分解树）所实现的不同有向图都是有 向二同构的，即在有向二同构的意义上Q的实现是唯一的.反之，若根据定理1实现了？ 的一个有向图G,则G的所有有向二同构图也都是Q的实现

第 2期 黄汝激等 : 从 基木 割 集矩 阵综合有 向 图 的分解法 的关联 关 系是 相反 的 , 即 Q ( a , ; k ) = 一 Q ( a 、 ; k ) , 若 Q (久 ; k ) = 士 Q 。 ; k ) 则 s = 干 1 . H . 可 实现 的充要 条件是 对于 割集 x 与 夕的所 有 公 共 连 支 k , 乘 积 Q (x , k) Q 。 , k) 都相 等 , 并 且 它 的子 阵 鱿 . 和 私 : 都 可 实现 . 这是 因 为若 Q ( x , k) Q ( y , k) 对于 和 x 和 y 的所有 公共 连 支 k 都相 等 , 则可 唯一 确定 、 和 凡 , 若 H , 可 实 现成 q ( 图 1 c() ) , 则 H , 分 解 成 鱿 , 和 鱿 2 将 对应 于 G l 分解 成 G I , 和 G 12 ( 图 1 d( ) ) , 它们 分别 是 拭 1 和 拭 : 的实 现 . 反 之 , 若 私 ; 和 私 : 可 实 现 成 .G , 和 G IZ , 则从 图 1 d( ) 中消去 两 个 缩 点 马 , 可 以 返 原到 图 l c() 中 的 q , 它就 是 H , 的 实 现 . 推广到 一般情况 , 可得 下 面引理 . 引理 1 若已知 矩 阵 H = Q (I , F 天 久 呀I , y 呀F , a 二 与 y 有 公 共 连 支 k , H 一 , 有 一 个二 划 分 H 一 , 一 [H ; , 斌 ] , H ; 一 Q ( I ; , 石) , 斌 一 Q (1 i , 几) , a 二 份 I ; , I ` , 日I ; 一 I , F ; U F ; 一 F 一 {y } , 乘积 Q (x , k) Q 伽 , k) 对于 割集 x 与 y 的所 有公 共 连 支 k 都相 等 , 则 ( l) H 有 一 个 二 分解 : H ~ ( H l , 从 ) , H l = Q (人 , 只) , 凡一 Q (几 , 凡) , I , 一 ’lI U { a , } , 名一 州 , 几一 I ; 日{ 一 a , }, 凡一 几 , 马二 sy , 若 Q a( 、 ; k) 二 士 Q (y , k) 则 、 二 刊 ; ( 2) H 可 实现 成 含 关 联 集 族 I 的有 向 图 G 的 充分 必 要条件是存在 H 的一个 二分解 H 一 (拭 , 从 ) , 使得 H , 和 从 分别 可 实 现成 含 关联 集 族 几 的有 向图 G , 和含 关联集族 几的有 向 图 G : . 定义 4 基 本割集矩 阵 Q 的分解树 D T 是 指根 据 定 义 3 和 引 理 1把 H = Q (I , )F 从 I = 电 F 二 { 1 , … , ” } 开始逐 步分 解直到 所有 行 y 任F 都 变成 关联集 行 。 , 为 止所得 表示 该分解 过程 的 一个 二 元 树 . 树根 H 二 Q , 它 的一 对子 点 H l 和 从 表 示 Q 的一 对子 阵 , 余类 推 . 若 Q 有 ” 行 , 则 D T 有 。 十 1 个叶点 . 叶 点表示 全 由关联集 行组成 的矩 阵 , 称 为叶阵 . 分解树 D T 称 为 可 行的 , 若所有 叶阵都 是关 联矩 阵 , 即每列 至多含 一个 “ 1 ” 和一 个 “ 一 1 ” 元素 . 定理 1 基 本割集矩 阵 Q 可实现 的充分必要 条件 是它有 一个 可行 分解 树 D T 若 Q 可 实 现 , 则它 的所 有 叶阵 的参考行 (每个 叶阵的所 有行 之代 数和反 号后 得到 的行 ) 组成 的矩 阵就 是实 现 Q 的一个有 向图 G 的关 联矩 阵 A . 证 设 Q 的所有 叶 阵都是 关联 阵 , 则每 个叶 阵可 实现一个 图 , 称 为叶 图 , 从 v + 1 个叶 图沿分 解树 D T 回 溯上 去 , 逐步 消去 所有 缩点 , 可得 一 图 G , 它 就 是 Q 的 一个 实现 . 反 之 , 设 Q 可实 现 , 实现 的一 个 图为 G , 则 Q 的逐 步分 解到 叶 阵 对 应 于 G 的逐 步 分解 到 叶 图 , 每 个 叶 阵是 其对应 叶 图的关联 阵 . 所 以 Q 可 实现 的充要 条件是它 有一 可行 分解 树 D T . 因 叶 阵 中每个 关联集 仅含一条 树 支 , 叶 图中的 树必 为星 树 , 叶 阵 的 参 考 行 就 是 星 树 中心 ( 图 G 的 一个顶 点 ) 的关联 集行 , 所 以从 。 十 1 个 叶阵产生 的 。 + 1 个参考行 组成 了图 G 的关 联矩 阵 .A 定义 5 两 个有 向图 G 和 ’G 称 为有 向二同构 的 , 如果 它们 的边 一 一 对应 , 回 路 也 一 一 对应 , 而且 对应 边 与对应 回 路 的关联 关 系 ( 包括方 向关系 ) 相 同 . 定义 5 是 文献 【41 中定 义 4 一 1 一 2 关 于 无 向 图的 二 同构 定 义 的 推 广 . 显然 文 献 【4] 中 关 于 无 向图的定理 4 一 1 一 2 也可 以 推广 到有 向图 , 即有下 面 的定理 . 定理 2 两个有 向 图 G 和 G ’ 为有 向二 同构 图的充 分必 要条 件是 它 们有 相 同 的 基 本 割 集 矩 阵 . 推论 若 Q 可 实现 , 则 Q 的 不 同分 解过 程 ( 不 同分 解 树 ) 所 实 现 的不 同 有 向 图都 是 有 向二 同构 的 , 即在有 向二 同构的意 义上 Q 的 实现 是 唯 一 的 . 反 之 , 若根 据 定 理 1 实 现 了 Q 的一 个有 向图 G , 则 G 的所有有 向二 同构 图也 都是 Q 的 实现

.188 北京科技大学学报 第16卷 2从有向2，综合有向图的分解算法 定义6从矩阵Q构造二维数组L和一维数组D[(L,D)称为Q的邻接表如下： L①，DD,L(i)s。←{k|k>",2(i;k)≠0}， L(k;)k。←{i≤v,Q(;k)≠0；D)←|L(;)l,i=1,…,e. 算法RFCMDM(用分解法实现有向基本割集矩阵2) (1)输入2及其行列数D和e. (2)按定义6建立2的邻接表(L,D),调DFS求出2的分块子阵Q,及其行列数t, 和e,r=1,…,d. (3)对于r=1,…,d进行： a)初始化：Q+,v←D,v+D,e÷e,A,+D,按定义6建立的邻接表(L, D),I←Φ，F←={l,…,v},a←Φ，y←1，a,←1，t-0,q0,u←-0S④，H←QI,凡 b)建立H-,的访问数组：VSy)←1，k∈Ly;),VSk)1. c)调DFS求出H,的分块数c和各块的行（树支）号集，=(，F),i=1,,c,a∈I八. 求H,→[HH]的行号集：若c=1则I←I八，F←F,I2←Φ，F←重；若c=2则 ←I,F←F,I←I户，F←F2;若c≥3则调算法SHTMJE,LT←LT-LT(I),RT ←RT-RT(I),LI-UI'(iELD,LF-UF(i∈LT),RI←U(i∈RT),RF←UF6∈ RT).若a∈Ll或a,=0则L←Ll,FLF,I·RI,FRF,否则I,RL,Fi←RF, I2*Ll,F←LF. d求H→(H,H,)的行号集：4U{a,}FFi,h←1U{-a,EF2 e)I+I F+-Fi t+-t+1,SI(t)1,SF(t)+-F2. f)若F≠0，转g);否则若H的每列至多含一个1和一个-1，则“←u+1,A(u;)← -Σ2；)i∈1，转i),否则转(4). g)I。←i川i∈，S←Φ，4j长v-1。-F,S0)←1. h)从(L,D)和VS搜索I和F中有某公共连支k的关联集a,和基本割集y.若Q(a;k) =2y;k),则s-1,否则s1.a,+y,转b), i)若t=0转(5)否则I←SI(),F+SF(t),t←t-1,转f). (4)停止，显示“Q不能实现”. (5)显示A,,A,结束RFCMDM. 3应用举例 例，已知Q=[U2,】,Q,如(1)式，求其对应有向图G

1 8只 北 京 科 技 大 学 学 报 第 1 6 卷 2 从有向 Qf 综合有向 图的分解算法 定义 6 从矩 阵 Q 构 造二 维数 组 L 和一 维数组 D 【(L , 功 称 为 Q 的邻接表如 下 : L ~ 。 , D ~ 。 , L ( i ; ) `、 。 ~ { k Ik > v , Q ( i ; k ) 笋 o } , L ( k : ) * > 。 ~ { i { i簇 v , Q ( i : k ) 并0 ; D ( i ) ~ IL i( : ) l , i = l , … , e . 算法 R CF M D M ( 用分 解法 实现 有 向基本 割集矩 阵 乌) ( 1) 输 人 Q, 及 其行 列数 。 和 。 . (2 ) 按 定义 6建立 乌的邻接 表 (L , D ) , 调 D Fs 求 出 q 的分块 子 阵 Q , 及 其行 列 数 v, 和 e , , r = 1 , … , d . ( 3) 对于 ; = 1 , … , d 进 行 : a) 初 始 化 : Q ~ Q fr , 。 ~ vr , 。 ~ v r , 。 ~ er , 次 ~ 必 , 按 定 义 6 建 立 Q 的邻 接 表 (L , )D , I ~ 中 , F ~ 。 = { 1 , … , ” } , 久 ~ 中 , y ~ 1 , 马~ 1 , t ~ o , q ~ o , 。 ~ 0月 尹等~ 中 , 月~ Q (I, 凡 b) 建立 H 一 , 的访问数 组 : VS 伽) ~ 1 , v k 〔 L 伽; ) , U又人) ~ L c) 调 D SF 求 出 H 一 , 的分块 数 。 和各 块 的行 (树支 ) 号集 it = (lI , 尸 ) , =1 1 , … , c , 久 呀.lI 求 H 一 y一 【拭 一 , H i ] 的 行 号 集: 若 。 = 1 则 石~ 1 , 石 ~ lF , 几~ 中 , rz’ ~ 中 ; 若 “ = 2 则 ’lI ~ I ’ , ’r, ~ lF , 人~ 1 2 , 几~ F ’ ; 若 。 ) 3 则 调 算 法 S H下M EJ ` 7 ] , L T ~ L T 一 L T ( l) , R T ~ R T 一 R T ( l ) , LI ~ U l ` ( i ` L 7) , LF ~ U F ` ( i ` L T ) , IR ~ U l ` ( i ` R T ) , RF ~ U F ` i( 〔 R T ) . 若 a 二 任IL 或 a 二 = 。 则 石~ IL , 石~ 五只 人~ RI , 兀~ RF , 否则 石~ IR, 斌 ~ 双 f , 人~ IL , 燕~ LF . d ) 求 H 一 ( H 卜 从 ) 的行 号集 : I , ~ I ;U { a , } , 兀 ~ F ; , 几~ I ; U { 一 马 } , 凡 ~ F ; · e) I ~ 人 , F ~ 只; t ~ t + 1 , SI ( )t ~ 几 , SF (t ) ~ 凡 . f) 若 }lF 笋 O , 转 g ) ; 否 则 若 H 的 每 列 至多 含 一 个 1和 一 个 一 1 , 则 u ~ u 十 1 , A, (u ; )~ 一 E Q ( i: ) } i 任 I , 转 i ) , 否则 转 ( 4 ) . 9) 1 。 ~ { 1 1 任对 , VS ~ 中 , v j 任 。 一 I 。 一 F , VS 仍 ~ 1 . h) 从 ( L , D ) 和 vs 搜 索 I 和 F 中有某公 共 连支 k 的关联集 a 二 和 基 本 割 集 y . 若 Q a( 二 ; k) 二 Q伽; k) , 则 、 ~ 一 l , 否 则 、 ~ 1 . a , ~ sy , 转 b) . i ) 若 t = O 转 ( 5 ) 否 则 I ~ SI ( t ) , F ~ SF ( r ) , t ~ r 一 l , 转 f ) . (4 ) 停止 , 显示 “ 乌不 能实 现气 ( 5) 显示 式 , … , 儿 , 结 束 R F C M D M . 3 应 用举例 例 , 已 知 Q = [ U 么〕 , 么如 ( l) 式 , 求其对应 有 向图 G

第2期 黄汝激等：从基本割集矩阵综合有向图的分解法 189· 15 16 171819 20 21 22 23 24 25 26 27 1 -1 -1 1 0 0 0 0 0 0 0 -11 1 -1 -1 11 0 0 0 0 0 0 -1 23456 1 -1 -1111 100 0 0 0 -1 0 10 1 0 -1 0 0 0 0 -1 〉 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 -1 1 1 00 0 0 0 0 0 0 0 2。= 78910 1 0 0 0 -1 1 0 1 1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 t 00 0000 0 1 00 000 000 000 00 000 0 0 010 0 001 1 0 0 1000 0 0 0 0 0 5 5 E -17 (b)HG 15- (c)G. 图2有向图G及其关于割集1的超图HG和等效图G, Fig.2 Directed graph G and its hypergraph HG and equivalent graph G.with respect to cutset 1

第 2期 黄汝激等 : 从 基本 割集矩 阵综合有 向 图 的分解法 198 l 6 矛骊ō 叭广 t4 么 吞枯乌 l 7 一 1 一 1 一 1 0 一 1 0 l 0 0 0 l 0 O 一 1 2 23 24 52 0 0 0 0 0 0 0 0 0 0 0 0 一 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 一 l 一 1 1 0 一 1 0 0 0 一 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 01260 -l 1且. , ù ù“ 2 01 () 1901 01 OQ 勺.1且 ù一二. 0 二, ǎ“ ǎ” ù 0 n ànU 一 l .1 .1 几 0 ù “n à n 0 nU 0 曰.1 0 0 0 ǔ UO 巧01 -l-l1 0-l l 1012134245679813 b 叽 洲 悠 巧 即’I 可 E Z 巨 习 乓 E 式汽 . 一 一 一 声 图 F 电 有向图 G 及其关于割集 1 的超图 H G 和等效 图 q 众 r 。比de 脚户 G a川 治 鲡哟尹户 H G a l目 呷咖犯吐 脚户 G 。 俪山 戏月拍 d ot 口胜祀 t l .22

·190 北京科技大学学报 第16卷 解应用RFCMDM于Q可得结果：d=1;第一次分解时y=1,综合出的T和t.如图2b) 和(c);通过v次分解求得2的一个可行分解树如图3，其中H=2(,114)有28个子阵， H1=Q(1,2614),H2=2(-1,7…13),H3=Q(1-2,),H=0(2,3614)H=Q(2-3,), H。=Q(3,45614),H,=2(3-4,514),H.=0(46),H,=2(3-4-5,)Ho=Q(5,14), H1=2(5-14,),H2=0(14,),H3=Q(4-6,)H4=Q(6,),Hs=Q(-1-7,)H6=Q(7, 8…13),Hm=2(7-8,11),Hw=0(8,9101213),Hg=2(7-8-11),H0=2(I1,)H2=2(8 -9,12),H2=0(9,1013),H2=Q(8-9-12,),H4=9(12,Hs=Q(9-10,),H%=Q(10, 13),H7=Q(10-13,),Hx=2(13,5其中有v+1=15个叶阵；H,H,Hg,H,H2,HB,H4, Hs,H9,H0,Ha,H,H5,Hn,Hx;每个叶阵寻出A阵的一行，例如H3=Q(1一2，)→A (1;)=-[2(1;)-2(2:)]=[-1100].从A阵可画出所实现的有向图G如图2(a). H=0 ● H H H H ● H : H, H, H H H H H H H H Hw HMHg Hx H H g Ha A(1;) A(3;） A(5) A(7:) A(9) A(11;) A(13;) A(I5) 图3Q的可行分解树DT Fig.3 The feasible decomposition tree DT of 4结论 本文导出了有向Q可实现的充分必要条件和G在有向二同构意义上的唯一性，并应用 超图理论和二分解概念解决了引言中提出的两个问题. 参考文献 1 Wu M Y,Chan S P.On the Properties of Directed Switching Networks,Proc ISCAS'83,New York: IEEE,1983.350 2 Mayeda W.Realizability of Fundamental Cut-set Matrioes of Oriented Graphs.IEEE Trans Circuit The- oy,1963,10(1):133 3黄汝激，应用超图理论实现有向基本割集矩阵，电子科学学刊，1992,14(1)：50 4 Mayeda W.Graph Theory.New York:Wiley,1972.139

19 0 北 京 科 技 大 学 学 报 第 16 卷 解 应用 R F C M D M 于 Q 可 得结 果 : d = 1 ; 第 一次分解 时 y = 1 , 综 合 出的 T 和 几如 图 2 (b ) 和 c( ) ; 通过 。 次分 解 求 得 Q 的 一 个 可 行 分 解树 如 图 3 , 其 中 H 二 Q ( , 卜 · 14) 有 28 个 子 阵 , H I 二 Q ( l , 2 … 6 14 ) , 从 = Q (一 l , 7 … 13 ) , 从 = Q ( l 一 2 , ) , 凤 = Q (2 , 3 … 6 14 ) , 凡= Q ( 2 一 3 , ) , 从= Q ( 3 , 4 5 6 14 ) , H 7 = Q ( 3 一 4 , 5 14 ) , 从= Q ( 4 6 ) , 凡= Q ( 3 一 4 一 5 , ) H L。 = Q ( 5 , 14 ) , H l l = Q ( 5 一 14 , ) , H 1 2 = Q ( 14 , ) , H 13 = Q ( 4 一 6 , ) , H , 4 = Q ( 6 , ) , H 巧 = Q ( 一 l 一 7 , ) , H 16 = Q ( 7 , 8… 13 ) , H 17= Q ( 7 一 8 , 1 1 ) , H I: = Q ( 8 , 9 10 12 13 ) , H 19 = Q ( 7 一 8 一 1 1) , 几 = Q ( 1 1 , ) , 从 1 = Q ( 8 一 9 , 12 ) , 月刀 = Q ( 9 , 10 13) , 月刀 = Q ( 8 一 9 一 12 , ) , 凡 ! Q ( 12 , ) , 月乃 = Q ( 9 一 10 , ) , 26H = Q ( 10 , 1 3 ) , 几 = Q ( 10 一 1 3 , ) , 几= Q ( 13 , ) ; 其 中有 v + l = 15 个 叶 阵: H 3 , H S , H g , H l l , H 12 , H 13 , H o4 , 城 5 , 城 9 , 凡 , 儿 , 几 , 凡 , 几 , H彭 每个 叶 阵寻 出 A 阵的 一 行 , 例 如 从 = Q ( 1 一 2 , ) ~ A ( l ; ) = 一 〔Q ( l ; ) 一 Q ( 2 ; )』= 【一 1 1 0 … 0 1 . 从 A 阵可 画 出所 实 现 的有 向图 G 如 图 2 ( a ) . 县 杏 备 易 备 奋 备 备 辜 备 幕 丢 导 县 毒 A ( l : ) A (3 : ) A ( 5; ) A (7 ; ) ^ (9 : ) A ( 1 1; ) A (13 ; ) A ( 15; ) 图 3 Q 的可行分解树 D T 瑰 . 3 1触 免画b触 血以朋训刻加 。忱 D T of Q 4 结 论 本文 导出了有 向 乌可 实现 的充分 必要 条件和 G 在有 向二 同构 意 义 上 的 唯 一 性 , 并 应 用 超 图理论和二 分解 概念 解决 了引 言 中提 出的两个 问题 . 参 考 文 献 1 W u M Y , C ha l l S P . O n 此 P or pe rt 治 of D 派以ed s 俪 t c hi n g N 己t认。 ksr , P ocr 巧C AS ’ 83 , Ne w yo kr : IE E E , 198 3 . 3印 2 M a 界da W . R 周山己bil ty of F 切队坛 ~ 园 C u t 一 set M a 川a 治 of o ir e n 曰 G m p比 . IE E E T ~ C irC 山t 们 l e - o ry , l % 3 , 10 ( l ) : 133 3 黄汝激 . 应用超图理论实现有 向基本割集矩 阵 . 电子科学学刊 , 1卯2 , 14 ( l ) : 50 4 M a 界da W . G ar P h l l联 , yr . Ne w yo kr : W ile y , 1 972 . 1 39