·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 和 几