第二章图论基础

1、图是指某类图是指某类具体事物和这些事物间联系的抽象具体事物和这些事物间联系的抽象描述描述。可可由一个点的集合和线段的集合构成。这些由一个点的集合和线段的集合构成。这些点称为点称为顶点或节点顶点或节点，线段称为边或，线段称为边或分支分支。2.1 图的基本概念图的基本概念 定义定义2-1 一一个图个图G定义为一个偶对定义为一个偶对(V，E)，记，记作作G(V，E)，其中：，其中： V是图是图G的节点的集合。的节点的集合。m=是节点数。是节点数。 E是图是图G的边的集合。的边的集合。n是图是图G的边数。的边数。 若偶对若偶对(V，E)是有序的，即由点和有向边组是有序的，即由点和有向边组成的图，称为成

2、的图，称为有向图有向图；若偶对；若偶对(V，E)是无序的，是无序的，称为称为无向图无向图；既含有向边，又含无向边的图称为；既含有向边，又含无向边的图称为混合图混合图。2.1 图的基本概念图的基本概念v4v1v5v2v3e1e2e3e4e7e5e6 图图G1是是(5，7)图。图图。图G1的边所的边所联接的两节点所构成的偶对是联接的两节点所构成的偶对是无序无序的的，它们是，它们是e1=,e2=,e3=,e4=,e5=,e6=,e7=。2.1 图的基本概念图的基本概念 图图G2，G3是有向图。图解中用带箭头的线段表是有向图。图解中用带箭头的线段表示有向边，箭头从始点指向终点，始终点为有序偶示有向边，

3、箭头从始点指向终点，始终点为有序偶对。为区别起见，一般用圆括号表示有序偶对，用对。为区别起见，一般用圆括号表示有序偶对，用尖括号表示无序偶对。尖括号表示无序偶对。112,ev v223,ev v如图如图G2中边中边e1v5v1v2v3v6v4e2e3e4e5e6e7e8e9v1v2v3v4e1e2e3e4e5e6联接同一条分支的两点称为联接同一条分支的两点称为邻接点邻接点，有共同节，有共同节点的两边称为点的两边称为邻接边邻接边。即一条边与它的节点。即一条边与它的节点关联关联。就是说，关联反映点、边间的联接关系，而邻接则就是说，关联反映点、边间的联接关系，而邻接则反映节点间或分支间的联接关系。反

4、映节点间或分支间的联接关系。2.1 图的基本概念图的基本概念 在有向图中，连接两个相同节点、方向也相同的分支称在有向图中，连接两个相同节点、方向也相同的分支称为平行边，即为平行边，即重边重边。始终点重合的分支构成始终点重合的分支构成圈圈。没有圈又不。没有圈又不含平行边的图称为含平行边的图称为简单图简单图。两节点间有平行边的图称为。两节点间有平行边的图称为多重多重图图。连按两个相同节点的重边数叫做边的。连按两个相同节点的重边数叫做边的重数重数。v1v2v3v4e1e2e3e4e5e6v4v1v5v2v3e1e2e3e4e7e5e6e1v5v1v2v3v6v4e2e3e4e5e6e7e8e92.1

5、 图的基本概念图的基本概念v1v2v3v4e1e2e3e4e5e6v4v1v5v2v3e1e2e3e4e7e5e6e1v5v1v2v3v6v4e2e3e4e5e6e7e8e9图中节点的个数称为图中节点的个数称为图的阶图的阶，用，用nv表示。每一对不表示。每一对不同节点间均有一条边相连的简单图称为同节点间均有一条边相连的简单图称为完全图完全图，图，图G2就是一个就是一个4阶的完全图。阶的完全图。m阶完全图的边数等于阶完全图的边数等于m(m-1)/2。 图中与节点图中与节点vi关联的边的条数关联的边的条数称为称为vi点的线度，记作点的线度，记作d(vi)。对有向图，进入节点的为负线度，离开节点的。

6、对有向图，进入节点的为负线度，离开节点的为正线度。显然，任一图为正线度。显然，任一图G中各节点的线度之和等于中各节点的线度之和等于其边数的其边数的2倍。倍。同一个图的图解又可有不同的画法，但只要它同一个图的图解又可有不同的画法，但只要它们们“同构同构”，均表示同一个图。，均表示同一个图。2.1 图的基本概念图的基本概念 同构的图被认为是等价的同构的图被认为是等价的。因此，在研究通风。因此，在研究通风问题时，只要保持同构，即可根据需要和方便，把问题时，只要保持同构，即可根据需要和方便，把通风系统图绘成简明清晰的通风网络图。通风系统图绘成简明清晰的通风网络图。 2.1 图的基本概念图的基本概念图中

7、，图中，b、c均是图均是图a的真子图，的真子图，c是图是图a的一个生成子图。的一个生成子图。在实际工程问题中，用只反映点边关系的图来在实际工程问题中，用只反映点边关系的图来揭示具体事物量值关系时，必须先给元素揭示具体事物量值关系时，必须先给元素(点或边点或边)赋权。权的具体内容，可根据实际需要确定。在通赋权。权的具体内容，可根据实际需要确定。在通风网络中，常用风网络中，常用通风参数作权的指标，如风阻、风通风参数作权的指标，如风阻、风量、风压等。量、风压等。2.1 图的基本概念图的基本概念 赋权图：赋权图：一个图一个图G(V，E)与定义在与定义在E或或V上的上的权或权函数，称为一个网络或赋权图，

8、亦称有权图。权或权函数，称为一个网络或赋权图，亦称有权图。网络的图解中，赋权通过在图的分支网络的图解中，赋权通过在图的分支(或节点或节点)旁注旁注明权函数的值来表示。明权函数的值来表示。链链：对于图对于图G的的p个边个边e1,e2,ep，如果有，如果有p1个顶点序列个顶点序列v0,v1,vp，且边，且边ei与与vi-1、vi关联关联(j1，2，p)，则这些边构成的序列称为，则这些边构成的序列称为链链，用，用u表示。表示。2.1 图的基本概念图的基本概念 不含重复边的链称为简单链。没有重复顶点的链不含重复边的链称为简单链。没有重复顶点的链称为基本链。基本链肯定是简单链，但简单链不一称为基本链。基

9、本链肯定是简单链，但简单链不一定是基本链。定是基本链。 图中，图中，v4e3v5e4v3e8v4e2v2e7v3是是条条链，也是一条简单链，但不是基本链；链，也是一条简单链，但不是基本链；v5e4v3e6v2e7v3e8v4e3v5是一条闭链。是一条闭链。 v1v2v3v4v5e1e2e3e4e5e6e7e8一条不闭合的简单链称为路一条不闭合的简单链称为路，记作，记作L。对有向图，若。对有向图，若一一条路中所有边的方向均一致，则称为道路条路中所有边的方向均一致，则称为道路，或称通路。，或称通路。不含重复节点的道路称为基本道路。不含重复节点的道路称为基本道路。2.1 图的基本概念图的基本概念图中

10、，图中，v1至至v3间的基本道路有间的基本道路有v1e5v3、v1e1v2e6v3、v1 e1v2e7v3、v1e1v2e2v4e8v3、v1e1v2e2v4e3v5e4v2等等五条。五条。 赋权图赋权图G中，两节点间每中，两节点间每条道路内各边的权条道路内各边的权之和称为道路的权之和称为道路的权。所有道路中，权最大。所有道路中，权最大者，称为最长路；权最小者称为最短路。者，称为最长路；权最小者称为最短路。v1v2v3v4v5e1e2e3e4e5e6e7e8回路回路:始点和终点重合的基本链称为回路始点和终点重合的基本链称为回路。图中。图中e1e5e6、e1e2e3e4e5、e6e7等均是一个等

11、均是一个。2.1 图的基本概念图的基本概念图的连通性图的连通性:图图G(V，E)中，若任意两节点间至少存中，若任意两节点间至少存在一条路，则称图在一条路，则称图G为连通图。在有向图为连通图。在有向图G中，若任意两节中，若任意两节点点(vi,vj)间至少存在着从间至少存在着从vi到到vj的一条道路，称此图为的一条道路，称此图为单向连单向连通图通图；若从；若从vi到到vj和从和从vj到到vi均至少有一条道路，则称均至少有一条道路，则称该图该图为强连通图为强连通图。 v1v2v3v4v5e1e2e3e4e5e6e7e8平面图平面图：如能把图：如能把图G画在平面上，使其各边为简单曲画在平面上，使其各边

12、为简单曲线，且除节点外任意两边均不相交，则称线，且除节点外任意两边均不相交，则称G为平面图。为平面图。 网孔：网孔：平面图平面图G中有许多自然网眼中有许多自然网眼(边包围的一个区域边包围的一个区域)，其内部既不含图的节点，也不含图的边，这样的自然网眼其内部既不含图的节点，也不含图的边，这样的自然网眼称为图称为图G的网孔，亦称为面，记作的网孔，亦称为面，记作f。网孔的边界就是包围。网孔的边界就是包围它的诸边所构成的回路。它的诸边所构成的回路。2.1 图的基本概念图的基本概念2fmn1Cnm欧拉公式：欧拉公式：一个连通的平面图为一个连通的平面图为(m,n)图图，假定图，假定图G的外部无限区域构成的

13、无限范围也算作一个的外部无限区域构成的无限范围也算作一个网孔，则网孔，则就是著名的欧拉公式。如果不计外部面，则连就是著名的欧拉公式。如果不计外部面，则连通平面团的内部回路数为：通平面团的内部回路数为： 不含回路的连通图不含回路的连通图，称为树，记作，称为树，记作T。组成树。组成树的边称为树枝的边称为树枝 。2.1 图的基本概念图的基本概念设设T是有是有m个节点的图，下述每条均可描述树：个节点的图，下述每条均可描述树：(1) T连通且无回路；连通且无回路；(2) T连通且有连通且有m-1条边；条边；(3) T的每一对节点间有唯一的的每一对节点间有唯一的条路；条路；(4) T无回路，但无回路，但T

14、中加上一条边恰有一个回路；中加上一条边恰有一个回路；ABCDEF生成树：生成树：如果如果T是图是图G的一个的一个生成子图且又是一棵树生成子图且又是一棵树时，时，则称则称T是是G的一棵生成树。一个图的生成树不是唯一的。任的一棵生成树。一个图的生成树不是唯一的。任何连通图均有生成树。生成树是连通一个图的全部节点的何连通图均有生成树。生成树是连通一个图的全部节点的极小边集合。极小边集合。 2.1 图的基本概念图的基本概念 余树：余树：图图G中去掉生成树中去掉生成树T后，剩下的边构成的子图，后，剩下的边构成的子图，称为余树称为余树(或称连枝或称连枝)。余树含的边称为余树弦或余树边。可。余树含的边称为余

15、树弦或余树边。可以看出，余树既可含回路，也可不连通。以看出，余树既可含回路，也可不连通。 连通图的树枝数与余树弦数之和等于边数。一个连通图的树枝数与余树弦数之和等于边数。一个(m,n)图的图的余树弦数为余树弦数为n-m+1。 设设T是连通图是连通图G的一棵生成树，由一条的一棵生成树，由一条余树弦和余树弦和T的树的树枝构成的回路枝构成的回路，称为图，称为图G关于生成树关于生成树T的基本回路。由的基本回路。由n-m+1条余树弦形成的条余树弦形成的n-m+1个基本回路，称为关于树个基本回路，称为关于树T的基的基本回路组。基本回路是线性无关的，亦称独立回路。本回路组。基本回路是线性无关的，亦称独立回路

16、。 2.1 图的基本概念图的基本概念 图的生成树不是唯一的，因而一个图的基本回路组也图的生成树不是唯一的，因而一个图的基本回路组也不是唯一的。不是唯一的。 对有向图，可给基本回路定义一个正方向。通常由对有向图，可给基本回路定义一个正方向。通常由余余树弦的方向作为回路的正方向树弦的方向作为回路的正方向。回路内其他边的方向，凡。回路内其他边的方向，凡与余树弦相同者为正，反之为负。与余树弦相同者为正，反之为负。abcdegf2.1 图的基本概念图的基本概念图中，取图中，取T=(a, b, d, f)，G关于关于T的基本的基本回路组回路组是是C1(a, b,c)，C2(a,b,d,e)，C3(a,b,

17、d,f,g)，可以看出，基本，可以看出，基本回路回路组是线性无关的。组是线性无关的。赋权图中，一棵生成树所有树枝上权的总和称为生成赋权图中，一棵生成树所有树枝上权的总和称为生成树的权。图树的权。图G的所有生成树中权最小者，称为的所有生成树中权最小者，称为最小树最小树，记作，记作Tmin；图；图G的所有生成树中权最大者，称为的所有生成树中权最大者，称为最大生成树最大生成树，记，记作作Tmax。2.1 图的基本概念图的基本概念割集割集S是连通图是连通图G的一个边的集合，把的一个边的集合，把S从从G中移去，将中移去，将使图使图G成为分离的两部分，但如少移去成为分离的两部分，但如少移去S中的一条边，则

18、图中的一条边，则图G仍是连通的仍是连通的。2.1 图的基本概念图的基本概念 常用常用虚线画出的闭合面虚线画出的闭合面表示割集。被每个虚线面切割表示割集。被每个虚线面切割的边组成一个割集，如的边组成一个割集，如S1=a, c, e, g，S2=b, c, e, g等。等。割集是图割集是图G所含边的一种最小集合。即所含边的一种最小集合。即只要少移去其中只要少移去其中一条边，图一条边，图G仍将是连通的仍将是连通的；另外，如果移去某些边后，使；另外，如果移去某些边后，使图分成两个以上部分，此边集也不是割集。图分成两个以上部分，此边集也不是割集。对有向图，若给割集定义一个方向，则称为有向割集。对有向图，

19、若给割集定义一个方向，则称为有向割集。以表示割集的虚线面为界，可把从割集由内向外穿出的方以表示割集的虚线面为界，可把从割集由内向外穿出的方向定为割集的正方向，也可把从割集由外向内穿入的方向向定为割集的正方向，也可把从割集由外向内穿入的方向定为正方向。定为正方向。2.1 图的基本概念图的基本概念与割集方向相同的边，称为正向边；反之，称为负向与割集方向相同的边，称为正向边；反之，称为负向边。边。一个连通图的生成树是连通这个图的全部节点的边数一个连通图的生成树是连通这个图的全部节点的边数最少的集合，而割集则是分割最少的集合，而割集则是分割个图的节点为不相连的二个图的节点为不相连的二个节点子集的边数最

20、少的集合，因此，一个图的生成树与个节点子集的边数最少的集合，因此，一个图的生成树与割集间存在着一定的联系。割集间存在着一定的联系。2.1 图的基本概念图的基本概念定理定理 连通图连通图G的一个割集的一个割集S至少包含图至少包含图G的生成树的的生成树的一条树枝。一条树枝。因为单纯余树弦是不能将图因为单纯余树弦是不能将图G分成两部分的。分成两部分的。设设S是图是图G(m，n)的一个割集，的一个割集，T是是G的一棵生成树，的一棵生成树，如果如果S中恰好含有中恰好含有T的一个树枝的一个树枝，则称，则称S为为G的关于生成树的关于生成树T的基本割集，记作的基本割集，记作Sf。因。因T有有m-1条树枝，可确

21、定条树枝，可确定m-1个基个基本割集。这本割集。这m-1个基本割集称为图个基本割集称为图G的生成树的生成树T的一个基本的一个基本割集组。割集组。 2.1 图的基本概念图的基本概念图中，取图中，取T=(a, b, d, f)，G关于关于T的基本割集组是的基本割集组是S1(a, c, e, g)，S2(b, c, e, g)，S3(d, e, g)，S4(f, g)，可以看出，基本割集组是线性无关的。可以看出，基本割集组是线性无关的。abcdegf一个图非常直观，但是不容易计算，特别不容易在计一个图非常直观，但是不容易计算，特别不容易在计算机上进行计算，一个有效的解决办法是将算机上进行计算，一个有

22、效的解决办法是将图表示成矩阵图表示成矩阵形式形式，通常采用的矩阵是邻接矩阵、，通常采用的矩阵是邻接矩阵、关联矩阵关联矩阵、回路矩阵回路矩阵和割集矩阵和割集矩阵。2.2 图的矩阵表示图的矩阵表示2.2 图的矩阵表示图的矩阵表示例如，图中对节点排列顺序为例如，图中对节点排列顺序为 v1,v2,v3,v4，有邻接矩阵，有邻接矩阵v1v4v2v3e1e2e3e4e5123412340110001100010000vvvvvAvvv 简单有向图的节点邻接矩阵是对角元素为零的不对称简单有向图的节点邻接矩阵是对角元素为零的不对称方阵。其总非零元素数目表示图的分支数；某行非零元素方阵。其总非零元素数目表示图的

23、分支数；某行非零元素数目表示从该行对应节点流出的分支数；某列非零元素数数目表示从该行对应节点流出的分支数；某列非零元素数目表示该列对应节点的流入分支数。目表示该列对应节点的流入分支数。2.2 图的矩阵表示图的矩阵表示 行数表示节点数，列数表示边数；行数表示节点数，列数表示边数；每一行非零元素表示对应节点的线度，每一行非零元素表示对应节点的线度，其中其中l表示正线度，表示正线度，1表示负线度；表示负线度；每列仅有的二个非零元素表示相应边每列仅有的二个非零元素表示相应边的始末点，的始末点，1对应于始点，对应于始点，1对应于对应于终点。终点。1234abcdef 1 10000121110003 0

24、011104 010111eabcdefB2.2 图的矩阵表示图的矩阵表示 在在m阶连通图阶连通图G的完全关联矩阵的完全关联矩阵 中，划去任一行中，划去任一行后，所得的后，所得的 矩阵，称为图矩阵，称为图G的的基本关联矩阵基本关联矩阵，简称关，简称关联矩阵，记作联矩阵，记作B。划去的对应点称为参考点划去的对应点称为参考点。通风网。通风网络图中常把大气节点作为参考点。络图中常把大气节点作为参考点。1234abcdef 1 10000121110003 0011104 010111eabcdefB 111000200111030101114abcdefB 在通风网络中，若划去一行为大气节点，则在通

25、风网络中，若划去一行为大气节点，则B中中仅含一个非零元素的列，即为与地面大气直接相连的仅含一个非零元素的列，即为与地面大气直接相连的分支，仅有一个分支，仅有一个1的列对应的边为的列对应的边为矿井出风分支矿井出风分支仅仅有一个有一个1的列对应的边为的列对应的边为入风井分支入风井分支。2.2 图的矩阵表示图的矩阵表示 mn矩阵的一个阶数为矩阵的一个阶数为minm, n的方阵，称为的方阵，称为mn矩阵的一个大子阵矩阵的一个大子阵，大子阵定义的行列式称为大行列式。，大子阵定义的行列式称为大行列式。 定理：连通图定理：连通图G的基本关联矩阵的基本关联矩阵B的一个大子阵是非奇的一个大子阵是非奇异的充要条件

26、为与这个异的充要条件为与这个大子阵的列相应的边，组成大子阵的列相应的边，组成G的一棵的一棵生成树。生成树。 找出图找出图G的关联矩阵的全部非奇异大子阵，每个的关联矩阵的全部非奇异大子阵，每个非奇非奇异大子阵的列所对应的边就是异大子阵的列所对应的边就是G的一棵生成树的一棵生成树。图2-10 关联矩阵与生成树的关系 图中非奇异大子阵的列为图中非奇异大子阵的列为(a, b, c, d)、(a, b, c, e) 、(a, b, d, e)、(a, b, d, f)、(a, b, e, f) 、(a, c, d, e)、(a, c, d, f) 、(a, c, e, f)、(b, c, d, e)、(

27、b, c, d, f)、(b, c, e, f)均对应于图均对应于图2-10的一棵生成树。而的一棵生成树。而B中由中由列列(a, d, e, f)、(a, b, c, f)、(b, d, e, f)、(c, d, e, f)组成的大子阵都是奇异的，故它们组成的大子阵都是奇异的，故它们均不是生成树均不是生成树2.2 图的矩阵表示图的矩阵表示 完全回路矩阵的各行不都是线性独立的，有些行可完全回路矩阵的各行不都是线性独立的，有些行可通过另一些行的线性组合求得。对于连通图通过另一些行的线性组合求得。对于连通图G为为 来说，来说，则完全回路矩阵的秩等于则完全回路矩阵的秩等于 n-m+12.2 图的矩阵表

28、示图的矩阵表示 如图如图2-11中，关于生成树中，关于生成树T（2，3，6）的基本回路矩阵）的基本回路矩阵123 1 2 3 456111000010011011101cCcc2.2 图的矩阵表示图的矩阵表示 基本回路矩阵的每行对应于一个独立回路。每行中的基本回路矩阵的每行对应于一个独立回路。每行中的非零元素即为该独立回路的组成分支。基本回路矩阵具有非零元素即为该独立回路的组成分支。基本回路矩阵具有如下性质：如下性质：(1) 连通图连通图G(m、n)的基本回路矩阵的秩等于的基本回路矩阵的秩等于(n-m+1)。(2) 连通图连通图G的生成树的生成树T的基本回路矩阵的列，若按余树弦的基本回路矩阵的

29、列，若按余树弦在前、树枝在后排列、则可将回路矩阵分为两部分，使余在前、树枝在后排列、则可将回路矩阵分为两部分，使余树弦矩阵为单位矩阵树弦矩阵为单位矩阵I，即，即 CI，Cf 123 1 2 3 456111000010011011101cCcc2.2 图的矩阵表示图的矩阵表示 显然，连通图显然，连通图G的完全割集矩阵的完全割集矩阵Se是线性相关的。是线性相关的。连通图连通图G(m，n)的完全割集矩阵的秩是的完全割集矩阵的秩是(m1)。1234abcdefS1S2S3S7S5S6S41234567 110001011101000111101100110110011010101011eabcdef

30、sssSssss2.2 图的矩阵表示图的矩阵表示 如图，取生成树如图，取生成树T(a、c、e)，则其对应的，则其对应的基本割集矩阵：基本割集矩阵：1234abcdefS1S2S3S7S5S6S4123110001011101000111abcdefsSss如果其列序按余树在前、如果其列序按余树在前、树枝在后，行按树枝在矩树枝在后，行按树枝在矩阵内的列序排序，则基本阵内的列序排序，则基本割集矩阵可写成割集矩阵可写成,jSSI101100 111010011001fbdfaceSSI2.2 图的矩阵表示图的矩阵表示 为便于叙述矩阵间的关系，首先需将矩阵为便于叙述矩阵间的关系，首先需将矩阵B、C、S

31、均均按按余树弦子阵在前、树枝子阵在后分块。余树弦子阵在前、树枝子阵在后分块。 例例2-2： 如图如图2-13所示，所示，G=（5，7），取一棵生成树），取一棵生成树T=（e1,e3,e4,e5），余树），余树(e2,e6,e7)e1v1v2v5v4e2e3e4e5v3e6e7267134511120001101010011010100100110001 = eeeeeeeBBB2671345123111212100111001001010010111 = = ceeeeeeecCccCCIC267134512341112111001000111010010100100110001 = = Se

32、eeeeeesCsssSSSI 2.2 图的矩阵表示图的矩阵表示e1v1v2v5v4e2e3e4e5v3e6e71211211010110001000011111011000100001BB1121112100000101100 =01011110001110011110 = 0-1010-1-11TTCBB 2.2 图的矩阵表示图的矩阵表示e1v1v2v5v4e2e3e4e5v3e6e70TCS0TSC1112TSC 12 TSCIs，1112100100111111101101011011TSC 2.2 图的矩阵表示图的矩阵表示e1v1v2v5v4e2e3e4e5v3e6e71111211

33、SBB11211 SB BIs，1121111011000100001B11000010101011B1111211SB B1111000011001000101010001011100111101011 2.3生成树的选择生成树的选择 在一个连通图中，逐次去掉一些边，在一个连通图中，逐次去掉一些边，以破除图中所有以破除图中所有回路，回路，则剩下的不含回路的连通图就是图的一棵生成树。则剩下的不含回路的连通图就是图的一棵生成树。如需选择最小树，每次去掉的边应是被破回路中权最大者；如需选择最小树，每次去掉的边应是被破回路中权最大者；如需选最大树，则逐次去掉的边应是被破回路中权最小者。如需选最大树，

34、则逐次去掉的边应是被破回路中权最小者。 (1) 画网路图，将点、边编号，标出风向。因画网路图，将点、边编号，标出风向。因G的的边数边数n6，节点数，节点数m4；(2) 确定图的余树弦数确定图的余树弦数N=n-m+1=3； (3) 将分支按权大小排序按风阻赋权，风阻按升序将分支按权大小排序按风阻赋权，风阻按升序排列为排列为R1，R6 ，R4，R2，R5，R3 (4) 从权最大的分支起，依次从图中除去，移去后从权最大的分支起，依次从图中除去，移去后被破坏的回路，即可能是独立回路。若被破坏的被破坏的回路，即可能是独立回路。若被破坏的回路中，有一条以上高阻分支，应重选；回路中，有一条以上高阻分支，应重

35、选；(5) 重复重复(4)，直到移去，直到移去nm1条余树弦，剩余的条余树弦，剩余的分支即组成最小风阻树分支即组成最小风阻树Tmin； 2.3生成树的选择生成树的选择 在图中任取一条边在图中任取一条边e1 ，找一条不与，找一条不与 e1构成回路的边构成回路的边e2 相连，然后再找一条不与相连，然后再找一条不与e1 e2 构成回路的边构成回路的边 相连，如相连，如此继续，直到此过程不能进行，这时所得的图就是一棵生此继续，直到此过程不能进行，这时所得的图就是一棵生成树，若加入的边总是权小的边，可得一成树，若加入的边总是权小的边，可得一最小树最小树；若加入；若加入的边总是权大的边，则得的边总是权大的

36、边，则得最大树最大树.(1) 将图去边留点；将图去边留点；(2) 将分支按权排序；每加入一条边都要判断是否构将分支按权排序；每加入一条边都要判断是否构成回路，若新加入的边与已有边构成回路，则这条成回路，若新加入的边与已有边构成回路，则这条边就是余树弦，将它取走，计入余树弦集合；若新边就是余树弦，将它取走，计入余树弦集合；若新加入的边与已加入的边未构成回路，说明它是树枝，加入的边与已加入的边未构成回路，说明它是树枝，计入树枝集合；计入树枝集合；(4) 重复重复(3)，将所有边都加过后，取走，将所有边都加过后，取走nm1条余条余树弦，剩余的树弦，剩余的(m1)条边，即构成一棵生成树条边，即构成一棵

37、生成树。2.3生成树的选择生成树的选择从权最小的分支从权最小的分支1开始加边，依次加边开始加边，依次加边6、加边、加边4，均未能形成回路，均未能形成回路，再加边再加边2，形成回路，形成回路(2，1，6，4)，去掉最后加入使图形成回路的分支，去掉最后加入使图形成回路的分支2，即为余树弦；再加边，即为余树弦；再加边5，形成回路，形成回路(5，6，4)，去掉，去掉5，亦为余，亦为余树弦；再加边树弦；再加边3，形成回路，形成回路(3，1，6)，分支，分支3亦是余树弦；去掉余树弦亦是余树弦；去掉余树弦后剩余的子图，即为最小树后剩余的子图，即为最小树Tmin(1，4，6)。例：例： 试以图为例，用加边法选择最小树。分支风阻升序排列为试以图为例，用加边法选择最小树。分支风阻升序排列为1，6，4，2，5，3。2.3生成树的选择生成树的选择 1) 基本思路基本思路：在图的一棵生成树中，每加入一条余树在图的一棵生成树中，每加入一条余树弦，可得到一个独立回路