等参数图的最大与最小距离树对及其在电网络分析中的应用

D0I:10.13374/j.issn1001-053x.1987.02.009 北京钢铁学院学报 J.Beijing Univ.of Iron Steel Technol. Vo1.9No.21987/ 等参数图的最大与最小距离树对及 其在电网络分析中的应用 穆珍 黄汝激 (电工教研室) (电路电子教研室) 掏 要 本文推广了线图的树对及其距离的概念，提出了$参数图及其树对和树对之距 离的概念。给出了等参数图中任一树对为一吸大（或最小）距离树对的充分必翠条件 和和应的算法，讨论了等参数图巾最大与最小距离树对在电网络分析中的应用，给 出了两条图主划分算法1的对偶算法和电网络的最优调和分解算法， 关键词：电网铬，等参数网，最大（小）距离树对，调利和分解 The Maximally and Minimally Distant Tree Pairs in the Equal Parameter Graphs and Their Applications in the Electrical Network Analysis Mu Zhen Huang Ruji Abstract This paper develops the concepts of a pair of trees and their distance in a linear graph.The necessary and sufficient conditions for a maximally and minimally distant tree pair and the algorithms for finding a maximally and minimally distant tree pair are given.This paper also disccuses the applications of maximally and minimally distant tree pairs in equal parameter graphs in the electrical network 1936一03一20收稿 62

北 京 钢 铁 学 院 学 报 产 ‘ 等参数图的最大与最小距离树对及 其在电 网络分析中的应用 穆 珍 电工教研室、 黄汝激 电瑟各电子教研室 摘 要 木文推广了 线 图 的树对及其距 离的概念 ， 提出了等参数图及其树对和树对之距 离的概念 。 给出了等参数 图 中任一树对为一最大 或最小 距离树对 的充分必要条件 和 相应的算法 ， 讨论了等参数 图 中最大与最小距 离树对在 电网络 分析中的应用 ， 给 出了 网络 图 主划 分算法 的对偶算法和 电网络 的最优调和 分解算法 关键 词 电网络 ， 等参数 图 ， 最大 小 距 离树对 ， 调和分解 一 ” ‘ · 飞 一 一 收稿 DOI ：10．13374／j ．issn1001－053x．1987．02．009

analysis,and presents the dual algorithm of principal partition algithm 1 and the algrithm of optimal harmonious decomposition of electrical networks. Key words:electrical network,equal parameter graph,harmonious and decomposition,maximally(minimally)distant tree pair 引 言 日本学者Y.Kajitani于1969年引入的任一给定图中最大距离树对的概念和网络图 的主划分的概念1)，对于求大网络分裂时含有最少独立变量数自的分裂和求图G的最 优调和分解具有重要意义，而进一步推广主划分概念及方法在电网络分析中的应.用，实 现以主划分方法为基础的网络分析最优算法仍是有待解决的问题。 本文的目的在于，将任一图中一对树的概念推广至一对图，研究最大（小）距离树 对在电网络分析中的应用，给出最小距离树对的算法，主划分算法1的对偶算法和电网 络的最优调和分解算法。这些概念和算法将有利于主划分理论的研究和电网络的计算机 辅助分析。 1等参数图与最大（小）距离树对 1.1基本定义 设电网络N的伴随线图G=G(V,E),V=V(G),E=E(G)各为G的顶点 集和边集。G的顶点数、边数、连通片数，秩和零度分别记为n(G),e(G),c(G), p和μ，其中n=|VI,e=|EI,且在所有讨论中，V,E,n,e,c,P,μ的足标 与其所属图的足标一致，如E:、P:分别表示图G:的边集与秩。图G的边集E与顶点集 V的编号集各记作Num(E)={X;},Num(V)=Y},其中X,Y,(i=1, 2,…e,j=1,2…n)属于正整数域。Num(V)和Num(E)有时简记为V和E, 即E={X:},V=Y}。 定义1若图G1、G2满足e1=e2,Num(E:)=Num(E,),则称G1、G:为一 对等边数图，记作G1,G,}.,e称为它的边数。 定义2若图G、G2满足e1=e2,n1=n,,Num(E,)=Num(E:), Num(V)=Num(V2),则称G1、G,为一对等参数图，记作{G,G,G:中任一 树T1与Gz中任一树T2构成等参数图{G,G2}的一个树对{T,T2}。 定义3等参数图中任一图的边集和顶点集称为G:,G,}的边集和顶点集，任一 图的边数、顶点数、秩和零度分别称为G,G}的边数、顶点数、秩和零度。 下面用e表示G:中的r号边，即e∈G,(i=1,2,r=1,2,e)。 定义4设有等参数图{G1,G2},{T1,T,}为其任一树对，.将含于一树面不含于 另一树的树支数目称为{G1,Ga}中树对{T,T2}的距离D(T:,T2),即D(T1, T2)=|T,nT2【=1T:∩T2{。 63

， ， ， ‘ ， 乒 ， 日 生‘ 口 日本学者 于 年引人的任一给定 图 中最 大距离树对的概念和 网络 图 的主划分的概念‘ ，，， 对于求大网络分裂时含有最少独立 变量数 自的分裂和 求 图 的 最 优调 和分解具有重 要意义 ， 而进一步推广主划分概念及方法在 龟网络分析中的应用 ， 实 现 以至划分 方法 为基础 的网 络分 析最优算法 仍 是 有待解 决的 问题 。 本文 的 目的在 于 ， 将任一 图 中一对树 的概念 推广至 一对 图 ， 研究最 大 小 距离树 对在 电网 络分析 中的 应用 ， 给 出最小距离树对 的算法 ， 主划分算法 的对 偶算法 和 电网 络的最优调 和分解算法 。 一 这 些概念和算法 将 有利 于主 划分理论 的研究 和 电网络 的计算机 辅助分 析 。 等参数图与最 大 小 距离树对 基 本定义 设 电网络 的伴随线 图 二 ， ， ， 各为 的顶 点 集 和边集 。 的顶 点数 、 边 数 、 连 通 片数 ， 秩 和零度分别记为 ， ， 。 ， 和 件， 其中 ， ， 且在 所有讨论 中 ， ， ， ， ， ， ， 协的 足 标 与其 所属 图的 足 标 一 致 ， 如 、 。 分别表示 图 的边 集 与秩 。 图 的边 集 与顶 点 集 的 编号集 各 记 作 ， ， 其 中 ， ， ， ， · ‘ · ， ， … 属于正 整数域 。 和 有时简记 为 和 ， 即 笼 ， ， 二 ， 。 定义 若 图 、 满 足 ， 、 ， ， 贝称 、 为一 对等边数 图 ， 记作 ， ， 。 称 为它的 边 数 。 定义 若 图 、 满 足 ， ， ， 梦 ， ， 则称 、 为一 对等参 数 图 ， 记作 魂 ， 中任一 树 ，与 中任一树 构 成等参数 图 ， 的 一个树 对 ，， 卜 。 定义 等参 数图 中任一 图的边 集和 顶 点集称 为通 ，， 的边 集 和 顶 点 集 ， 任一 图的边 数 、 顶点数 、 秩和零度分别称为 ，， 的边 数 ， 顶 点数 、 秩 和零 度 。 下 面用 ‘ 尝’ 表示 中的 号边 ， 即 ‘ ’ 〔 ， ， ， ， ， … 。 定义 设 有等参数图 ，， ， ， 为其任 一树对 ， 、 将含 于一树而 不含 于 另一树 的树 支 数 目称 为 笼 ， 。 中树对笼 ，， ， 的 距离 ，， ， 即 ， 二 、 门丁 三 ’ 了 、

定义5设{T1,T:}为{G1,G2}的任一树对，边e1(j=1,2,e)属于E。若 e;∈T,∩T,称e;为{T,T}关于T的非公共树支；若e∈T,∩T2;称e;为{T, T}关于T1的非公共连支；若e,∈T:∩T,称e1为{T1,Tz}的公共树支；若e;∈T: 门T,称e;为{T,Tz}的公共连支。 若令Ebb,E:c,E,E:（i=1,2),分别为{T,T2}的公共树支集， 公共连支集，关于T:的非公共树支集，关于T:的非公共连支集，可以证明： D(T,T2)=1E1=IE|(i=1,2),所以，D(T1,T2)≤min (P,μ)。 .1.2·最大距离树对.· 定”设{T,T:}为G,G2}的某一树对，若对于任一树对{T,T2,均 有D(T,.T2)≤D(T:,T:),则称{T,T:为{G,G:}的一个最大距离树 对。 定义7设{T:,T2}为{G1,G:}的任一树对，Ecc,Ebb分别为{T1,T2}的公共 连支集与公共树支集。若对e,∈E:,在{G1,G:中存在极小的等边数子图对{ML1, MLz}e,满足a.e:'∈MLi,e'∈ML2;b.T,∩ML1,T2∩ML2分别为ML1、 ML2的树；c,{ML1,ML2},不含{T1,T2}的公共树支，则称这样的子图对为G, G:}关于公共连支e.的一个ML一子图对。 若对e:∈Ebb,.在G1,Gz}中存在极小的等边数子图对{MC1,MC,}。,满足a. e∈MC,e∈MC2;b.T,∩MC1,Tz∩MC:分别为MC1、MC的树；c. {MC1,MC2}。不含{T,T2}的公共连支，则称这样的子图对为{G1,G:}关于公共树 支e.的一个MC一子图对。 定理1{G1,G2}中树对{T1,T2}是最大距离树对，当且仅当对于{T1,T}的 每条公共连支都存在对应的ML一子图对。 定理2{G1,.G2}中树对{T:,T}是最大距离树对，当且仅当对于T1,:T2}的 每条公共树支都存在对应的MC一子图对。 1.3最小距离树对及其算法 定义8设{T:,T:}为G,G2}的某一树对，若对任一树对{T1,T2},均有 D(T,T2)≥D(T:,T:),则称{T:,T:}为G,G2}的一个最小距离树 对。 定义9设{T1,T}为{G1,G2}的任一树对，Eb(i=1,2)为{T,T2}关 于T:的非公共树支集。若对eaEEab,在{G,G2}中存在极小的等边数子图对{MC, ML},满足(1)e∈MC,e日∈ML;（2)Tc=T:∩MC,T2L=Tz∩ML 分别为MC,ML中的树；(3)ML中关于T2的金部基本回路不含非公共树支，MC 中关于T:的金部基本割集不含非公共连支，则称这祥的子图对为{G,G2}关于非公 共树支e:的一个MCL一子图对。 图1所示的等参数图{G,G},边数e=9,顶点数1=6。任一树对{T1,T2} 为：Ti={e,e2,e4,e,e8,T2={e2,e4,e6,e8,eg},则Ebb={e2,e,e6, e8},Eee={e,e,e7,E={e},E={eg},D(T,T:)=1。边集 64

’ 定义 设 工， 卜为 ，， 的 任一树 对 ， 边 。 不 ， ， ” · 属 于 。 若 任 ， 丁 ， 称 为 ，， 关 于 ，的非 公共树 支 若 〔 币 ， ， 称 。 为 ，， 关 于 ，的非 公共连 支 若 〔 工 门了 ， 称 为 ， 的 公共 树 支 若 〔 了 门了 ， 称 为 谧 ，， 的 公共连 支 。 若令 ， ， 胃 ， 钾 ， ， 分别 为 ， 的 公共 树 支 集 ， 公共连 支集 ， 关 于 的 非 公共树 支集 ， 关 于 的非 公共连 支集 ， 可 以证 明 ，， ‘广 二 毛宫 ， ， 所 以 ， ， ， 卜 。 · 「 七 最天距离树对 一 定了 一 设 ， 梦 为 工， 的 某一树对 ， 若对 于 ， 任 一树 对 笼 ，， ， 均 有 ，， 一 簇 全 ， 雪 ， 则称 广 ， 一 穿 为 ，， 的一个 最 大距 离树 对 。 定义 设 ， 为 ，， 。 的 任一树对 ， 。 ， 分 别为 ，， 的 公 共 连 支集与 公共树 支集 。 若 对 〔 。 。 ， 在 、 ， 中存在极小的 等边 数子 图 对 ，， ‘ ， 满 足 ‘ 尝 ’ 〔 ，， ‘ 爹 ’ 〔 ， ，， 。 分别为 ，、 的树 笼 ， 不含 笼 ，， 的 公共树支 ， 则称这 样的 子 图对为 ，， 关 于 公共连 支 的 一个 一子 图对 。 若 对 。 任 ， 在 ，， 中存在 极小 的 等边数子 图对 ，， 。 。 ， 满 足 ‘ ’ 任 工， 代 ’ 〔 门 ，， 门 分 别 为 工、 人 的 树 ，， 。 不含 ， 的 公共连 支 ， 则称 这 样 的 子 图对为 笼 ，， 关 于公 共树 支 的 一个 一子 图对 定理 ，， 中树 对 ， 是最 大 距 离树 对 ， 当且仅 当 对 于 ，， 的 每条公共连 支都存在对 应的 一子 图对 。 定理 ，， 、 中树 对 ，， 是最 大 距离树 对 ， 当且仅 当对 于 ，， ， 的 每条公共树 支都存在 对应的 一子 图对 。 最小距 离 树对及其算法 定义 设 ， 穿 为 工， 的某 一树 对 ， 若 对 任 一树 对 ，， ， 均 有 ， 》 犷 ， 犷 ， 则称 犷 ， 犷 为 ， 的一 个最 小 距 离 树 对 。 定义 设 ，， 、 为 ， 的 任 一树 对 ， 毛咨 ， 为 ，， 关 于 的非 公共树 支 集 。 若对 。 任 。 ， 在 ，， 中存在 极 小的 等边 数 子 图对 ， ， 满 足 。 ‘二 ’ 〔 ， 昭 ’ 〔 。 ， 门 ， 。 门 分别为 ， 中的树 中关 于 雨勺全部基 本回路 不含非 公共树 支 ， 中关 于 。 的 全部基 本割 集不含非 公共连 支 ， 则称 这 样的 子 图对为 ，， 关 于 非 公 共树 支 的 一个 一 子 图对 。 图 所示 的 等参 数 图诬 ，， ， 边 数 ， 顶 点数 。 任 一树 对 ，， 为 汪 ’ ，， ， ， 。 ， 。 ， 。 ， ， 。 ， ， ， 则 笼 ， ‘ ， ， ， 。 。 笼 ， ， ， 与 ， ， 几 ， 丁 ， 。 边 集

{e1,e2,ea,e4,cs}在{Gi,G:}中构成关于e的MCL一子图对。 图1 定理3{G,G中树对{T,T}为一最小距离树对，当且仪为T,T2}关于 T:(T2)的全部非公共树支都存在其相应的MCL一子图对。 最小距离树对算法 回求出任一树对{T,T},T1→T1,T2→T2,Ee→EC,Ebb→EB,E4B→ ED,转到①。 :①从ED中取一边e,∈T1,若ED=中，结束；否则e-→C,k=1,·转到②。 ②找出C中各边关于T2的基本回路之并集L,若L中含非公共树支e?,(T2- c)'Ue)→T2,k=k-1,当k≤1时，L=中，C=中，返回①，否则转到④：若 L中不含非公共树支，转到③。 ③找出L中各边关于T1的基本割集之并集后送入C,若其中由边e:产生的基本割 集中含非公共连支e”,则当e=e时，（T1-e)Ue→T1,L=,C= 本，返回①，否则转到⑤。若C中不含非公共连支，找出C中各边关于T2的基本回路之 并集LC,当LC=L,令L=中，C=中，返回①；当LC≠L,LC→L,k=k+1,返 回②。 ④按此时k值，从EB中找出产生e:’所属的基本割集的树支e:',(T1-e:)U e-+T1,转到⑤。 ⑤按此时k值，从EC中找出产生e‘:所属的基本回路的连支e,(T2~e‘))U e’→T2,k=k-1。若k=1,将此时新的E:c→EB,Ebb*EC,返回①。 ·在对有源网络进行拓扑分析时，电压图G,和电流图G:构成一等参数图对。G,和 G:有一棵共有树是有源网络拓扑分析有唯一解的充分必要条件。若令G1=G,G:= G,则G,与G:的一棵共有树正是{G,G:}的一个距离为零的树对T:,T:}。因 此，应用算法求出{G,G:的一个最小距离树对，当Dmn（T:,T)=0时，有 源网络拓扑分析有唯一解。 2电网络主划分算法1的对偶算法 文献〔2〕已给出了电网络主划分算法1。根据对偶原理，可导出主划分算法1的 偶算法（主划分算法2)如下（其中所用符号与文献〔2〕中完金一致）：。 ①置k=1,Tk)=T,Lk)=L,G=中，Gm=中，转到②。 ②找出L)的每个连通片L的点集V(L‘,),把T)中的对应点集融合成 65

一 ， ， 在 工， 中构 成关 于 ，的 一 子 图对 。 口 饥 定理弓 ，， 中树 对 ，， 为 一 最小 距 离树 对 ， 当且仪为 ，， ‘ 关 于 补 刃 的 全部非 公 共树 支都存在其 相 应 的 一子 图对 。 最 小距 离树 对 算法 求 出任一树对 ，， ， 、 ， 。 ， 。 。 、 ， 匕 ， 与公， ， 转到① 。 ①从 中取 一边 〔 ， 若 二 小 ， 结束 否则 ‘ ’ 一 ， 】 ， · 转到② 。 ②找 出 中各边关 于 ‘ 的基本 回路之 并集 ， 若 中含非 公共 树 支 ‘ 幕 ’ ， 、 ‘ 护 ‘ 节 ’ 、 ， 一 ， 当 《 时 ， 小 ， 小 ， 返 回① ， 否 则 转到④ 若 中不含非 公共树 支 ， 转到③ 。 ③找 出 中各 边 关 于 的基 本割 集之并集后送 入 ， 若 其 中由边 。 ‘ 吞 ’ 产生 的 基 本割 集 中含习卜公共连 支 ‘ 当 ’ ， 则 当 ‘ 吞 ’ ‘ ’ 时 · ， ’ 一 ‘ ’ ‘ ’ ， 小 ， 小 ， 返 回① ， 否 则 转到⑤ 。 若 中不 含非 公共连 支 ， 找 出 中各边 关 于 的基本 回 路 之 并集 ， 当 ， 令 小 ， 小 ， 返 回① 当 铸 ， ， ， 十 ， 返 回② 。 ④ 按此 时 值 ， 从 中找 出产生 。 ‘ ’ 所属 的基 本割 集的 树 支 。 ‘ ’ ， 一 ‘ ’ ‘ ’ ， 转到⑤ 。 ⑤按此 时 值 ， 从 中找 出产生 ‘ 圣 ’ 所属的 基 本回路 的 连 支 ‘ 圣 ’ ， 一 ‘ 若 ’ ‘ ’ 、 ’ ， 一 。 若 二 ， 将 此时新的 。 。 、 ， 、 ， 返 回① 。 ‘ 在对 有源 网 络进 行 拓 扑分 析时 ， 电压 图 ， 和 电流 图 、 构 成一 等参 数 图 对 。 ， 和 ‘ 有一棵 共有树 是有源 网络 拓 扑分 析和准一解 的充分 必要 条件 。 若 令 ， 二 ， ， 、 ， 则 与 的 一棵 共 有树正 是 诬 ， ， 、 的 一 个距 离为零 的 树 对 福 了 ， 犷 。 因 此 ， 应用 算法 求 出 ， ， 。 的 一个 最小 距 离 树 对 ， 当 梦 ， 犷 时 ， 有 源 网络拓 扑分 析有 唯一解 。 电网 络主 划分算法 的对偶算法 文献 〔 〕 已给 出了 电网络 主划分 算法 。 根据对 偶原理 ， 可导 出主划分 算法 的 偶算法 主划分 算法 如下 其 中所用 符 号与 文 献 〔 妇巾完 全一致 ①置 ， ‘ “ ’ ， ‘ ’ 二 ， 小 ， 小 ， 转到② 。 ②找 出 “ ’ 的 每 个连 通片 亡乍 ， 的 点集 ‘ 借 ’ ， 把 尹 ‘ “ ’ 中的 对应 点集 融 合 成

一点(i=1,2,…),去掉自环、悬挂边及桥，剩下的边集T’就是纯树支割集之 并集。若T)=中，则G。→G”,G-G,→Gm,G白Gm→G,G。→Gm,转到④。若 T中中，则从T中取出边集E(T))→T,T-T.→T”,转到③。 ③找出T的每个连通片T的点集V(T背)，把L,中的对应点集融合成一 点（i=1,2,…),去掉自环、悬挂边及桥，剩下的边集L就是纯连支割集之并 集。从L中取出边集E（Lk))→L,L-L→L,k+1→k,回到②。 ④从L:中去掉悬挂边和桥，剩下的边集C1对应于Gm中纯连支回路之并集。若C1= 中，则T和Gm就是G的极树和主缩减图，G-G)→G,转到⑦。若C:=中，转到⑤。 ⑤划分C1=∑C1i,C1:是C:的第i号连通片。对于每个i,比较Ci中各边的k值， 找出一个最小值1i,取出一条对应连支eci。Lm-eci→L,T,Ueci→T,转到 ⑧。 ⑥从T.中取出含ec:的（单连支）回路C2,从C:中找出一条k=1:的树支ebi。 0 在Gm中对调ebi和eci,即Tm-esiUSeci-→Tm,Lm-三eciUΣebi→Lm。同样， 在G中对调eb:和eci。若全部1：=1，Tm→T,Lm→L),Gm=中，回到②。若至 少一个1>1，Gm→G,回到④。 ⑦置k=1,G,=G,G。=中，转到⑧。 ⑧从L“’中取出除悬挂边和桥以外的子图L就是纯连支回路之并集，L’= L,L?是L的第号连通片。若L,=中，转到@。若L≠中，则从L 中取出边集E(L)→L。找出L的点集V(L),把T,中的对应点集融 合成一点(i=1,2,…),L”曰L→L,转到回。 ⑨从T’中取出除悬挂边和桥以外的子图T,就是纯树支回路之并集，T,= ΣT',T等是T的第号连通片。从T中取出边集E(T)→T。找出T的 点集V(T),把L)中的对应点集融合成一点（j=1,2,…),T⊙T’→ Tk),k+1→k,回到⑧。 ⑩置G)=G©G,则G,和G)中存放的就分别是原图G的主部分图和主导出 图。 若G不连通，可对G的各连通片逐片应用算法2。另外，求图G的主划分时，若G 较琥，宜用算法1，若G较密，宜用算法2。 3电网络最优调和分解的实现 设图G的主划分为(Gn,Gm,G。),G的一个调和分解为(G,G:),其中 G,=GaUG。,G;=GmUG。i,G。,和G。1是主导出图Go的一个调和分解。根据文献 〔2)，容易推得以下两个定理。 定理5(G,的性质)设F·为G的一个极林，G的主划分为(G,G,G。),F· 66

一 点 宜 ， ， “ · ， 去掉 自环 、 悬挂边及桥 ， 剩 下的边集 梦 ， 就是纯树 支割集 之 并集 。 若 寸 ’ 二 小 ， 则 ， ‘ ‘ 七’ ， 一 “ ‘ 。 ， ， ‘ 川 转到④ 。 若 ‘ 幻 笋 小 ， 则从 中取 出边集 产 ， ‘ ，， ， ， ‘ ‘ 幻 ， 转到③ 。 ， ③找 出 ‘ 肚’ 的每 个连通 片 ‘今 ’ 的 点集 ‘梦 ’ ， 把 ‘ ’ 中的 对应点集融 合 成一 点 ， ， ” · ， 去 掉 自环 、 悬挂边及桥 ， 剩 下的边集 啥 ’ 就是纯连 支割集之 并 集 。 从 中取 出边集 毕 ’ ‘ 。 ， 一 。 ‘ ‘ “ ’ ， 十 、 ， 回 到② 。 ④从 ， 中去 掉悬挂边和桥 ， 剩 下的边集 对应于 中纯连 支回路之并集 。 若 小 ， 则 和 二就是 的极树和主缩减图 ， 一 ‘ “ ’ ， ， 转到⑦ 。 若 ， 小 ， 转到⑤ 。 ⑤划分 艺 ， 是 的 第 号连 通 片 。 对于每 个 ， 比较 ， ，扣各边 的 值 ， 找 出一个最小值 ， 取 出一条对应连 支 。 ‘ 。 一 艺 “ ， 夸 · ‘ ，， 转 到 ⑥ 。 ⑥从 ， 中取 出含 。 的 单连 支 回路 ， 从 中找 出一条 的 树 支 ， 。 在 。 中对调 、 和 。 ，， 即 一 艺 。 乏 。 ， 一 乏 。 ‘ 艺 ‘ 口 。 同 样 ， 在 中对调 和 。 。 若全部 ， ‘ “ ’ ， ‘ ‘ “ ’ ， 一 小 ， 回 到② 。 若至 少一个 万 ， ， 、 回 到④ 。 ⑦置 ， ‘ “ ， ， ， 二 小 ， 转到⑧ 。 ⑧从 ‘ “ ’ 中取 出除悬挂边 和桥 以外 的子 图 ‘岔 ’ 就是 纯连 支回 路 之 并 集 ， ‘合 ’ 艺 盖飞 ， ， 盖专 ’ 是 ， 的 第 号连 通 片 。 若 ， 二 小 ， 转 到 ⑩ 。 若 啥 ， 子 小 ， 则 从 中取 出边 集 奢 ’ 。 。 找 出 二、 ， 的 点集 飞 ’ ， 把 ‘ “ ’ 中的 对应 点 集 融 合 成一点 ， ， … ， ‘ “ ， 啥 ， ‘ “ ’ ， 转 到⑨ 。 ⑨从 ‘ “ ’ 中取 出除悬挂边 和桥 以外 的子 图 ‘ 匕 ’ 就是 纯树 支 回 路之 并 集 ， ’ 艺 二考 ’ ， 么乍是 啥 ’ 的 第 号连通 片 。 从 中取 出边 集 咭 ’ ” ， 。 找 出 二乍 ’ 的 点集 二 ’ ， 把 ‘ “ ’ 中的对 应 点集融 合 成一 点 ， ， 一 ， ‘ “ ， 曰 ， ’ ‘ ‘ ， ， ” ， 回到⑧ 。 ⑩置 ‘ “ ’ 二 ，， 则 ， 和 ‘ ’ 中存 放的就分别是 原 图 的主部分 图 和 主 导 出 图 。 若 不连通 ， 可对 的各连 通 片逐 片应用算法 。 另外 ， 求 图 的主划分 时 ， 若 较 疏 ， 宜 用 算法 ， 若 较密 ， 宜 用算法 。 电网络最优调 和分解的实现 设 图 的主划分为 ， ， 。 ， 的一个调 和 分 解 为 ， ， ， 其 中 ， 。 。 ， ， 。 ，， 。 ， 和 。 是主导 出图 。 的 一个调 和分 解 。 根据文献 〔 〕 、 容 易推得 以下 两个定理 。 定理 。 的 性质 设 为 的一个极林 ， 的主划分 为 。 ， 、 ， 。 ， ‘