有向基本割集矩阵的超图综合法

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

块数大于2的问题。本文应用超图理论提出了从有向Q,的树路子阵Q逐层判断其可实现性 和综合出其对应有向图G的算法RFCMHGT。它的原理直观。 1有向图关于基本割集的超图和等效图 设已知一个元素为0、1和-1的n×e阶基本割集矩阵Q,=〔IQ:),I为单位阵，Q,称为 Q,的树路子阵，因为它的每行对应于一条树支，每列对应于一条连支和与该连支构成基本 回路的一条树路。行（树支）号集t={1,…,n},列（边）号集g={1,…e},Q:p的列（连 支)号集利={n+1,…,e}。要求实现Q,即综合出一个连通有向图G,以G为其基本割集的 矩阵。若Q,含有互不关联的d块（子阵）Q1,…,Q,则它们可以分别进行实现。若它们实现 成有向图G1,…,G,则由它们共有一点（参考点）所得的图G就是Q,的一个实现。暂时 假设Q,只含一块，并省去下标f,即设Q=〔IQ,。令M(R,)、M(,C)和M(R;C)分别 表示矩阵M中行集R、列集C和行集R及列集C所构成的子阵，则Q=Q(t,g),Q。=Q(: t)。 定义1矩阵Q-,Y∈t,是指从Q中移去行列Y、列Y和列集tr得到的矩阵，即 Q-y=Q(t-{y},g-{Y}-tr),tr={k|Q(ysk)≠0，k∈1} (1) 一般Q-x可按行划分成互不关联（即没有公共连支）的C个子阵（块）Q-(t:;),,为 块i的行（树支）号集，=1，"，c。若Q可实现成图G,则块Q-r(t:)对应于子图G。 令行y对应于G。,t。={y}。暂时不考虑边的方向和各G:内部的边及顶点，仅考虑每个G:的 端点集E,以便搞清各G,之间的联接关系。根据超图理论5，E,是超树支，超树支集 E={E,E:,…,E。}构成超树T,有向图G(图1(a)变成无向超图HG(图1(b)。对应 于基本割集y中每条连支k,HG中有一条由超树支组成的超通路Px与连支K构成超回路， Px称为超树路，在E,左、右的子超树添上E.后各称为左超树LT和右超树RT。RT(LT) 内E:(>0)的端点中离E,的右（左）端最近（即对应超树路最短）者称为E,和t,的父点r:。 若把E。(t。)用等效树支“1代替，把E,(t,),>0,的从i,到其余各端点的二端子超边E.(树 路p.)各用一等效树支4，a>1,代替，则E,(t,)变成以r:为中心的等效星树1.：（每个t. 的所有树支互称为伴随树支)，T(t)变成等效树t,HG(G)变成无向等效图G。(图1（©）。 1的在41左、右子树添上“1后各称为左树L和右树R。如果从4：和E。开始向右、左逐步生 长t.和T,则生长：和E,的等效树支s,=u。(树支f∈p)称为t.和E,的等效父支（父支）， 记作rb()=b;从等效树支4。（树支j)生长出的等效树支u。(树支h)称为“.(）等效子支 (子支)、从u.生长出的所有右（左）等效子支的集合记作Rt.(Lt.),E。、41和y各称为 T、t,和的根支。 定义2定义Q,关于行y的无向子阵J,如下： Qpg←Q,(tg多t,),ty=t。Ut1/U…Ute, (2) J,←Q?(所有元素取绝对值)。 对于i=0,1,…c进行：从y(t;)中取出所有相异列的列号组成集Z:;对于S=1, 186

块数大于 的向题 。 本文应 用 超图理论提出 了从有向 了的树路子阵 了， 逐层判断其可 实现性 和综合 出其对应有向图 的算法 。 它的 原理直观 。 有向图关于基本 割集 的超图 和等效图 设已知一个元素为。 、 和 一 的 阶基本割集矩阵 ， 〔 ，， 〕 ， 为单位阵 ， ，， 称 为 了 的 鱼路圣阵 ， 因为它的每行对应于 一条树支 ， 每 列对应于一条连 支和与 该连支构成基本 回 路的一 条树路 。 行 树支 号集 ，… ， ， 列 边 号 集 夕 ， … ， ， 的 列 连 支 号集 习 二 谧， 十 ， … ，。 。 要求 实现 ，， 即综 合 出一个连通有向图‘ ， 以‘ 了为其基本割集的 矩阵 。 若 ， 含有互不关联的 块 子 阵 ， ， 一 ， ，‘ ， 则它们可以分别进行实现 。 若它们实现 成有向 图 了 ， … ， 了‘ ， 则 由它们共有一点 参考点 所得 的 图 就是 了 的一个 实现 。 暂时 假设 了只 含一块 ， 并省去下标 ， 即设 〔 ， 〕 。 令 ， 、 和 分别 表示矩阵 中行集 、 列集 和行集 及列集 所构 成的子阵 ， 则 ， ， ， 二 。 定义 矩阵 一 ， ， 任 ， 是指从 中移去 行 列 、 列 和列集 得到的矩阵 ， 即 一 ， 一 ， 一 一 ， 夕 笋 ， 任 一般 一 可按行 划分成互不关联 即没有公 共连支 的 个子阵 块 一 ‘ ， ，为 块 的行 树支 号集 ， 二 ， ， 。 若 可 实现 成图 ， 则块 一 。 ‘ 对应于 子 图久 。 令行 对 应于 。 ， 。 二 对 。 暂时不考虑边 的方向和各 ‘内部的边 及顶点 ， 仅 考虑每个 ‘ 的 端点 集 ‘ ， 以便搞清各 。 之 间的联接关 系 。 根据超图理论 ‘ ” 〕 ， ， 是超树支 ， 超树 支 集 二 丈 。 ， ， … ， 。 构成超树 ， 有 向图 图 变成无向超图 图 。 对 应 于基本割集 中每 条连支 ， 中有一 条 由超树支组成的超通路 二 与连 支 构成超 回 路 ， 尸二 称为超树 路 。 在 。 左 、 右 的子超树添上 。 后各称为左超树 和右超树 。 内 。 的 端点 中离 。 的右 左 端最近 即对 应超树路最短 者称为 ‘和 ， 的父点 ‘ 。 若把 。 。 用等效 树支 。 ， 代替 ， 把 ， ‘ ， ‘ ， 的 从“ 到 其 余各端点 的 二端 子超边 。 。 树 路 。 各用 一等效 树支 。 ， 。 ， 代替 ， 则 ‘ ‘ 变成以， ‘为 中心 的等效 星 树 ‘ 每个 ， ‘ 的 所有树支互称为伴随树支 ， 变成等效 树 ， ， 变成 无 向等效 图 ， 图 。 。 的 在 。 左 、 右 子树添上 “ 后各 称为左树 和右树 。 如果 从 。 和 。 开始向右 、 左逐步生 长 和 ， 则生长 ， ‘ 和 ‘ 的等效树支 ， 二 “ 。 树支 ‘ 任 。 称为 ，和 ‘ 的等效父支 父 支 ， 记作 ’ 二 叭 从等效 树支 “ 。 树支 生长 出的等效 树支 “ 。 树支 称为 。 。 力等效 子支 子支 、 从 。 。 生长 出的 所有右 左 等效子 支的集合记作 。 。 ， 。 、 。 和 各 称为 、 和 的 根支 。 定义 定义 ，关于行 的无向子阵 ， 如下 ，， ， ， ， ， ， 。 … ‘ ， ， 所有元素取绝对值 。 ， 对于 。 ， ， ” · 。 进行 从 ‘ 中取出所有相异 列的 列号组成集 己 ， 对于

15 13 28 16 (a)G 15 E6 、 16 16 19 (b)HG1-HG 15 1 1411 1w9 1410 19 、-18 (c)Ge=Ge 15 0 23 23 ld)G2 (e)G2 图1有向图G及其超图HG和等效图G。、G2、G3 Fig.1 Directed graph G and its hypergraph HG and equivalent graphs G.,G.,G3 -1 …,1Z进行：←Z(s),a←∑1Z+,P.←{lJy:)=1,jt:,2{化 r=0 ,)=y,∈i,wo。习1Z。p.C,称为：的a号树路， 187

一 一 一 一 一 一 一 、 、 、 、 、 。 三 一 一 一一 一一下犷 一 一一 一 一 一、 ，、 匕 汀公，二 月 。 二 沪 嘴 舍、 、 饰 ‘ 廷 图 有向图 及 其超图 和 等效图 ， 、 ‘ 子 、 ‘ 了 ‘ ‘ ， ， ， ， 苍 一 … ， 一 进行 十 一 “ ， 十 艺 二 卜 “ ， 一‘ 益 · ， 任 “ ， ， 一 ‘ ‘ 食‘ ‘ ， 瓦 ， ‘ 任丁 ， 不 。 。 ‘ 。 。 ， 习 ‘ 。 户 。 二“ 称为“ 的 号树路 ， 名 二

拟称为p.到t:的下标变换集。了，的行数n,=n,列数1，=|t,。 定义3把J,中每条树路p.用一等效树支“。代替，并以Z。作为“。关联的连支集，构 成行J.(u),即Va∈{1，…，n},Vk∈t,若k∈Z:则J,(u；k)←1，否则J,(“. k)一0，那么行（树支）集t,变成行（等效树支）集t.(t.:内所有行互称为伴随行)，形成 的矩阵J,称为Q关于y的等效树路阵或G.的树路阵。J.的行、列号集各为，=t.。Ut,U…Ut,e 和t.=|t,行、列数各为n,和.=【，。 定义4元素为0和1的矩阵M称为(0,1)矩阵。M中每行（列）的非零元素数称为该 行（列）的长度。元素全为1的行（列）称为么行（列）。元素全为零的行（列)称为零行 (列)。设M的行、列号集各为R和C,若 M(i;k)-M(j;k)≤0，Vk∈C (3) M(ism)-M(i,n)≤0，Vi∈R (4) 则称行i含于行j,列m含于列”，记作M(i;)CM(j;),M(;m)二M(;n);否则称为 行不含于行i,列m不含于列n,记作M(,)CM(i;),M(;m)CM(;n)。若(3)和(4) 式中等号成立，则称为行等于行j,列m等于列n,记作M(i;)=M(j;),M(;m)= M(;n)。=是C的特殊情况。 定义5对于矩阵J.的任一列k,定义列k的增广列k“如下：若J.(“。;k)=1,“.∈t, 则对于所有u6∈t,J,(“。k)←1。从Jy(J,)中选一最长列k,去掉所有含于列克1(k,)的 列后，再选一最长列k,去掉所有含于列k2(k2·)的列，依此类推，直到全部列都去掉，所 得列集{k1,,k}称作J,的覆盖列集，记作Z,(J,的增广覆盖列集，记作Z)。 2从等效树路阵Je综合等效树te和超树T 要从Q综合G,可先从Q,综合G的有向树t,再给t添上所有连支，就形成G。若有 从J,综合.和T的算法，就可接着应用该算法于Q-,的各分块，依此类推，逐步产生出t。 为此应将J,中每列k的树支集Pk都实现成一条树路，而且彼此相容，即能够形成一等效 树t,。 定义6对于任意k∈Z,px←{u。l4.∈t.,J.(“.;k)=1},J.x←J.(px)。h-1,对于 j=2,…,lPx进行：若px(j)=“,则i←W(a),若t.l>1,则把当行i加上（逻辑和） 其在」，中的每个伴随行时所形成的新列排在J,x的右边（这是由于t:为星树，这些列也是 应被实现的树路)，即对于r=1,…,1tl进行多若t.(r）=46,b卡a,则对于s=1,…, 1.进行，若j.(b,s)=1则h←h+1,J,x(;h)←J,x(s),J.x(a,h)1。比较各列，若有相 等列，仅留一列，移去多余列。把行按长短从上到下排列。若几行等长，则其中对应于末稍 树支（即I.(i)=1)的行j（若有的话）应排在下面，其余行按行号自然顺序排。形成的矩阵 称为I,x的增广阵，记作Ix。若J.k的第j行变成Ix的第i行，则Sx〔px(j)门←i,Tx() px(),集Sx和Tx分别称为I.到Tx的行号正和反变换集。Jx的行、列号集记作Rx和Cx。 根据定义6，注意到px关联的所有连支都跨越根支41，并且px的末稍树支“，（用 I,(“,)=1表示)上不容许再生长树支，可导出下面的定理1和推论1。 定理1I,x的增广阵Tx具有下列性质： 188

甜称为户 到 ‘的下标变换集 。 ， 的行数 ， 。 ， 列数 ， ， 。 定 义 把 ， 中每条树路 。 用 一等效树支 “ 代 替 ， 并以 。 作为 “ 关联的连 支集 ， 构 成行 ， 即 任 谧 ， … ， 。 ， 任 ， ， 若 〔 ‘ 。 则 。 ， 否则 “ 。 ， 那么行 树支 集 变成行 等效树支 集 ‘ 二 内所有 行互称为 伴随 行 ， 形 成 的矩阵 ， 称为 关于 的等效树路阵或‘ 的 树路阵 。 的行 、 列号集各为 ， ， 。 ， ， 日 … 。 和 二 ， ， 行 、 列数各为气和 ， 二 ， 。 定义 元素为 。 和 的矩 阵 称为 ， 矩阵 。 中每 行 列 的非零元素数称为该 行 列 的 长度 ， 元素全为 的行 列 称为鑫丘三列 。 元素全为零的行 列 称为雯旦 左业夕 设 的行 、 列号集各 为 和 ， 若 一 ， 几〔 一 。 ， 任 则称行 含于行 ， 列 含于列 ， 记作 ， ， 二 否 则称为 行 不含于行 ， 列。 不含于列 ， 记作 己 ， 己 。 。 若 和 式 中等号 成立 ， 则称 为行 等于 行 ， 列 。 等于 列 。 ， 记作 ’ 了 ， 舰 万 。 是二 的特殊情况 。 定义 对 于矩阵 的任一列 舟 ， 定义列 的增广列 如 下 若 。 幻 ， “ 任 。 ‘ ， 则对 于 所有 “ 。 任 ‘ ， “ 。 ’ ， 。 从 ， 中选一最长列 ， 去掉所有含于列 儿 的 列后 ， 再选一最长列秃 ， 去掉所有含于列 的列 ， 依此类推 ， 直到全部列都去掉 ， 所 得列集 仕 ， … ， 讨称作 ， 的 覆盖列集 ， 记作 ， 的增广覆盖 列集 ， 记作 。 从等效树路阵 。 综合等效树 。 和超树 要从 综合 ， 可 先从 ， 综合 的有向树 ， 再给 添上 所有连支 ， 就形 成 。 若有 从 ， 综合 和 的 算法 ， 就可接着应用 该算法于 一 的各分块 ， 依此 类推 ， 逐步产生 出 为此 应将 中每列 的树支集 尸 都实现成一条树路 ， 而且彼此相 容 ， 即能 够形成一等效 树 。 定义 对 于任意 任 ， ， 尤 。 。 “ 。 任 ， 无 二 ， 二 ， 二 。 ， ， 对 于 二 ， … ， 户二 进行 若夕二 。 。 ， 则 平 ， 若 ‘ ， 则把 当行 加上 逻辑和 其在 中的每个伴随行时 所形成的新列排在 ， 的右边 这是 由于 ， ， 为 星树 ， 这些 列 也是 应被实现的树路 ， 即对 于 ， ， ‘ 进行 ， 若 ， ， “ ， ， 午 ， 则对 于 ， ” · ， 进行 ， 若 ， ， 则 “ ， ， 二 “ ， ， 二 ， ， 。 比 较各列 ， 若有相 等列 ， 仅留一列 ， 移去多余列 。 把行按 长短从上到 下排列 。 若几行等长 ， 则其中对应于末稍 树支 即 的 行 若有的话 应排 在下面 ， 其余行按行号 白然顺序排 。 形 成的 矩阵 称 为 ‘ 的遭鱼鉴 记作 八 。 若 ‘ 的 第 行变 成 八 的第 行 ， 则 二 〔 ‘ 〕 ‘ ， 二 。 ，夕以 ， 集 和’ 分别称为 到几 的行号正和反变换集 。 八 的行 、 列号集记作 和 ‘ 。 根据定义 ， 注意到 ‘ 关联的 所有连支都跨越根支 。 ， 并且 二 的 末 稍 树 支 “ 用 二 表示 上不容许再生长树支 ， 可 导出下面的定理 和推论 。 定理 入 二 的增广阵 几 具有下列性质 名

(1)第一行为么行，k号连支对应列为么列。 (2)若Ix可实现成树路pK,则右（左）树路Rpx(LPx)中串联树支的对应行必相等， 非串联树支的对应行必不等而且长度不同，离根支4：愈近的树支对应行愈长，在丁x中愈靠 上。 (3)设从Jx已产生px的子树路px二Px,pk的右和左末稍树支各为ax和bs,则从Tx别 去pk的对应行集S(pk)〔rxrx-S(p)门和零列集Z。={月jeCx,Ix(rx)=0}(Cx← Cx-Z,)后，若第一行Rx(1)为么行，则其对应树支ex=Tx(Rx(1)是唯一当前待生树 支，它将生长在P:的右或左侧，否则，不含于行Rx(1)的最长行（称为Rx(1)的匹配行）的 对应树支e:也是当前待生树支，ex与e:将分别生长在pk的两侧。 (4)当前待生树支dx(ex或e)可生长在父支Sx(ax或bx)上的必要条件是(a)Sx不是px 的末稍树支，即I,(Sx)=0;(b)行dx含于行Sx,即Jx(dx;)CJx(Sx;)。 推论1矩阵Jx可实现的一个必要条件是Ix或其子阵不含有3个长度相同的不相等行。 注意：(1)星树t,:中所有等效树支是互相伴随的，必须同时产生，即在生长ex∈t,:和 e∈t.:的同时必须生长t.和t:',t,和t。“称为当前待生星树，E:和E称为当前待生超 树支。(2)当从丁x综合了px时，不仅实现了J,的列k,也实现了丁.中含于增广列k·的所有 列。(3)所有满足px∩t三+中，k∈Z,的树路px的集合称为生长1，：的树路集，其对应列 号集记作Z,Z:CZ,。根据这些定理1可导出定理2。 定理2设I.的增广覆盖列集Z。={k,…,km},构造增广阵Jk1,“,Jx,从它们 同时综合树路Px1,·,Pxw,若整个综合过程满足下面的相容生长条件，对于每棵当前待 生星树t,与所有k∈之，所有fx=PxAt,都是当前待生树支，而且都能够生长于同一条等 效父支Sk(ax或bx)=4s上，即 Vk∈Z,Sx(ax或bx)=4s,I.(s)=0,Ix(fx;)二Ix(Sx;), (5) 则Px1,“,卫x#是相容的，即它们能组成等效树t,。 根据定理1和2可设计一个从J.综合t,和T的算法SHTMJE如下。算法中每步生长过程 进行了两次，第一次检查相容生长条件是否满足，若满足才进行第二次的实际生长过程；若 从右侧进行和从左侧进行生长都不满足相容生长条件，则，不能实现。每条等效树支“。在算 法中用其下标a表示。 算法SHTMJE(Je,Y;RT,LT,Rt,Lt,rb) (1)初始化：所有数组清零，a←1，RT(r)←0，B←1，LT(1)←0；按定义5求Ze, Vk∈Ze,gx←1，hxl,Rpx(1)←1，Lpx(1)←1。 (2)Vk∈Z.,按定义6从J,构造Jx、Sx、Tk、Rx和Cx,RxRx-Rx(1)。 (3)若Z.=中，转步骤T,否则Vk∈Z.进行（求等效父支ax、bx、当前待生树支集Bx 和当前待生超树支集Dx): ①Z。←{ili∈Cx,Tx(Rx:j)=0},Cx←Cx-Zo,Z。r{jj∈Cx,Ix(Rx(1)5 j)=0},ex←Tx(Rx(1),i-W(ex),ax←Rpx(gx),bx*-LPx(hx)。 ②若Zo1=p,则Bx←{ex},Dx←{》。 ③若Zg1卡中，则r-第一个己Rx(1)的最长行的行号，eR←Tx(r),"-W(e), Bx{ek,e》,Dx←{i,}。 189

第一行为么行 ， 寿号连支对应列为么列 。 若 、 可 实现 成树路 ， 则右 左 树 路 夕、 ‘ 中 串联树支的对应行必相等 ， 非串联树支 的对 应行必 不等而且长度不同 ， 离 根支 。 ， 愈近 的树支对应行愈长 ， 在 八 中愈靠 上 。 设 从几 已产生 的子树路 二、 三 ， 关的右 和左 末稍树支各 为 二 和 、 ， 则 从 二 删 去 差 的对应行集 二 〔 ‘ ， 二 一 印关 〕 和零 列 集 。 二 二 ， 》 二 一 。 后 ， 若 第一行 为 么行 ， 则 其对应树支 ‘ 二 袱 是唯 一 当前待 生 树 支 ， 它 将生长 在 关的右 或左 侧 多 否则 ， 不含于行 二 的 最长行 称 为 二 的 匹配 行 的 对 应 树支嵘 也 是 当前待生树支 ， 二 与 要将分别生 长 在 鑫的 两 侧 。 当前待生树支 二 二 或 份 可 生长 在父 支 二 、 或 二 上的 必要条件是 二 不是夕‘ 的末稍树支 ， 即 二 行 、 含于行 、 ， 即 ‘ 、 〔 、 、 。 推论 矩阵几可实现 的一个必要 条件 是几或其 子阵不含有 个长度相 同 的 不相 等行 。 注意 星树 口 ‘ 中所有等效树支 是互相 伴随的 ， 必须 同时 产生 ， 即在生长‘ 任 ， 。和 。 分任 。 。 ‘ 的 同时 必须生长 ‘和 ‘ ， ， ‘和 ， ‘ 称 为 当前待生 星树 ， ，和 ‘ · 称 为 当前待 生超 树支 。 当从几综合 了 时 ， 不仅实现了 ， 的 列 ， 也 实现了 中含 于增广列 的所有 列 。 所有满足 二 门 。 今 功 ， 友任 ， 的树路 二 的集合称为生 长 ， ‘ 的 树 路集 ， 其对 应 列 号集记 作 ‘ ， ‘ 仁 。 。 根据这些 定理 可 导 出定理 。 定 理 设 的增广 覆盖 列集 。 伪 ，， … ， 讨 ， 构造增广阵 几 ， … ， 几，， 从它们 同时综合树路 ， ， 一 ， 二 二， 若整 个综合过程满足下面的相 容生长条件 ， 对 于每裸 当前 待 生星树 。 ‘ 与所有友任二 ‘ ， 所 有 二 二 门 ‘ 都是当前待生树支 ， 而且都能 够生长于同一条等 效父支 二 ‘ 或 二 。 。 上 ， 即 益任 ‘ ， 二 ‘ 或 二 ， 。 ， 二 ‘ 二 ‘ ， 则 ， 二 ， 、 二 是相 容的 ， 即它们能 组 成等效树 。 根据定理 和 可 设计一个从 综合 和 的算法 如下 。 算法 中每步生长过程 进行了两 次 ， 第一次检查相 容生长条件是否满足 ， 若满 足 才进行第二次的实际生长过程 若 从右侧进行和从左 侧进行生长都不满足相 容生长 条件 ， 则 不能 实现 。 每 条等效 树支 。 。 在算 法 中用 其下 标 。 表 示 。 算法 ， ， ， 亡， ， ‘ 初始 化 所 有数组清零 ， ， ， ， 。 ， 声， ， ，。 按定义 求 ， 任 ， 夕、 ， ， ‘ “ ， 二 ， ， ‘ ， 。 任 ， 按定义 从 构造 二 、 ‘ 、 ‘ 、 ‘ 和 二 ， 二 ， 二 一 二 。 若 ， 价 ， 转步骤 ， 否则 壳任 进行 求等效父 支 听 、 久 、 当前待生树支集 二 和 当前待生超树支集 户 ① 。 ， 币 任 二 ， 、 二 ， ， ‘ 一 。 ， 。 任 、 ， ‘ 、 二 ， 二 ， ‘ 二 ， 牙 ‘ ， ， ‘ 二 ， 、 ， ‘ 二 。 ② 若 。 ， 二 价 ， 则 “ 对 ， 补 。 ③ 若 。 ，午价 ， 则 第一个 己 八 的 最 长行 的行号 ， 心 “ ‘ ， ’ 甲 为 ， 刀‘ ， 夏 二 ， 里 ， 二 ， 丈 ， ， 。 习

(4)D←Uxz。Dx(D中元素按自然顺序排)，V∈D,2,中。Vi∈D和Vk∈Z.进行 (修改Bx和Dx,求生长t的树路号集Z,)； ①p:K←t:∩px,若P,k={fx}牛中，fx∈Bx,则Z,Z:U{}。 ②若p:x={fx}+中，x不属于Bx,则若Bx={ex,Bx-BxU{fx},Dx←DxU{的， Z,←Z,U{k};若Bx={ex,e},转步骤6。 (5)检查相容生长条件，生长当前待生树支和当前待生超树支： ①m1←0，n1-0,1←0。 ②D←D,M←中，ST中，S1←p,r←0 ③若D=中，转步骤3；否则i←D(1),Mi)←1，转步骤⑤。 ④若r=0,m1三0，则m1←1，I←n1,转步骤②。若r=0,m1=1,转步骤①。若 r十0，，则i←ST(r),1←S1(r),r-r-1,转步骤⑤。 ⑤Yk∈Z,进行（取出待生树支∫x,匹配超树支·进栈）：fkBx∩t,,若Dx-《i》 ={》+中，M(i)=0,则M()←1，r←r+1,ST(r)←i",若1=0，Sl(r)←1，否则 S1(r)-0 ⑥若m1=0,1=0,转步骤⑦，若m1=0,1=1,转步骤⑧。若m1=1,1=1,转步骤 ⑩。若m1=1,【=1,转步骤①。 ⑦若Vk∈Z,ax=a,I(a)=0,Jx(fx;)CJx(ax),则D"←D·-{i},转步骤④； 否则转步骤⑨。 ⑧若Vk∈Z,bx=b,I.(b)=0,Jx(fx)CJx(bx),则D·←D·-{i},转步骤④ 否则转步骤⑨ ⑨若n1=0,则r1←1，，1←1，转步骤②；否则转步骤⑥。 四Vk∈Z,进行，gx←9x+1,Rpx(gx)←fx,a←ax,jSx(fx),Rx←Rx-{i}, 若Rx=中，，Z.←Z.-{}。a←a+1,RT(a)←i,rb()←a,Rt.←Rt.Ut,D←D-{i}, 转步骤④。 ①Vk∈Z,进行；hx←hx+1,Lpx(hx)fx,b←bx,jSx(fx),RxRx“{j}, 若Rx=中，Z,*Z.-{k}。B←B+1,LTBi,rb()←-b,Lt。←Lt。Ut,D←D-{i}, 转步骤④。 (6)停止，显示“J,不能实现”。 (7)结束SHTMJE。 了从基本割集矩阵Q综合有向图G 定义7从矩阵Q构造二维数组L和一维数组D如下： L←中，D中，L(i;):m-{|k>n,Q(i;k)≠0}， (6) L(k;)xn←{|i≤n,Q(,k)≠0}，D()←lL(i,川，i=1,…,e, 数组对(L,D)称为矩阵Q的邻接表。 应用深度优先搜索算法DFS(例如文献〔6)中算法5.2)从(L,D)可求得Q的块数和各块 的行号集。 190

， ‘ 中元素按 自然顺序排 ， ‘任 ， ，，价 。 才任 和 庵任 进行 修 改 和 ， 求生长 ，的 树路号 集 。 ① 户 ‘ 二 ， 。 自户‘ ， 若 ‘ 二 尤 含 价 ， 二 任 ‘ ， 则 ‘ ， ‘ 习 。 ② 若 户 ‘ 、 二 斧 价 ， 二 不属 于 二 ， 则若 ‘ 二 ， ‘ 二 匕 ‘ ， 二 ， 二 日 ， ‘ 谧壳 若 ， 贯 ， 转步骤 。 检查相 容生 长条件 ， 生长 当前待生树支和 当前待生超树支 ‘ ① 。 ， 。 ， ， 。 ② 刀 ‘ ， “ 必 ， 劝 ， 价 ， ， ③ 若 ‘ 价 ， 转步骤 否则 ￡，刀 ’ ， ’ ， ， 转 步骤⑤ 。 ④ 若 ， ， ， “ ， 则 沉 ， ， ， 转 步骤② 。 一 若 ， ， ， 转 步 骤① 。 若 等 ， ， 则 ， ‘ 一 ， 一 ， 转步骤⑤ 。 ⑤ 吞任 ，进 行 取 出待生 树 支 二 ， 匹配超树支‘ 进栈 ‘ 二 自 ‘ ， 若刀二 一 ’ 圣今 沪 ， ‘ ， 则 ’ ， “ ， “ ‘ ， 若 ， “ ， 否则 ， ⑥ 若 二 、 ， 二 。 ， 转步骤⑦ ， 若。 ， ， 转步骤⑧ 。 若 ， ， 转步骤 ⑩ 。 若 ， ， 转 步骤 。 ⑦ 若 任 ‘ ， ‘ ， ， 二 ‘ 已 ‘ 二 ， 则 ， ’ 一 谧 ， 转步骤④ 否则转步骤⑨ 。 ⑧ 若 任 ‘ ， 二 ， ， 二 ‘ 二 二 ， 则 “ 一 ， 转步骤④， 否 则转步骤⑨ ⑨ 若 、 。 ， 则， ， ， ， “ ， 转步骤② 否则转步骤⑥ 。 ⑩ 任 ‘进行 ， ‘ ， 夕 ， 二 夕‘ ‘ ， ， 二 ， 二 二 ， 二 ， ‘ 一 ， 若 价 ， ， ， 一 。 ， ， ， ， ， 。 ‘ ， ， 一 ， 转步骤④ 。 ⑧ 掩〔 ‘进行 二 ， ‘ ， 夕二 二 ， ‘ ， 二 ， ， ‘ ‘ ， ， 二 一 ， 若 二 价 ， ， 一 伪 。 声 声 ， 声，‘ ， ‘ ， ， 一， ‘ ， ‘ ， “ 一 ， 转步骤④ 。 停止 ， 显示 “ 不能 实现 ” 。 结 束 。 从基本割集矩阵 综合有向图 定义 了 从矩 阵 构造二维数组 和一 维数组刀如下 价 ， 价 ， ‘ ‘ 、 。 “ ， 笋 ， 壳 二 。 ， ‘ 簇 ， 秃 笋 ， ‘ ， ， ， 亡 数组对 ， 刀 称为矩阵 的 邻接表 。 应用 深度优先搜索算祛 例如文献〔 〕 中算法 从 ， 的行号集 。 二 ， … ， 。 刀 可求得 的块数和各块

从基本割集矩阵Q综合有向树t是逐层逐块进行的。令H存放第m层的正在实现的Q的 一块子阵，H存放H"的树路子阵，X1(j)和X2()存放树支j的始点和终点号，t“和分 别表示第m层的正在综合的有向树和无向等效树，S(j)=1,-1或0表示树支j的方向与 根支y=y'的一致、不一致或未定，1（引jt")=1表示i是"的未稍树支，R={Rt}, Lt={Ltb}。 第m层是从H综合"，综合过程如下： (1)从H,求出J:和J,从J:综合出t:和T"(RT和LT")。计算每条树路px及其子树 路p:的末稍树支数9x和9，，若9x>2或g:>1,则Px不能实现。 (2)顺序处理RT中每条超树支E的对应子树t:(a)若J:(t”)=J:(t:,)(即= ,且Va∈t”,Ip引=1)则可以给t”中每条未处理(S(i)=0)的树支i标定方向和始、终 点号，即对于树支与其父支f的对应基本割集的所有公共连支1检查乘积H”(i;)H(f;) :是否都相等，若否（表示行i与∫的元素符号有矛盾），则H“不能实现，若是，则S() H(i;I)H(f,)S(f),I(j)1,将E的父点号赋于j的左端，若i有一条子支h已处理 过，则将h的左端点号赋于i的右端，否则vv+1,将v赋于i的右端。(b)若J(”,)≠ J:(::)(即引≠或3a∈，pl>1),则的结构未定，H1Q(tU{f};), 进入第m+1层，从H+1综合m+1=t”U{f}。 (3)顺序处理LT,中每条超树支E:的对应子树：；与(2)类似，但左、右二字互换。 根据上述原理可设计一个从H“综合t"的算法SDTFCM和从Q,综合G的主算法 RFCMHGT如下。 算法SDTFCM(Hm;ym,tm,S,x1、X2) (1)初始化：Q。←H,y←y",t。-{y},t,←1。 (2)按定义7建立H二y的邻接表(L,D),调算法DFS从(L,D)求出H二y的块数c和 各块的行号集t,i=1,“,C。 (3)按定义2从Q,求得Jy、W和P。,a=1,…,n。若m>2,求Jy的覆盖列集Zy,对 于每个i∈{1，…，c}和每个k∈Zy进行；9：x-∑I(引i∈t,Jy(i;k)=1),若9x>1,转 步骠(7)；对于每个k∈Zy进行；9x←已9：，若9x>2转步骤(7)。 (4)按定义3从Jy求得J.和t.1,t=1,…,c。若m>1,对于a=1,…,n,进行；q.← 已I(引j∈p),若9.>0则I.()-1,否则I.(a)←-0。 (5)调算法SHTMJE从J.产生RT,LT,Rt,Lt和rb: ①若=1，转步骤②：否则找出含有父支f"的t?,若∈RT则L←-1，否则L←1。 若L“R-1=-1则RT"-LT,LT"←RT,Rt"←Lt,Lt"←Rt,转步骤③：否则转步骤②。 ②RT←RT,LTm←LT,Rt"←Rt,Lt←Lt。 ③rb"-rb,I:←I.p8p。,a=1,…,n；t←t6,t,-ti,i=1,…,c。 (6)顺序处理RT"和LT"中每条超树支E?(处理RT时R1,处理LT"时R"← -1) 191

从基本割集矩阵 缥合有向树 是逐层逐块进行的 。 令 ‘ 存 放第 层的正在卖现的 的 一块 子阵 ， 君存 放 ‘ 的 树路子阵 ， 和 存 放树支 的始点和终点号 ， “ 和代分 别表示第‘ 层 的正在综合的有向树和无向等效树 ， ， 一 或 。 表 示树 支 的 方 向 与 根支 的 一致 、 不一致或未定 ， ’ ‘ 二 表示 挤是 ’ 的 末稍树支 ， 。 ， 。 第 层是丛尘兰查竺， 盆查过程如下 从 贯求 出 罗和 ， 从 综 合 出片 和 ’ ’ 和 “ 。 计算每 条树路 及其子树 路 。 ，的末稍树支数 ‘ 和 ，，， 若 ‘ 或叮 ‘ 。 ， 则 二 不能 实现 。 顺序处理 ’ 中每条超树支 丁的对应子树 号 若 笋 片 二 ‘ 即 州 片 ‘ 且 。 任叮 ， ， 则可 以给 绍 中每 条未处理 力 的树支 标定方 向和始 、 终 点号 ， 即对 于树支 与其父支 了的对应基本割集的所有公 共连 支 检查乘积 二 是否都相 等， 若否 表 示行夕与 了的元素符号有矛盾 ， 则 ‘ 不能 实现 若是 ， 则 ’ ， 万 丁’ 二 ， ’ 将 罗的父点号 赋于 夕的左 端 若 夕有一 条子支 已处理 过 ， 则将 的左 端点 号 赋于 的右端 ， 否则 ， 将 赋于 夕的 右端 。 若 种 丁户并 才丁 ‘ 即 了 并 ‘ 】或 日 〔 丁 ‘ ， 丁 ， 则 尹的结 构未定 ， ’ “ ‘ 一 丁日 谧 ， 进人第。 层 ， 从 ’ ’ 综 合 ’ ‘ 才丁七 》 。 顺序 处理 。 中每 条超树支 的对应子树 甲 与 类似 ， 但左 、 右 二字互换 。 根据上述 原理可 设 计一个从 ‘ 综合 ’ 的 算 法 和 从 ， 综合 的 主 算 法 如下 。 算法 ， ， ， 、 初始化 ，，万 二 ， 少，夕 ’ ， 。 夕 ， 。 。 “ 。 按定义 建立 二， 的邻接表 ， 刀 ， 调 算法 从 ， 求 出 二， 的块数 。 和 各块的 行号集 ‘ ， ， … ， 按定义 从 ，求得 ， 、 牙和 ， ， 。 二 ， … ， ” ， 。 若 ， 求 的覆盖列集 ， 对 于每个 任 ， … ， 和每个 任 进行 “ 笋 任 “ ， ， 若 ‘ 二 ， 转 步骤 ， 对 于每个吞〔 进行 ‘ 。 ， ， 若 叮二 转步骤 。 按 定义 从 求 得 ‘ 和 ， ‘ ， 二 ， … ， 。 若。 ， 对 于 二 ， … ， 进行 ， 任 户 。 ， 若 。 则 。 。 ， 否则 ， 。 ， 。 二 调 算法 从 。 产生 ， ， ， 和 ① 若。 二 ， 转步骤 ② 否则找 出含有父支 ’ 的叮 ， 若 任 则 ’ 一 ， 否则 ’ ， 。 若 ’ ’ 一 ’ 二 一 则 ’ ， 一 ， ’ ， ， 刀 “ ， ’ ， ，转步骤③ ， 否则转步骤② 。 一 “ ， ‘ ， 君’ ， 。 ， ， ， 。 ， 二 ， … ， 。 ‘ 尹 ‘ ， 丁 ‘ ， 才 ， ‘ ，‘ ， … ， 。 顺序处理 ’ 和 ’ 中每条超树文 丁 处理 “ 时 ’ ， 处理 ’ 时 ‘ “ ②③

①若i=0则a←1，i←y",转步骤2；否则转步骤②。 ②找出E:的父支于和父点r:b←rb"(i),f←p8中离y"最远的树支影若R"S(f)=1 则r←X2(f),否则rX,(f)。 ③若t:l=|t:,l且Vat”4,Ip。1=1,且则对于每个it:,若S(i)=0,进行； i对于树支j与f的对应基本割集的所有公共连支I检查乘积H,(i:)H:(付：) 是否都相等，若否，转步骤(7)；若是，则S(i)←H。(i;1)H(f;l)S(f),I(j)1。若 RS(j)=1,X1(i)←r,否则X:(i)-r。 2找出树支j的子支h和子点S:若R=1,顺序检查c∈Rt:,否则检查c∈ Lt；若找到-一个c满足I(c)=1且|pg|=1,则h←p8(1)。若RS(h)=1则S←X1(h), 否则SX:(h)。若找不到上述c,则v-U+1,v。若R"S(i)=1则X2(j)-S,否 则X1（j)一S。 ④若{t1≠l或1a∈t,p引>1，则mm+1,H←Q(-1U{f},),H。←H (:t),从H,找出一个使H,(f;)≠0的最长列k,再找出使H(y,k)≠0，S(y)=0的 最长行y。对于y与∫的对应基本割集的所有公共莲支I检查乘积H:(y;)H(f;)是否 都相等；若否，转步骤(7)；若是，则S(y)一H(y;1)H(f;I)S(f),I(y)I,y y,f"f,调SDTFCM。 (7)停止，显示“H"不能实现”。 (8)mm-1,结束SDTFCM。 主算法RFCMHGT(Q,:S,X:,X2,A) (1)输入Q1。 (2)按定义7建立Q:的邻接表(L,D),调DFS求出Q:的分块子阵Q1x,x=1, …,d。 (3)对于￥=1，…，d进行； ①初始化：Q←Q,A←中，S←中，x1←中，x2←中，I←中，v←0，m←1，H"← Q,H。←H(;),yHg的最长行的行号，S(y)1,y←y,I(y)I, ②调SDTFCM,从H=Q综合有向树1=t,即产生t的树支的方向集S和始终点集 X1、X2o ③建立Q:.的图G1,的关联阵A.: A(X,(j);j)←1，A.(X2(j)s(i)*-1,j=1,,n p1{i1iet,Q(ii)≠0}，A,(j)←∑A.(;i)Q(;i),j=n+1,",e (7 （4)建立Q,的图G的关联阵A,4<-Diag〔A1,,A门。 (5)结束RFCMHGT。 本算法的计算时间主要决定于步骤②，最坏情况是d=1,m=1,J。=Q♪规模最大， 其计算复杂度为O(12),n和1为Q,的树路子阵Q,的行数和列数（限于篇幅，应用举例从 192

若 一 。则 。 一 ， ，， 。 ，转步骤 省 否贝。转步骤② 。 找 出 犷的父支 和父点 ’ ， ， 忿中离 最远 的树支 若 ’ 舍② 则 ， 否则 ， ， 。 ③ 若 】 犷 二 ， 】且 ‘ 丁 ‘ ， 厂 卜 ， 且则 对于每个 ‘ 罗 ， 若 ， 进行 对于 树支 了与 的 对应基本割集的 所有公 共连 支 检查乘积 厂 万 二 八 是否都相等 ， 若否 、 转步骤 若是 ， 则 厂 二 打 ， 。 若 ’ ， ， 否则 。 找 出树支 的 子 支 和子点 若 ‘ 二 ， 顺序 检 查 〔 叮 ， 否 则 检 查 任 了 若找到 一个 。 满足 厂 且 公卜 ， 则 ， 忿 。 若 “ 则 ， ， 否则 。 若找 不到上述 。 ， 则 。 ，。 ， ，。 。 若 ’ 二 则 ’ ， 否 则 了 。 ④ 若 笋 ‘ 或三 任 厂 ， 二 ， 则 。 ， ’ “ 尹 一 ， 厂十万 ’ 川 ， 从 罗找 出一个使 厂 了 并。 的最长列 掩 ， 再找 出使 罗 幻 笋 。 ， 的 最 长行 夕 。 对于 夕 与 了的 对应 基本割集的 所有公共连支 检查乘积 厂 口 厂 是否 都相等 若否 ， 转 步 骤 若 是 ， 则 “ 厂 爪 ， ， ， 夕， 夕 ， ‘ 十 ， 调 。 停止 ， 显示 “ ‘ 不能实现 ” 。 ， ‘ · 二 一 ， 结束 。 主 算法 ， ， 、 ， ， 输人 了。 按 定义 建立 的邻接表 ， ， 调 求 出 ， 的 分 块 子 阵 ，二 ， ‘ 二 ， 对于 二 ， … ， 进行 初始化 ， 。 ， 二 ，价 ， 价 ， ，价 ， ，功 ， ，价 ， 。 ，。 ， 。 “ ， 万 ’ ， ‘产、 ‘产、、 护矛， 、少一飞 了瓜 山 了‘ 、门︺一 ， 罗，万 ‘ ， 二的 最长行 的行号 ， ， 夕 ’ 夕 ， 十了 ， ② 调 从 王 综合有向树 ， 即 产生 的 树支的方向集 和始终点 集 、 。 ⑧ 建立 ，二 的图 了 的 关联阵 二 二 ， ， ‘ 一 ， ， … ， “ 哎 落任 ， ‘ 尹 ， 二 ， ， 名 二 ‘ ‘ ， 二 ， 一 ， 、 气 建立 的 图 的关联阵 ， 〔 ， ， ‘ 〕 。 结束 。 本算法 的计算时 间主要决定于 步骤② ， 最坏情况 是 ， 。 ， 。 ， 规模最 大 ， 其 计算复杂度 为 之 ， 和 为 了的树路子阵 ，，的 行数和列数 限于篇 幅 ， 应用举 例从

略)。 参考文献 1 Bixby R E,Cunningham W H.Mathematics of Operations Research,1980, 5:321 2 Fujishige S.Journal of Computer and System Sciences,1980,21:63 3 Meyeda,W.IRE Trans,Circuit Theory,1963,10:133 4 Porxo B,Ku6cpHer,1986,1:39. 5黄汝激。电子科学学刊，19879,2447 6 Aho Av,et al.The Design and Analysis of Computer Algorithms,Addi- son-Wesley Publishing Company,1976 7陈树柏，左铠，张良震。网络图论及其应用，北京：科学出版社，1982：第9章 193

略 。 参 ， 住 。 考 文 献 ， ， 。 ， ， ， ， 。 ， ， ‘ 小 ， ， 黄饮激 电子科学学刊 ， ” ， ， 往 ， 一 ， 。 了 陈树柏 ， 左 恺 ， 张 良震 网络 图论 及其应 用 ， 北京 科学 出版社 ， 第 章 了