网络图论和网络方程课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《网络图论和网络方程课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络图 网络 方程 课件
- 资源描述:
-
1、2023-1-10电网络分析第二章顶点(节点)顶点(节点):线段的端点或孤立的点称为顶点或节点,:线段的端点或孤立的点称为顶点或节点,顶点用符号顶点用符号v表示表示;边(支路)边(支路):连接两个顶点连接两个顶点vi、vj的一条线段称为边或支的一条线段称为边或支路。边用顶点的无序偶路。边用顶点的无序偶e=vi,vj表示表示;图(线图)图(线图):边和顶点的集合称为图或线图,其中所有边:边和顶点的集合称为图或线图,其中所有边连接于顶点。若用连接于顶点。若用E表示图中所有边的集合,表示图中所有边的集合,V表示图中所有表示图中所有顶点的集合,则这个图顶点的集合,则这个图G可以表示为可以表示为G=(V
2、,E);有向图有向图:若将图中所有的边标上一定的方向,称为有向图。:若将图中所有的边标上一定的方向,称为有向图。有向边有向边a用其顶点用其顶点vi、vj的有序偶的有序偶a=(vi,vj)表示表示。若用若用A表示图表示图中所有边的集合,中所有边的集合,V表示图中所有顶点的集合,则这个图表示图中所有顶点的集合,则这个图Gd可可以表示为以表示为Gd=(V,A)第二章第二章 网络图论和网络方程网络图论和网络方程 21 网络的图和图论基本术语网络的图和图论基本术语2023-1-10电网络分析第二章相关联和相邻接相关联和相邻接:如果边联接着两个顶点,则称边与这两:如果边联接着两个顶点,则称边与这两个顶点个
3、顶点相关联相关联;如果两个顶点之间至少存在一条边,则两;如果两个顶点之间至少存在一条边,则两个顶点是个顶点是相邻接的顶点相邻接的顶点;如果两条边至少有一个公共顶点,;如果两条边至少有一个公共顶点,则称两条边为则称两条边为相邻接的边相邻接的边。顶点的次数(维数)顶点的次数(维数):与顶点相关联的边的数目。:与顶点相关联的边的数目。孤立顶孤立顶点点的次数为的次数为0,次数为,次数为2的顶点称为的顶点称为简单顶点简单顶点。子图、互补子图:子图、互补子图:子图的每一个顶点和边都是原图的顶点子图的每一个顶点和边都是原图的顶点和边;两个子图没有相同的边,但共同包含原图的全部边和边;两个子图没有相同的边,但
4、共同包含原图的全部边和顶点,这样的两个子图称为互补子图。和顶点,这样的两个子图称为互补子图。第二章第二章 网络图论和网络方程网络图论和网络方程 21 网络的图和图论基本术语网络的图和图论基本术语2023-1-10电网络分析第二章通路通路:由:由m条边和条边和m+1个顶点通过个顶点通过m条边依次连通,且条边依次连通,且m+1个顶点中除始个顶点中除始端和终端是端和终端是1次外,其余各顶点均为次外,其余各顶点均为2次的,这样的子图称为通路。通路所次的,这样的子图称为通路。通路所包含的支路数包含的支路数m称为通路的长度。称为通路的长度。回路和自环回路和自环:通路的始端顶点和终端顶点重合,这种闭合的通路
5、称为回:通路的始端顶点和终端顶点重合,这种闭合的通路称为回路或环;一个回路所包含的支路数称为回路的长度,任何回路的长度等于路或环;一个回路所包含的支路数称为回路的长度,任何回路的长度等于回路所包含的节点数;长度为回路所包含的节点数;长度为1的回路称为自回路,即自环。的回路称为自回路,即自环。连通图连通图:任意两个顶点之间至少有一条通路的图称为连通图,否则就是:任意两个顶点之间至少有一条通路的图称为连通图,否则就是非连通图。非连通图。完备图完备图:任何一对顶点之间有且仅有一条边。:任何一对顶点之间有且仅有一条边。可断图可断图:如果一个连通图:如果一个连通图G存在着这样一个存在着这样一个顶点,将该
6、顶点移去后(移去该顶点及相关联顶点,将该顶点移去后(移去该顶点及相关联的边),使的边),使G成为一个非连通图,这样的顶点成为一个非连通图,这样的顶点称为断点,含断点的连通图称为可断图。称为断点,含断点的连通图称为可断图。第二章第二章 网络图论和网络方程网络图论和网络方程 21 网络的图和图论基本术语网络的图和图论基本术语2023-1-10电网络分析第二章树和树余树和树余:包含连通图的全部顶点而不包含任何回路的子图:包含连通图的全部顶点而不包含任何回路的子图称为连通图的树,在树中,任意两个顶点之间仅有称为连通图的树,在树中,任意两个顶点之间仅有1条通路;条通路;在连通图中与树互补的子图称为树余。
7、树中所含的边称为树在连通图中与树互补的子图称为树余。树中所含的边称为树支,树余中所含的边称为连支。支,树余中所含的边称为连支。林和余林:在由林和余林:在由s 个分离部分组成的非连通图中,各分离部个分离部分组成的非连通图中,各分离部分的树的集合构成一个包含分的树的集合构成一个包含s 个树的林。林的补图称为余林。个树的林。林的补图称为余林。割集割集:若移去割集中所有的边,将使连通图分离为:若移去割集中所有的边,将使连通图分离为2个且仅个且仅有有2个彼此分离而又各自连通的子图,若保留割集中的任一条个彼此分离而又各自连通的子图,若保留割集中的任一条边不被移去,该图仍然是连通的。边不被移去,该图仍然是连
8、通的。基本割集基本割集:单树支割集。:单树支割集。基本回路基本回路:单连支回路。:单连支回路。第二章第二章 网络图论和网络方程网络图论和网络方程 21 网络的图和图论基本术语网络的图和图论基本术语2023-1-10电网络分析第二章定理定理2-1:在具有:在具有Nt个顶点,个顶点,B条边的连通图条边的连通图G中,任何中,任何一个树一个树T的树支数为的树支数为N=Nt-1,连支数为,连支数为B-N。定理定理2-2:对于具有:对于具有Nt个顶点,个顶点,B条边的连通图条边的连通图G,G中中关于任何一个树关于任何一个树T的基本割集数为的基本割集数为N,基本回路数为,基本回路数为B-N。第二章第二章 网
9、络图论和网络方程网络图论和网络方程 21 网络的图和图论基本术语网络的图和图论基本术语2023-1-10电网络分析第二章网络的图是表示网络结构(或拓扑性质)的图形,图的顶点(节点)网络的图是表示网络结构(或拓扑性质)的图形,图的顶点(节点)与边(支路)、回路与边、割集与边与边(支路)、回路与边、割集与边的关联性质都可以用矩阵的关联性质都可以用矩阵形式来表示。在网络分析中,利用图的矩阵表示,可方便地建立向形式来表示。在网络分析中,利用图的矩阵表示,可方便地建立向量形式的网络方程,也有利于用计算机辅助网络分析和设计。量形式的网络方程,也有利于用计算机辅助网络分析和设计。一、关联矩阵:一、关联矩阵:
10、增广关联矩阵增广关联矩阵Aa:Aa=aij 是一个是一个NtB的矩阵的矩阵1 1 0 ijjiiajiiji 第 支路与第 个节点相关联,且支路方向离开节点第 支路与第 个节点相关联,且支路方向指向节点第 支路与第 个节点无关联第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章定理定理2-3:一个节点数为:一个节点数为Nt的连通图,其增广关联矩阵的连通图,其增广关联矩阵Aa的秩为的秩为N=Nt-1。关联矩阵关联矩阵A:从:从Aa中去掉任一行所得到的矩阵称为关联矩中去掉任一行所得到的矩阵称为关联矩阵阵A。定理定理2-4:在增广关联
11、矩阵:在增广关联矩阵Aa中,对应于图中,对应于图G的任一回路的任一回路的列是线性相关的。的列是线性相关的。定理定理2-5:连通图:连通图G的关联矩阵的关联矩阵A的一个的一个N阶子矩阵是非奇阶子矩阵是非奇异的必要和充分条件是:此子矩阵的列对应于图异的必要和充分条件是:此子矩阵的列对应于图G的一个的一个树上的树支。树上的树支。tl AAA第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章二、回路矩阵二、回路矩阵:增广回路矩阵增广回路矩阵Ba:Ba=bij 是一个是一个LB的矩阵的矩阵,L为有向连通图为有向连通图G的回路数。的回路数。
12、1 1 0 ijjibjiji 第 支路与第 个回路相关联,且支路方向与回路方向相同第 支路与第 个回路相关联,且支路方向与回路方向相反第 支路与第 个回路无关联第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章定理定理2-6:对于一个具有:对于一个具有Nt=N+1个节点、个节点、B条支路的连通图条支路的连通图G,其增广回路矩阵的秩为其增广回路矩阵的秩为B-N。基本回路矩阵基本回路矩阵Bf:对于一个具有对于一个具有Nt个节点、个节点、B条支路的有向连通图条支路的有向连通图G,在选定,在选定一个树后,选取基本回路方向,使之与它所关
13、联的连支方向一一个树后,选取基本回路方向,使之与它所关联的连支方向一致。基本回路矩阵致。基本回路矩阵Bf是一个是一个(B-N)B矩阵,其元素矩阵,其元素bij定义如定义如下:下:1 1 0 ijjibjiji 第 支路与第 个基本回路相关联,且支路方向与基本回路方向相同第 支路与第 个基本回路相关联,且支路方向与基本回路方向相反第 支路与第 个基本回路无关联 ftl BB1第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章 三三、割集矩阵、割集矩阵:增广割集矩阵增广割集矩阵Qa:对于一个具有对于一个具有Nt个节点、个节点、B条支
14、路、条支路、C个割集的有向连通图个割集的有向连通图G,选定割集的方向,则增广割集矩阵是一个选定割集的方向,则增广割集矩阵是一个CB矩阵,它的矩阵,它的每一行对应于一个割集,每一列对应于一条支路,其元素每一行对应于一个割集,每一列对应于一条支路,其元素qij定定义如下:义如下:1 1 0 ijjiqjiji 第 支路与第 个割集相关联,且支路方向与割集方向相同第 支路与第 个割集相关联,且支路方向与割集方向相反第 支路与第 个割集无关联第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章定理定理2-7:具有:具有Nt个节点、个节点、
15、B条支路的有向连通图条支路的有向连通图G,其增广,其增广割集矩阵割集矩阵Qa的秩为的秩为N=Nt-1。基本割集矩阵基本割集矩阵Qf:Qf 是是一个一个NB矩阵,割集的方向与它所关联的树支方向矩阵,割集的方向与它所关联的树支方向一致,它的每一行对应于一个基本割集,每一列对应于一条一致,它的每一行对应于一个基本割集,每一列对应于一条支路,其元素支路,其元素qij定义如下:定义如下:1 1 0 ijjiqjiji 第 支路与第 个基本割集相关联,且支路方向与基本割集方向相同第 支路与第 个基本割集相关联,且支路方向与基本割集方向相反第 支路与第 个基本割集无关联 ftl Q1Q第二章第二章 网络图论
16、和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章四、邻接矩阵四、邻接矩阵:对于一个具有对于一个具有Nt个节点连通图个节点连通图G,节点之间的邻接关系可,节点之间的邻接关系可以用邻接矩阵以用邻接矩阵D来表示。来表示。D=dij是一个是一个Nt阶方阵,其行列均对阶方阵,其行列均对应于节点,其中每一元素应于节点,其中每一元素dij定义如下:定义如下:邻接邻接矩阵特点:矩阵特点:一个无向图一个无向图G,邻接矩阵为对称矩阵;当且仅当无自环时,邻接矩阵为对称矩阵;当且仅当无自环时,其对角线元素为零的对称矩阵;其对角线元素为零的对称矩阵;每一行(或每一列)所含每
17、一行(或每一列)所含1的个数是相应的节点次数的个数是相应的节点次数1 0 ijjidji第 个节点与第 个节点相邻接第 个节点与第 个节点不相邻接第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章五、矩阵五、矩阵A、Bf、Qf之间的关系之间的关系:矩阵矩阵A与矩阵与矩阵Bf之间的关系之间的关系:如果同一有向连通图的如果同一有向连通图的矩阵矩阵A和矩阵和矩阵Bf的列按相同的支路顺序排列,则的列按相同的支路顺序排列,则有:有:证明:令证明:令 如果将如果将A和和Bf的列按先树支后连支的顺序排列,基本回路的顺序与对应的的列按先树支后连
18、支的顺序排列,基本回路的顺序与对应的连支顺序一致。则连支顺序一致。则 ,TfAB0TfB A0 ftlBB1 tlAAATTT tftlttllBABAAA BA01第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示TfABC 11:0 2:0Bijikjkkijipjpimjmijca bijca ba b节点 不属于回路 节点 属于回路2023-1-10电网络分析第二章 因为因为At为非奇异的,则:为非奇异的,则:将上式两端取转置,有将上式两端取转置,有 ,因此,因此 因此,如果已知关联矩阵因此,如果已知关联矩阵A,则可由上式写出基本回路矩阵,则可由上式写出
19、基本回路矩阵Bf。T1ttl BA AT1ttl BA AT1 ftltll BB1A A1第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章 矩阵矩阵Bf与矩阵与矩阵Qf之间的关系之间的关系:如果同一有向连通图如果同一有向连通图G按照相同的支路顺序排列,则有:按照相同的支路顺序排列,则有:证明:令证明:令如果矩阵如果矩阵Qf和和Bf的列按先树支后连支的顺序排列,则有的列按先树支后连支的顺序排列,则有 ,那么,那么TffQ B0TffB Q0 ftlBB1 ftlQ1QTTT lltfftlt1B QB1BQ0Q第二章第二章 网
20、络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示TffQ BP 11:0 2:0Bijikjkkijimjminjnijpq bijpq bq b割集 与回路 无公共支路 割集 与回路 有公共支路(必为偶数)2023-1-10电网络分析第二章 因此:因此:因此有:因此有:Ttl BQTlt QBT lfl BQ1T -fttQ1B第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章 矩阵矩阵A与矩阵与矩阵Qf之间的关系之间的关系:因为:因为:所以:所以:当已知关联矩阵当已知关联矩阵A时,可根据上式写出基本割集矩阵
21、时,可根据上式写出基本割集矩阵Qf。T1ttl BA AT1tltl QBA A111 tttftltlQ1A AAAAA A第二章第二章 网络图论和网络方程网络图论和网络方程 22 图的矩阵表示图的矩阵表示2023-1-10电网络分析第二章一、基尔霍夫电流定律的矩阵形式一、基尔霍夫电流定律的矩阵形式 用关联矩阵用关联矩阵A表示的表示的KCL方程方程:用基本回路矩阵用基本回路矩阵Bf表示的表示的KCL方程方程:如果在图中选定一个树,支路的编号按先树支后连如果在图中选定一个树,支路的编号按先树支后连支的顺序,则关联矩阵和支路电流向量可分块为:支的顺序,则关联矩阵和支路电流向量可分块为:bAi=0
22、tlA=A Atl bii=i第二章第二章 网络图论和网络方程网络图论和网络方程 23基尔霍夫定律的矩阵形式和支路电压电流基尔霍夫定律的矩阵形式和支路电压电流关系的矩阵形式关系的矩阵形式以下研究的电网络限于线性时不变集总电网络。网以下研究的电网络限于线性时不变集总电网络。网络变量是电压、电流;依据:络变量是电压、电流;依据:KCL、KVL、VCR2023-1-10电网络分析第二章由于由于At是一个非奇异矩阵,所以有:是一个非奇异矩阵,所以有:由此看出,由此看出,B条支路电流中,只有条支路电流中,只有B-N个连支电流是独立的,个连支电流是独立的,树支电流可由连支电流决定,因此,连支电流是全部支路
23、电树支电流可由连支电流决定,因此,连支电流是全部支路电流集合的一个基底流集合的一个基底(basis)。考虑到矩阵。考虑到矩阵Bf与与A的关系,得到的关系,得到 该式就是用基本回路矩阵该式就是用基本回路矩阵Bf表示的表示的KCL方程的矩阵形式。方程的矩阵形式。tbtlt tl ll iAi=A A=A i+A i=0i-1ttl li=-A A i-1tTtlblflll i-A Ai=i=B ii 1第二章第二章 网络图论和网络方程网络图论和网络方程 23基尔霍夫定律的矩阵形式和支路电压电流基尔霍夫定律的矩阵形式和支路电压电流关系的矩阵形式关系的矩阵形式2023-1-10电网络分析第二章 用基
24、本割集矩阵用基本割集矩阵Qf表示的表示的KCL方程方程:由于矩阵由于矩阵Qf的每一行的非零元素表示与该行对应的基本割的每一行的非零元素表示与该行对应的基本割集所关联的支路及关联形式,因此:每一个基本割集所含集所关联的支路及关联形式,因此:每一个基本割集所含支路的电流的代数和为零。支路的电流的代数和为零。二、基尔霍夫电压定律的矩阵形式二、基尔霍夫电压定律的矩阵形式 用基本回路矩阵用基本回路矩阵Bf表示的表示的KVL方程方程:用基本割集矩阵用基本割集矩阵Qf表示的表示的KCL方程方程:如果在图中选定一个树,支路的编号按先树支后连支的如果在图中选定一个树,支路的编号按先树支后连支的顺序,则基本回路矩
25、阵顺序,则基本回路矩阵Bf和支路电压向量和支路电压向量ub可分块为:可分块为:fbQ i0fbB u0第二章第二章 网络图论和网络方程网络图论和网络方程 23基尔霍夫定律的矩阵形式和支路电压电流基尔霍夫定律的矩阵形式和支路电压电流关系的矩阵形式关系的矩阵形式2023-1-10电网络分析第二章于是:于是:由此看出,由此看出,B条支路电压中,只有条支路电压中,只有N个树支电压是独立的,连个树支电压是独立的,连支电压可由树支电压决定,因此,树支电压是全部支路电压支电压可由树支电压决定,因此,树支电压是全部支路电压集合的一个基底集合的一个基底(basis)。因此可以得到:。因此可以得到:该式就是用基本
展开阅读全文