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

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

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