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

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

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

在Ga、Gm、G。中的对应子图分别记为F:、F:、F。,L。是G。中F。的余林，则 有：(1)F。=F⊙F:-Fa,(2)F。UL。=Go,F。∩L。=中。(3)任 取eb∈F。与Gn(或Gm)相邻接，则必存在e:∈L&,与eb在相同的顶点处相邻接。 (4)任取eb∈F&,ec∈L。,则Fa Oep是G□eb的极林，L。-e:是对应G。-ec 的极林之余林。 定理6设一绝对非密一绝对非疏图G的边巢为E,任取一边eo∈E,则有：(1) G曰eo为-一密图，G-eo为一疏图。(2)G,(c0)=G⊙eo的主缩减图G:m(e。)= 中，Ge(e。)=G-e的主部分图G'cn(e。)=b。(3)G.n(e。)=G’,m(e。)U e,为G中最小含eo调和部分图；Gcm(e。)=G'cm(e。)Ueo为G中最小含e调和缩减 图，这里G'.n(e。)是G,(e。)的主部分图，G's(e。)是G。(e。)的主缩减图。 根据文献〔2〕中给出的最优调和分解原则和生成调和分解树的方法，应用主划分 算法1和主划分算法2，考虑到上两定理，可得求网络图之调和分解的算法如下。 最优调和分解算法： 第一部分用士划分算法1（或算法2）求出图G的极林F·和主划分(Gn,G, G。)。 第二部分将主划分算法1和主划分算法2的后半部分（第⑦~①步）分别记作算 法1.2和算法2.2，并把G)改记作GK,G,和G.改记作GV。 ①若G0=中，输出G,=Gn,G:=Gm后结束，否则求出Gn、Gm在未进行GOGm 运算前的连通片，Gn=UGnr,Gm=UGm,转到②。 ②由Go=G⊙Gn-Gm,求出G,及其各连通片，G。=UG。1,转到③。 ③任取一未经处理的G。1（j=1,2,.…),若这样的G。;不存在，则输出G,、 G:后结束；否则G。;→GP,G的第0行各元素赋初值，转到④。 ④找出与G。,相邻的未检查过的Gn,(p=1,2,…),若这样的Gm,不存在， 转到⑦；否则给Gnp加上已检查标志，从G。1中找出一条邻接Gn的连支EJN,转到⑤。 如果找不到，返回④。 ⑤用算法1·2求出最小含EjN调和缩减图G。icm→GV,G。icm→GP。若GP=中， 转到@；否则在GP中找出一条与TV相邻的树支边EJM,转到⑥。 ⑥用算法22求出最小含EJM调和部分图G。i:n-→GV,G。:n→GP。若GP=中， 转到⑩，否则在GP中找出一条与TV相邻的连支边EJN,返回⑤。 ⑦找出与G。;相邻的未检查过的Gm(q=1,2,…),若这样的G不存在，转 到①；否则给Gm,加上已检查标志，从G。;中找出一条邻接Gm,的树支边EJM,转到 ⑧。如果找不到，·返回⑦。 ⑧用算法22求出最小含EJM调和部分图G。i:n→GV,G。1:m→GP。若GP=中， 转到⑩；否则在GP中找出一条与TV相邻的连支边EJN,转到⑨。 .⑨用算法1·2求出最小含EJN调和缩减阁G。1cm→GV,G。jcm→GP。若GP=中， 转到①；否则在GP中找出一条与TV相邻接的树支边EJM,返回⑧。 67

在 。 、 、 。 中的 对应子 图分别记 为 井 、 言 、 矛 ， 才 是 。 中 才 的 余 林 ， 则 有 咨 一 斋 ， 岔 矛 二 。 ， 矛 言 小 。 任 取 、 〔 才 与 。 或 相邻 接 ， 则 必存在 。 〔 岔 ， 与 在 相 同的 顶 点处相 邻 接 。 任取 任 岔 ， 。 〔 言 ， 则 尝 是 。 的 极林 ， 岔 一 。 是 对应 。 一 。 的极林之 余林 。 定理 设 一 绝对非 密一 绝对非 疏 图 的边 集为 ， 任 取 一边 。 〔 ， 则 有 。 为一密 图 ， 一 为一疏 图 。 。 。 的 主缩 减 图 二 。 。 小 。 。 一 。 的 主部分 图 ， 。 。 。 卜 。 。 。 二 ， ，， 。 。 为 中最小含 。 调 和部分 图 。 二 ’ 。 。 。 为 中最小含 。 调 和缩 减 图 ， 这 里 ’ ‘ 。 。 是 。 。 的 主部分 图 ， ’ 。 ， 。 是 。 。 。 的 主缩 减 图 。 根据文献 〔 〕 中给 出的 最优调 和 分解 原则 和生 成调 和分解树 的方法 ， 应用 主划分 算法 和 主划 分 算法 ， 考虑到 上两定理 ， 可 得 求网 络 图之调 和分 解 的算法 如不 。 最 优调 和 分 解算法 第一部 分 用 主划 分 算法 或 算法 求 出图 的极林 ’ 和 主 划 分 ， 。 。 。 第二部 分 将主划 分算法 和 主 划 分算法 的后 半部分 第⑦ ⑩步 分 别记 作算 法 和 算法 ， 并把 ‘ “ ’ 改记 作 ， ， 和 。 改记 作 。 ①若 。 小 ， 输 出 ， 二 ， 二 后 结束 否则 求 出 、 在 未 进 行 运算前 的连 通 片 ， 。 ， 。 二 ， 转 到② 。 气 ②由 。 。 一 ， 求 出 。 及其 各连 通 片 ， 。 。 ， 转 到③ 。 ③任取 一未经处理 的 。 ， ， 一 ， 若这 样 的 。 不存在 ， 则输 出 ， 、 后 结束 否则 。 、 ， 的 第 。 行各元素赋初值 ， 转到④ 。 ④ 找 出与 。 相邻 的未检查 过 的 ， ， ， ， ” · ， 若这 样的 、 ， 不 存 在 ， 转到⑦ ， 否则给 。 ， 加 上 已 检 查标 志 ， 从 。 中找 出一条邻 接 、 ， 的连 支 ， 转到⑤ 。 如果找不 到 ， 返 回④ 。 ⑤用 算法 · 求 出最 小含 调 和 缩减 图 。 、 。 、 ， 。 。 。 、 。 若 小 ， 转到⑩， 否则在 中找 出一条与 相邻 的树 支边 ， 转到⑥ 。 ⑥用算法 · 求 出最 小含 调 和部 分 图 。 ， 。 。 。 。 、 。 若 小 ， 转到⑩ 否则 在 中找 出一条与 相 邻 的连 支边 ， 返 回⑤ 。 ⑦找 出与 。 相邻 的未 检查过 的 ， ， … ， 若达 样的 ， 不 存 在 ， 转 到 否 则给 、 加 上 已检 查标 志 ， 从 。 中找 出一条邻 接 。 ， 的 树 支 边 ， 转 到 ⑧ 。 如 果找不到 ， 返 回⑦ 。 ⑧ 用算法 · 求 出最 小含 调 和部 分 图 。 。 、 ， 。 ， 。 若 小 ， 转 到⑩ 否 则 在 中找 出一 条与 相 邻 的连 支边 ， 转到⑨ 。 · ⑨用算法 · 求 出最 小含 调 和 缩 减 图 。 。 ， 。 ，。 。 若 小 ， 转到⑩ 否贝 在 中找 出一条与 相邻 接 的树 支边 ， 返 回⑧

⑩此时已得到Go,的一个调和分解，在GP中恢复G。i,求出G。;的连支数μ。；→ G(0,2),求出pi=p:→G(0,3),其中p:(t=1,2,)为G;属 于G,的第t号连通片的秩，消去G.p,Gma(P、q=1,2,…)的已检查标志。当Σp:+ μ。；>G(0,0)(G(0,0)中存前面各次分解中最小的运算时间)，删去本次 分解，返回④。当∑p:+μG(0,1),按第二种情况 处理。 ①此时已得到G。1全部可能的谁最优调和分解，并检查比较完毕。G的第0列存着 .对应于G。的最优（或准最优）调和分解，给G。加上已处理标志，G。1,G,G。j:→ G:,G的第0列清零，G(0,0),G(0,1)置最大值，返回③。 4结 论 试验结果表明，在对一网络进行分析时，若采用由最优调和分解算法确定的混合变 量，其运算时间大约是割集分析运算时间的1/4，`是选任一组混合分析变量的混合分析 运算时间的1/3~1/6。因此，主划分算法1、主划分算法2和最优调和分解算法以及实 现对网络计算机辅助分析的优化具有很大的实际意义。· 参考文献 1 )Ohstuki,T.,Isigaki,Y.,Watanabe,H.:IEEE Trans,CT-17, 1970,p.491. 〔2〕黄汝激：电子学报，3(1985)。 8 )Kishi,G.,Kajitani,Y.:IEEE Trans.Circuit Theory,CT-16,. 1969,p.323。 〔4〕1984年南京暑期讲习班（宽带匹配网络理论与网络图论专题）一第四卷，南 京邮电学院。 68

⑩此时已得到 今属 。 ，的一个调 和分解 ， ， ， 求 出 。 艺 了 ‘ 。 在 中恢 复 。 ，， 求 出 。 ， 的 连 支 数林 。 ， ， 其 中 ， ， · ‘ · 为 。 于 ， 的第 号连通 片 的秩 ， 消去 ， ， ， 。 、 ， 一 的已检查标 志 。 当艺 兮 心 ， ， 中存前面各 次分解中最 小 的运 算时 间 ， 删 去 本 次 分 解 ， 返 回④ 。 当万 亨 。 卜忿 ， ， 将艺 。 件言，” ， ， 卜 ‘ ， ， 本次分 解送 入 的第 。 列保存起来 ， 返 回④ 。 当艺 考 心 二 ， ， 若 拼 。 ， 簇 ， 按第一 种情况处理 若卜 。 ， ， 按第二 种情况 处理 。 ⑧此时 已得到 。 全部可 能 的准最 优调 和分解 ， 并 检 查 比较完毕 。 的第 列存着 一 对应 于 。 的最优 或准 最优 调 和分 解 ， 给 。 加上 已处理标 志 ， 。 ，， ” ， ， 。 ， 的第 列清零 ， ， ， ， 置 最大值 ， 返 回③ 。 结 论 试 验结果表 明 ， 在对 一 网络进行分 析时 ， 若采用 由最优调 和分解算法 确定 的混 合 变 量 ， 其运 算时 间大约 是割 集分 析运 算 时 间的 ，’ 是选任 一组 混 合分 析变量 的混 合分 析 运算时 间的 邝 一 。 因此 ， 主划分算法 、 主划分算法 和最优调 和分解算法 以及实 现对 网络计算机辅 助分 析的优化具有很 大 的实 际意义 。 参 考 文 献 〔 〕 ， ， ， ， ， 一 ， ， ‘ 〔 〕 黄 汝激 电子学报 ， 。 〔 〕 ， ， ， 几 ， 一 ， ， 。 。 〔 〕 年南京暑 期讲习班 宽带匹配 网络理论 与网络 图论 专题 一第四 卷 ， 南 京 邮 电学 院