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