1、网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-91在前面所学的在前面所学的“电工原理电工原理”等课程中,由于网络(即等课程中,由于网络(即所谓的所谓的“电路电路”)结构比较简单,人们可以比较容易地利)结构比较简单,人们可以比较容易地利用用“电工原理电工原理”中介绍的各种方法去求解网络参数。然而中介绍的各种方法去求解网络参数。然而随着科学技术的不断发展和提高,网络的结构日趋复杂随着科学技术的不断发展和提高,网络的结构日趋复杂(支路数和节点数大大地增加),再用那些传统的方法来(支路数和节点数大大地增加),再用那些传统的方法来分析和设计已经是力不从心了,因此有必要寻找一种全新
2、分析和设计已经是力不从心了,因此有必要寻找一种全新的系统化的即能够把计算机作为辅助计算工具的方法来进的系统化的即能够把计算机作为辅助计算工具的方法来进行网络分析和设计,这种方法就是网络图论。行网络分析和设计,这种方法就是网络图论。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-92图论虽然属于拓扑学的范畴,但是它的应用已渗透图论虽然属于拓扑学的范畴,但是它的应用已渗透到许多学科领域,它在电路(网络)中的应用称为网络到许多学科领域,它在电路(网络)中的应用称为网络图论或网络拓扑。图论或网络拓扑。本章介绍图的一些基本知识,并结合电路分析的方本章介绍图的一些基本知识
3、,并结合电路分析的方法,应用网络拓扑的知识,系统地建立各种网络方程的法,应用网络拓扑的知识,系统地建立各种网络方程的基本矩阵形式,以便进行分析和计算。基本矩阵形式,以便进行分析和计算。 网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-93本章主要内容本章主要内容图的基本知识图的基本知识拓扑矩阵拓扑矩阵电网络的矩阵分析法电网络的矩阵分析法返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-94图的基本知识图的基本知识 图论的发展简史图论的发展简史 网络拓扑的基本概念网络拓扑的基本概念 树树 基本回路、基本割集基本回路、基本割集 基本回路基本回路
4、割集割集 基本割集基本割集割集分析法割集分析法返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-95图论的发展简史图论的发展简史 哥尼斯堡桥 汉密尔登圈 平面图与非平面图 电网络方程 四色定理 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-96哥尼斯堡桥哥尼斯堡桥 瑞士数字家欧拉(Euler)发表了一篇讨论哥尼斯堡(这是原十八世纪东普鲁士、现为立陶宛的一个城市)七桥(如图所示,其中 A、B、C、D 为四块陆地,其余为连接为四地的七座桥梁)难题的论文。ABCD网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-97
5、哥尼斯堡桥哥尼斯堡桥 这篇论文讨论的主要内容是:从 A、B、C、D 任何一地出发,走遍七座桥,但每座桥只能经过一次(一笔画)。这个想法能不能实现?欧拉经过多次实验都没有成功;最后欧拉认为上述目的是无法实现的,并总结出一个通用判定准则:网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-98哥尼斯堡桥哥尼斯堡桥 连接奇数个桥的陆地只有一个或超过两个以上时,不能实现一笔画; 连接奇数个桥的陆地仅有二个时,则从两者中的任一块陆地出发,可以实现一笔画,但终止在另一块陆地上; 每块陆地都接有偶数个桥时,则从任一块陆地出发都能实现一笔画,并且回到原出发点。网络分析与综合网络分析与综合网络
6、图论网络图论上一页上一页2022-6-99哥尼斯堡桥哥尼斯堡桥将陆地用点来表示,桥用线段来表示,就构成了一个图。要想一笔画出这个图,就要求这个图满足下面的条件:图必须是连通的,且每个顶点所关联的边的条数都是偶数,此时,一笔画的起点与终点相同;若其中仅有一对顶点关联的边数是奇数,则可以从这两顶点之一出发,终止于另一个顶点完成一笔画。 网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-910哥尼斯堡桥哥尼斯堡桥哥尼斯堡七桥等效模拟图见图,由于该图中 A、B、C、D 四点所关联的边都是奇数,因而不可能实现不重复地走遍七座桥。欧拉最先一个实际问题化为一个图论的问题,并加以解决,所以
7、后来人们公认欧拉为图论的创始人,把一笔画出来的路称为欧拉路。 ABCDABCD返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-911汉密尔登圈汉密尔登圈 英国数学家汉密尔登(Hamiltonian)发明了一种称为Euler Trail的游戏:在一个画在平面上有20个顶点的图中,把这20个顶点当作20个城市,旅行者从其中某一个城市出发,能否找出一条经过所有城市,但只能经过一次的闭合路径?回答是肯定的(如图中按从小到大的数字即12319201的路径就是满足要求的一条路径)。该回路称为汉密尔登圈,而含有汉密尔登圈的图称为汉密尔登图。 网络分析与综合网络分析与综合网络图
8、论网络图论上一页上一页2022-6-912汉密尔登圈汉密尔登圈 1234567891011121314151617181920网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-913汉密尔登圈汉密尔登圈 欧拉路与汉密尔登圈的区别:欧拉路与汉密尔登圈的区别:前者的一条路必须经过每一条边且只能经过一次,而经过各顶点的次数不限;后者的一条路必须经过每一个顶点且只能经过一次,而经过边的次数不限,也可以不经过。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-914如果图中的所有边在顶点以外的地方均不相交,那么这个图就称为平面图,否则就是非平面图。判断
9、一个图是不是一个平面图,可以看它是否满足公式:nb + f = 2 (其中 n 、b 、f 分别为图的顶点数、边数和面数),如果满足,这个图就是平面图,反之,这个图就是非平面图。 平面图与非平面图平面图与非平面图 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-915电网络方程电网络方程 如何确定及列出给定电网络的独立方程是较长时间困扰人们的问题。基尔霍夫(Kirchhoff)由树的概念提出了解决确定独立方程数的方法;还提出了列出集总(或分布)参数电网络的相应方程的两个基本方法:KVL(基尔霍夫回路电压定律)、KCL(基尔霍夫节点电流定律)。 返返 回回网络分析
10、与综合网络分析与综合网络图论网络图论上一页上一页2022-6-916四色定理四色定理 四色定理起源于对地图的染色:一个英国人提出,他只需四种颜色,就能使平面地图上任两个相邻国家的颜色不同,这里所谓的相邻是指两个国家有一段公共边界。将这个四色问题转化成图论的问题则为:用一个顶点代表一个国家,如果某二个国家相邻,就用一条线(边)将对应二个顶点连接起来,证明只需要有四种颜色,就可以使所有相邻的顶点有不同颜色,这就是四色定理(该定理在1976年得到了证明)。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-917网络拓扑的基本概念网络拓扑的基本概念 节点的度节点的度 子
11、图子图 通路通路 连通图和非连通图连通图和非连通图 回路回路 图的定义及电网络图的表示图的定义及电网络图的表示 与图有关的几个名词与图有关的几个名词 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-918图的定义及电网络图的表示图的定义及电网络图的表示 图图:一组顶点与线段(边)的集合,边的两端终止于顶点,又称为“线图”,可用G(graph)表示。它把实际的网络结构用顶点和线段抽象地表示成几何图形。电网络中各支路两端的电压、流过各支路的电流之间的规律服从于定理 KVL、KCL,它们只与网络的连接形式有关,而与各支路中所含的元件类型无关。 网络分析与综合网络分析与
12、综合网络图论网络图论上一页上一页2022-6-919图的定义及电网络图的表示图的定义及电网络图的表示 3b1b2b4b5b6b图图或线性图线性图,还可以简称为“图图”。为了习惯或方便,我们仍可称图中的顶点为节节点点(Node),称线段为支路支路(Branch)。我们用圆点表示节点(或称结点),用线段表示支路,这样就可以得到一个抽象的描述网络连接情况的图,把它称为网络的拓扑图拓扑图,也可以称为线线网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-920图的定义及电网络图的表示图的定义及电网络图的表示 其中线段上没有方向箭头的图称为无向图;如果各线段上有箭头,它表示所对应支路的
13、电流或电压降的参考方向的图称为有向图,又称为有向线图,在实际应用中,有向图用得比较多。 6b1b2b3b4b5b6b1b2b3b4b5b3b1b2b4b5b6b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-921与图有关的几个名词与图有关的几个名词节点的度节点的度 G 中某节点的度,表示与该节点相关联的支路数。如图中节点、的度都为 3,因为与它们相关联的支路都有3条。 6b1b2b3b4b5b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-922与图有关的几个名词与图有关的几个名词 子子 图图G中的任一部分节点与支路的集合,可以
14、用表Gs示(Sub-graph)。如图中节点、与支路 b2、b4 构成一个子图,节点、与支路 b1、b5、b6构成一个子图,节点、与支路 b3、b5 也构成一个子图。 6b1b2b3b4b5b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-923与图有关的几个名词与图有关的几个名词 通通 路路两个端节点,通过内节点及相应支路相连而构成的子图(或路径)。 端节点:端节点:仅与一条支路相连的节点,它的度为1。内节点:内节点:与二条或二条以上的支路相连的节点,其度大于等于2(但通路的内节点的度只能为2)。网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022
15、-6-924与图有关的几个名词与图有关的几个名词 通通 路路在图中如果单看节点、与支路 b1、b2 就构成一条通路(其中节点、为端节点,节点为内节点),节点、与支路 b2、b3、b5 也构成一条通路(其中节点、为端节点,节点、为内节点)。 6b1b2b3b4b5b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-925与图有关的几个名词与图有关的几个名词连通图和非连通图连通图和非连通图 若若 G 中任二个节点间至少有中任二个节点间至少有一条通路,则称一条通路,则称G 为为连通图连通图(Connected Graph),否则),否则G 为为非连通图非连通图(Unco
16、nnected Graph)。)。如图中节点、与支路如图中节点、与支路 b b1 1、b b2 2构成的子图和节点、构成的子图和节点、与支路与支路 b b1 1、b b5 5、b b6 6 构成的子图构成的子图都是连通图,而节点、都是连通图,而节点、与支路与支路 b b3 3、b b5 5 构成的子图就是构成的子图就是非连通图。非连通图。 6b1b2b3b4b5b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-926与图有关的几个名词与图有关的几个名词回路回路通路的两端节点重合时形成的一个闭合路径就是回路回路(Loop或Circuit)。回路的特点是:回路的特点
17、是:当移去其中任何一条支路时,路径则没有闭合,或者它其中每个节点的度均为2。如图中节点、与支路 b2、b3、b4 构成的子图,节点、与支路 b1、b3、b6 构成的子图,节点、与支路 b4、b5、b6 的子图。特特殊地,殊地,一个节点和一条支路也可以构成一个回路,我们把它称为“自环”。 6b1b2b3b4b5b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-927树树 树在拓扑理论尤其在我们这里的网络拓扑中是一个非常重要的概念。网络拓扑中的树是一组支路及与它们相关节点的集合,对于每个连通图来说,其树的选择不是唯一的,而一旦确定了树以后,整个图就分成了树枝和连枝二
18、部分:构成树的各支路称为树枝树枝,而图中除树以外的剩余部分支路则被称为连枝连枝,其集合又称为对应树的“补树补树”。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-928树树 树的定义树的定义 两种特殊类型的树:两种特殊类型的树:线树线树、星树星树 树的几个基本定理树的几个基本定理 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-929树的定义树的定义 包含有图G 中所有节点但又无回路的连通子图。详细来说就是:具有n+1 个节点,b 条支路连通图G 的一个连通子图,若具有下列特性中的任意两个: 包含图G的所有节点; 具有n 条支路
19、; 没有回路。这就是图G 的一个树(Tree),可以用T 表示。网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-930下面是左图所示网络的部分树。 6b1b2b3b4b5b1b5b6b2b3b1b3b4b5b1b4b5b6b1b2b树的定义树的定义 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-931两种特殊类型的树两种特殊类型的树线线 树树如果其所有树枝仅连成了一条通路(路径),那么这个树就称为线树,如下图所示的树; 3b4b5b1b4b5b6b1b2b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-93
20、2两种特殊类型的树两种特殊类型的树星星 树树如果其所有树枝有一个公共的顶点,那么这个树就称为星树,如下图所示的树(它们的公共顶点分别是节点和节点); 1b5b6b2b3b1b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-933树的几个基本定理树的几个基本定理 定理一:定理一:每一个连通图G 至少存在一个树: 如果G 中不含有回路,则G 就是一个树; 如果G 中含有回路,那么在保证G 连通的前提下,移去某一回路的一条支路,并按照这种方法,破坏掉所有的回路,剩下的就是树。定理二:定理二:若连通图中包含有n+1个节点,那么它的树必定有n条树枝。定理三:定理三:如果连
21、通图G 中的任意两节点之间,当且仅当存在一条通路(路径)时,则G就是一个树。 网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-934树的几个基本定理树的几个基本定理 定理四:定理四:在含有n+1个节点的连通图 G 中,若具有如下性质之一,则G 就是一个树;反之,如果G 是一个树,则它就具有以下性质: G 连通但没有回路; G 有n 条支路,且无回路; G 连通,且含有n 条支路; G 没有回路,但任意在两节点间加一条支路,就会出现一个回路; G 连通,但移去一条支路后,G 就不连通了; 从G 中任一个节点到另一个节点,有且仅有一条通路(或路径)。 返返 回回网络分析与综合
22、网络分析与综合网络图论网络图论上一页上一页2022-6-935基本回路基本回路基本回路是回路的一种,是一种特殊的回路。定义:定义:(一般在有向图中考虑)单连枝回路,即它是由且仅由一条连枝支路,其余均为树枝支路构成的。 3b6b1b2b4b5b1b3b4b5b13b4b5b2b3b4b266b4b5b网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-936基本回路的特点基本回路的特点 其方向取连枝支路的电流参考方向;其方向取连枝支路的电流参考方向;对给定的连通图(节点有对给定的连通图(节点有n+1+1个,支路有个,支路有b条)来说,基本回路的数量是一定的,为条)来说,基本回路
23、的数量是一定的,为b- -n 个。个。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-937割割 集集 定义:定义:连通图G 中一个边(支路)的最小集合 c 。性质:性质: 移去c 中所有的支路后,G 就被分成两个不相连的子图Gs(也可以分成两个以上的Gs,但如果不加说明,后面所指割集均是只分成两个Gs 的简单割集); 若保留c 中任一条支路,而移去其余支路,G 仍是连通的。 网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-938割割 集集 顶点割集:顶点割集:移去c 后,两个中Gs 有一个孤立顶点。如右图中,取b1、b5、b6 为一个割
24、集c5,移去c5 后剩下二部分:其一为节点,其二为、节点和支路b2、b3、b4,这二部分不连通,且一部分就只剩节点,所以把这个c5 割集称为顶点割集。同理,左图中,c3 也是一个顶点割集。3c6b1b2b3b4b5b4c6b1b2b3b4b5b5c6b1b2b3b4b5b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-939基本割集基本割集 同样道理,基本割集是割集的一种,一种特殊的割集。定义:定义:(一般在有向图中考虑)单树枝割集,即它是由且仅由一条树枝支路,其余均为连枝支路构成的。基本割集的特点:基本割集的特点: 其方向取树枝支路的电流参考方向; 对给定的连
25、通图(节点有 n+1 个,支路有b 条)来说,基本割集的数量也是一定的,为 n 个(与树枝数相同)。返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-940割集分析法割集分析法我们对电网络的分析方法有四种:利用基尔霍夫回路电压定律 KVL 的回路回路分析法、网孔网孔分析法(当回路恰好是网孔的时候,回路分析法就变成了网孔分析法,所以说网孔分析法是回路分析法的特例),利用基尔霍夫节点电流定律 KCL 的割集割集分析法、节点节点分析法(当割集恰好都是顶点割集的时候,割集分析法就变成了节点分析法,所以说节点分析法是割集分析法的特例)。这里通过一个例子来介绍割集分析法。 网
26、络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-941割集分析法割集分析法首先选择一棵树,利用由基尔霍夫节点电流定律 KCL 的对基本割集列出的一组电流方程是独立的方程组,求解这个方程组,可以得到树枝电压,进而利用网络中各支路之间的基本关系可以求出除树以外支路的电压和所有支路的电流。 网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-942割集分析法割集分析法如图,首先选 b1、b4、b5、b7 为树枝,取对应四个基本割集。利用 KCL 对基本割集列电流方程:与割集方向相同的支路电流取正号,否则取负号,于是有: 0000 7665343221IIIIII
27、IIII2b3b6b1b4b5b7b1c4c5c7c网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-943割集分析法割集分析法这里设b3 支路有一个电流源Ig3(若是电压源 Ug3,可以利用诺顿定理变换成电流源Ig3=G3Ug3),方向与支路方向相同,于是有: 333gIII前式为 00 0000 7636533432217665343221IIIIIIIIIIIIIIIIIIIIIIgg网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-944割集分析法割集分析法设各支路导纳为Gi,电压为Ui,连枝电压用树枝电压来表示(电压方向与电流方向成关联关系)为
28、: 2b3b6b1b4b5b7b1c4c5c7c412UUU543UUU756UUU网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-945割集分析法割集分析法将 代入 iiiUGI 00 763653343221IIIIIIIIIIIIgg得 00 7775637565554334454341241211UGUUGIUUGUGUUGIUGUUGUUGUUGUGgg756543412 UUUUUUUUU网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-946割集分析法割集分析法整理得: 由上式可以看出:第一个方程是对第一个割集列写的,其左边第一项是本割集
29、树枝电压 U1 与本割集所有相关联支路导纳总和的乘积,第二项是第二割集树枝电压与第一、二割集所有公共支路导纳之和 G2 的乘积,因为第一、二割集方向相反,故第二项前取负号,由于第一割集与第三、四割集无公共支路,故方程的第三、四项为零,另外方程右端为零,表示无电流源流过本割集;第二方程右端为一个负电流源 Ig3,表示电流源 Ig3 与割集方向相同。 00 7765637656534335344321242121UGGUGIUGUGGGUGIUGUGGGUGUGUGGgg2b3b6b1b4b5b7b1c4c5c7c网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-947割集分析
30、法割集分析法找出如上规律,就可以由电路的有向图直接写出上面的割集方程组了,而不需要再重复前面的步骤。最后,就可以求解割集方程组得到树枝电压U1、U4、U5 和U7 ,并根据连枝电压与树枝电压的关系求出连枝电压U2、U3 和U6 ,最后再由 Ii=GiUi 求出各支路的电流。总结以上讨论的结果,我们可以得到如下割集分析法的一般步骤: 网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-948割集分析法步骤割集分析法步骤 画出电路对应的有向图。 为电路选择一棵树,其原则是:尽可能选“星树”,这样列出方程通常比较简单;电压源应选为树枝,这样可以少列方程;尽可能地把待求电压支路选为树
31、枝,这样解出割集方程也得到了待求电压。 取基本割集。网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-949割集分析法步骤割集分析法步骤 列割集方程,此时要注意的是:本割集树枝电压与本割集所关联的所有导纳总和和乘积项永远取“+”号;相邻项的“+”、“-”号取决于二个相关割集的方向是否相同,相同取“+”号,相反取“-”号;方程右边为流过本割集的电流源,其“+”、“-”号与电流源的方向、割集的方向都有关,当电流源的方向与割集方向相同时取“-”号,相反时则取“+”号。网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-950割集分析法步骤割集分析法步骤 解割集方
32、程组求出树枝电压。 由树枝电压求出连枝电压。 由树枝电压、连枝电压及各支路导纳(或阻抗)求出各支路电流。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-951拓扑矩阵拓扑矩阵 邻接矩阵邻接矩阵 关联矩阵关联矩阵 回路矩阵回路矩阵 割集矩阵割集矩阵 矩阵矩阵 A、Bf 、Qf 之间的关系之间的关系 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-952邻接矩阵邻接矩阵 表征节点与节点之间关系的矩阵,用 表示,其元素 dij 的取值如下: 注:注:相邻表示有支路相连。 1 1 nnjidD 0 1 无自环不相邻与节点节点有自环相邻与
33、节点节点jijijijiijd网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-953例例 子子 4321 0111101111011110 4321aD 54321010011010101011001011111054321bD3b6b1b2b4b5b7b1b2b3b4b5b6b返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-954关联矩阵关联矩阵 表征节点与支路之间关系的矩阵。表征节点与支路之间关系的矩阵。无向图的关联矩阵无向图的关联矩阵有向图的关联矩阵有向图的关联矩阵 增广关联矩阵增广关联矩阵 关联矩阵关联矩阵 网络分析与综合网络分析与
34、综合网络图论网络图论上一页上一页2022-6-955无向图的关联矩阵无向图的关联矩阵 用 表示,其元素 的取值如下:这里的关联表示节点 i 为支路 j 的一个端点,否则就不是。 bnjiaaA 1 jia jia 无关联与支路节点相关联与支路节点 0 1 jiji网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-956例例 子子 3b6b1b2b4b5b7b1b2b3b4b5b6b 4321 110001101100011010 0 0 0 1 1 1 654321bbbbbbAaa 54321 1100000011010000011100000011 1 0 1 1 0
35、0 1 7654321bbbbbbbAba网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-957无向图的关联矩阵性质无向图的关联矩阵性质 每列只有2 个1 元素;每行1元素的个数对应节点的度;对连通图,关联矩阵的每一行至少有一个1元素;如果某一行只有一个1元素,那么这个1 元素所在的列对应的支路一定是一条悬挂支路。如果形如 ,则对应的图为一个具有两个连通子图的非连通图。221100AAAa网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-958增广关联矩阵增广关联矩阵 用 表示,其元素 的取值如下: bnijaaA1ija的方向的方向为指向节点且支路相
36、关联与支路节点的方向的方向为离开节点且支路相关联与支路节点无关联与支路节点 , 1 , 1 0 ijjiijjijiija网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-959例例 子子3b6b1b2b4b5b7b1b2b3b4b5b6b 4321110001101100011010000111654321bbbbbbAaa 12345671001101111000002011100030010110400000115a bbbbbbbbA网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-960增广关联矩阵性质增广关联矩阵性质 每一列只有两个非零元素1
37、和-1,且同列元素之和为零; 任一行元素等于其它各行元素之和,且符号相反。这说明全部节点均写方程的话,肯定至少有一个方程非独立,由此可以划掉一行(一般划去电位参考点所在的那一行),由此得关联矩阵(或称为降阶关联矩阵,节点矩阵)。 网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-961关联矩阵关联矩阵 例如(分别取节点、为参考节点)的关联矩阵分别为: 1234561110001010110100020011014311a abbbbbbA 12345670111000100110111100000200101104000001153a bbbbbbbbA 1234567 1
38、0011011110000020010110400000115 bbbbbbbbAbnijaA 321101100011010000111 654321bbbbbbAa网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-962关联矩阵关联矩阵 对下图,如果选 b1、b4、b5、b7 为树,把 A 分成左右两部分:左边为树枝块 AT ,右边为连枝块 AL(脚标各自从小到大排列),则 7b1b2b3b4b5b6b1457236 1111 00011 00010020010011400010015TLb bbbbbbAAA 1234567 100110111100000200101
39、10400000115 bbbbbbbbA显然有 , 。nTnA Ln b nA返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-963回路矩阵回路矩阵 回路矩阵回路矩阵(回路支路)(回路支路) 基本回路矩阵基本回路矩阵(基本回路支路)(基本回路支路) 表征(有向图中)回路与支路关系的矩阵。表征(有向图中)回路与支路关系的矩阵。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-964回路矩阵(回路支路)回路矩阵(回路支路) 用表示 ,其元素 的取值如下: 方向相反与回路且支路相关联与支路回路方向相同与回路且支路相关联与支路回路不关联
40、与支路回路 1 1 0 ij,jiij,jijiijbbijabBijb网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-965例例 子子如图所示,除三个网孔分别构成 l1、l2、l3 回路外,还有l1 与l2 两网孔合并构成一个回路l4 ,l2 与l3 两网孔合并构成一个回路l5 ,最后还有整个外围构成一个回路l6 。假设均取顺时针方向为回路的方向,依定义可以列出如下回路矩阵: 6543217654321110011111011000010111111000000111000001011 bbbbbbbBa7b12b3b4b5b6b7b234561b返返 回回网络分析与综
41、合网络分析与综合网络图论网络图论上一页上一页2022-6-966基本回路矩阵(基本回路支路)基本回路矩阵(基本回路支路) 用 表示,回路的方向与连枝方向相同,其元素 bij 的取值与上面的相同,显然会有树枝选的不同,连枝也就不一样,这样 Bf 也就不一样,例如对下图如果选b1、b4、b5、b7 为树(如粗线所示),那么连枝为 b2、b3、b6,对应的基本回路如右边几个图,其 Bf 如下式:2b3b6b1b4b5b7b6326327541100110001001100010011 bbbbbbbBfbnbjifbB 2b1b4b5b7b21b4b5b7b3b31b4b5b7b6b6网络分析与综合
42、网络分析与综合网络图论网络图论上一页上一页2022-6-967例例 子子若取 b1、b2、b3、b6 为树(如图粗线所示),那么连枝就是 b4、b5、b7,对应的基本回路也如图所示,其Bf 如下右式: 7547546321100111101001110010011 bbbbbbbBf1b2b3b4b5b6b7b6b3b1b4b2b46b3b2b1b5b56b3b2b1b7b7可以表示为: 。其中: :与树枝相关联的部分; :与连枝相关联部分。 1TLTfBBBBnnbfB 1nbnbLB返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-968割集矩阵割集矩阵 割集
43、矩阵割集矩阵(割集支路)(割集支路) 基本割集矩阵基本割集矩阵(基本割集支路)(基本割集支路) 表征割集与支路关系的矩阵。表征割集与支路关系的矩阵。 返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-969割集矩阵(割集支路)割集矩阵(割集支路) 用表示 ,其元素 的取值如下:(其中c为总的割集数) bcijaqQijq方向相反的方向与割集且支路相关联与支路割集方向一致的方向与割集且支路相关联与支路割集不关联与支路割集 , 1 , 1 0 ijjiijjijiijq网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-970例例 子子如图所示,除了
44、c1、c4、c5、c7四个割集外,还有很多割集。为了不至于遗漏,可以采用c1c4、c1 c5 、c4 c5 、c1 c4 c5 等等这样的方式,把它们所有的组合都列出来,就构成相应电路的割集矩阵。 2b3b6b1b4b5b7b1c4c5c7c网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-971例例 子子注意:注意:式中由于未标出割集的方向,这时仅用“1”表示该割集与相应支路相关联,用“0”表示该割集与相应支路无关联;式中的有些割集不只把图分成了二个子图。 7541754751741541757454715141754176543211011001101101010101
45、11110110101110011010100110111001110101100011011011100011011100000011010000011100000011 ccccccccccccccccccccccccccccccccbbbbbbbQa返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-972基本割集矩阵(基本割集支路)基本割集矩阵(基本割集支路) 以一条树枝,数条连枝做一个割集,取树枝方向为割集的方向。例如,如果选b1、b4、b5、b7 为树枝,那么连枝为b2、b3、b6,于是对应Qf 的如下(其中: 为与树枝关联的部分, 为与连枝关联的部分。
46、同样,树选的不同,Qf 也就不一样): 2b3b6b1b4b5b7b1c4c5c7c1nTnQnbLnQ754173275411001000110010001100100010001 ccccbbbbbbbQbfnLLTQQQ1返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-973矩阵矩阵 A、Bf 、Qf 之间的关系之间的关系 在选定相同的树,且在先树枝后连枝,支路顺序相同时所列出的拓扑矩阵 A、Bf 、Qf 有如下关系: 0 0 0 0TffTffTfTfQBBQABAB或及或LfTfLTQQ,BB,AAA1 1 若节点数为 n+1 个,支路数为b 条,则树
47、枝为n 条,连枝为b-n 条,则各矩阵的大小为: nbnLbnfnnbTbnbfnbnLnnTbnQ、Q、B、B、A、A、A LTTTTLTffLTTTTTLTTfQBBQBQ、ABABAAAB1 1 1 于是有:于是有:网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-974矩阵矩阵 A、Bf 、Qf 之间的关系之间的关系 由前面的例子可以得到: 1457236 1111 0 0011 0001 002001 00 11400010 015TLb bbbb bbAAA 1 1 111 0 000 01 00 0 01TA100110001000LA110001100011
48、TB6326327541100110001001100010011 bbbbbbbBf754173275411001000110010001100100010001 ccccbbbbbbbQbfn100110011001LQ网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-975矩阵矩阵 A、Bf 、Qf 之间的关系之间的关系 于是,利用以上关系,可以由一种矩阵求出其它两种矩阵。 TLTTLTTTTTTAAB,ABA,BA1 0 100110001000LTfTLTfLTTTLLTTAAQAAB,AABQ,QB111 1 1 0网络分析与综合网络分析与综合网络图论网络图论上
49、一页上一页2022-6-976例例 子(子(2.1)已知: ,试画出对应的有向图,并求矩阵 Bf 及 Qf 。 4321010010010100001010100010100111008 7 6 5 4 3 2 1A解:解:由矩阵可以画出如图所示的有向图。1b3b2b4b5b6b7b8b网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-977例例 子子选择支路 b2、b3、b4、b8 为树枝,则 b1、b5、b6、b7 为连枝,于是重新列写矩阵 A 为: 10010100100000010100100100101110 76518432bbbbbbbbAAALT101000
50、00110011110TA01101000111101001TA网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-978例例 子子1100100101111000100110000100001001101000111101001LTAA 1 1TLTfAAB10001101010010100010001000010110LTfAAQ1 1 011001000100101000111001010000001返返 回回网络分析与综合网络分析与综合网络图论网络图论上一页上一页2022-6-979电网络的矩阵分析法电网络的矩阵分析法 支路阻抗矩阵支路阻抗矩阵 节点分析法节点分析法