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

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 的实现

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