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

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

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