1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2.1,图论的基础知识,七桥难题,1,2,3,4,6,5,7,A,B,C,D,怎样才能不重复地走过所有七座桥,再回到出发点?,如何“一笔画”出以上图形?,第二章 系统分析法,1,图论的基本定义和概念,拓扑图,:抽象实际问题得到的由点、线构成的几何图形,反映了点、边邻接关系。,图,是,边,(或支路,是图中的线段)和,点,(或节点,是支路的连接处或终端)的集合。,I,1,I,5,I,4,I,2,I,3,I,6,+,u,s,1,+,u,s,2,i,s,1,A,B,C,D,I,1,I,2,I,3,I,6,I,5
2、I,4,A,C,B,D,2,有向图,:各支路都有参考方向的图(电压降,电流方向);否则为,无向图,。,子图,:若图,G,包含有图,H,所有的点集和边集,则称图,H,为图,G,的一个子图,图,G,为图,H,的,母图,。,连通图,:全部节点都为支路连通的图;否则称为,非连通图,。分离部分的个数称为,分离度,。,图,G,图,H,无向图,有向图,3,平面图,:若,图能表示在一个平面上,使得图的任意两条边仅仅在它们的公共节点上相交,则图称为,平面图,;否则为,非平面图,。,平面图,非平面图,4,回路,:由一组支路构成的闭合路径。,秩,:图,G,节点数为,n,,分离度为,k,,则称,R,=,n,k,为图
3、G,的,秩,。,表示连通图中不包含起点的所有节点数。,零度,:图,G,为有,n,个节点,,b,条支路的连通图,则称,L,=,b,n,+1,为图,G,的,零度,。,表示独立回路的个数。,I,1,I,2,I,3,I,6,I,5,I,4,A,C,B,D,R=,4,1=3,L,=6 4+1=3,b,=6=,R,+,L,5,树,:连接所有节点但不包含回路的子图。,树支,:,构成树的边称为,树支,。,连支,:不属于树支的边称为,连支,。,6,基本回路,:仅含一条连支的回路为,基本回路,。,割集(,cut-set,),:能被切割,/,移去而使连通图分为两个分离部分的一组最少数量的边的集合。,如果切割,/,
4、移去这些支路,就会使图成为两个分离部分,只要少切割,/,少移去其中任一支路,图仍然连通,A,B,C,D,1,2,3,4,5,A,B,C,D,2,3,4,A,B,C,D,1,3,7,基本割集,:仅含一条树支的割集为,基本割集,。,A,B,C,D,1,2,3,4,5,A,B,C,D,1,2,3,4,5,(2,4,5),不是基本割集,8,重要的数量关系:,在分离度为,k,、点数为,n,、边数为,b,的图中,秩,R,=,n,k,不含起点的节点数,树支数,基本割集数,零度,L,=,b,R,=,b,n,+,k,独立回路数,连支数,基本回路数,连通图:,R,=,n,1,L,=,b,n,+1,9,连通图中,R
5、n,1,的证明:,(,1,),R,=1(,n,=2),:只有,1,个树支,,2,个节点,必然成立。,(,2,)设,n,=,n,0,R,=,n,0,1,成立,,则增加,1,个点,(,n,=,n,0,+1),,对于连通图,必然增加,1,个树支,即,R,=,n,0,1+1=,n,1,也成立。,L,=,b,n,+1,的证明:,因为图的支路由树支与连支组成,,显然,对于支路数为,b,、树支数为,R,(=,n,1),的连通图,,连支数必为:,L,=,b,R,=,b,n,+1,10,对于连通图(,n,个点、,b,条边),树支数:,t,=,n,1,(,=,秩,=,基本割集数),连支数:,L,=,b n,
6、1,(,=,零度,=,基本回路数),对于非连通图(,分离度,k,,,n,个点,,b,条边),树支数:,t,=,n,k,(,=,秩),连支数:,L,=,b,n,+,k,(,=,零度),例:,(,连通图),:,n,=4,,,b,=5,则,t,=3,,,L,=2,A,B,C,D,1,2,3,4,5,11,对于连通图(,n,个点、,b,条边),树支数:,t,=,n,1,(,=,秩,=,基本割集数),连支数:,L,=,b n,+1,(,=,零度,=,基本回路数),对于平面连通图(,n,个点、,b,条边),网孔数:,m,=,b n,+1=,L,(连支数),A,B,C,D,1,2,3,4,5,12,用矩阵
7、表示有向图的节点与支路的连接关系,未连:,0,,进入:,1,,离开:,1,支路:,1 2 3 4 5,A,1000 1,节,B,11010,点,C,0 1100,D00 1,1,1,任一支路必进入一点、离开一点(任一列:,+1,、,1,),删除任一行,仍能充分反映连接关系,删除的一行对应的节点为,参考点,关联矩阵,关联矩阵:,A,B,C,D,1,2,3,4,5,A,=,1,0 0 0,1,1 1 0 1,0,0 1 1 0,0,13,A,B,C,D,1,2,3,4,5,A,=,1,0 0 0,1,1 1 0 1,0,0 1 1 0,0,关联矩阵(以,D,为参考点),支路,1 2 3 4 5,树
8、支,连支,=,A,T,A,L,设支路电流向量,I,=,i,1,i,2,i,3,i,4,i,5,T,则:,AI,=,1,0,0 0,1,1 1,0 1 0,0,1,1 0,0,i,1,i,2,i,3,i,4,i,5,i,1,i,5,i,1,+,i,2,+,i,4,i,2,+,i,3,=,=,0,0,0,KCL,的矩阵形式:,AI,=0,节点,A,B,C,14,关联矩阵(以,D,为参考点),支路,1 2 3 4 5,设支路电压向量,U,=,u,1,u,2,u,3,u,4,u,5,T,节点电压向量,U,N,=,u,A,u,B,u,C,T,A,T,U,N,=,1,1 0,0 1,1,0 0 1,0 1
9、 0,1 0 0,u,A,u,B,u,C,u,A,u,B,u,B,u,C,u,C,u,B,u,A,=,由节点电压得支路电压,:,A,T,U,N,=,U,u,1,u,2,u,3,u,4,u,5,=,=,U,A,B,C,D,1,2,3,4,5,节点,A,B,C,A,=,1,0 0 0,1,1 1 0 1,0,0 1 1 0,0,=,A,T,A,L,15,2.2,求解变量的选择,一 最多数量的变量和方程,设电路有,b,条支路,,,n,个节点,,,则 最多可有,2,b,个变量:,b,个,支路电压,,,b,个,支路电流,2,b,个,独立,方程:,n,1,个节点,/,基本割集,的,KCL,方程,b,n,+
10、1,个基本回路,/,平面图的网孔的,KVL,方程,b,个支路的,VCR,方程,求解电路的,2,b,法,16,二 最少数量的变量和方程,(,1,)变量是,独立,的,变量的数量最少,(,2,)变量是,完备,的,能求得其它所有的变量,方程必须满足:,与变量同样的数量,独立的方程,1,最少数量的变量必须满足:,17,2,以电压作为变量:,(,1,),变量的独立性,支路电压不能构成回路,树支电压(,n,1,个,),独立节点的节点电压(,n,1,个,),(,2,),变量的完备性,树支电压,通过基本回路的,KVL,连支电压,节点电压,节点电压之差为支路电压,(,3,),n,1,个独立方程,变量为树支电压,基
11、本割集的,KCL,方程 (割集法),变量为节点电压,独立节点的,KCL,方程 (节点法),18,3,以电流作为变量,(,1,),变量的独立性,支路电流不能构成割集,连支电流(,b,n,+1,个,),网孔电流(,b,n,+1,个,),(,2,),变量的完备性,连支电流,通过基本割集的,KCL,树支电流,网孔电流,网孔电流之差,/,和为支路电流,(,3,),b,n,+1,个独立方程,变量为连支电流,基本回路的,KVL,方程 (回路法),变量为网孔电流,网孔的,KVL,方程 (网孔法),19,节点法,网孔法,A,B,C,D,1,2,3,4,5,6,i,m1,i,m2,i,m3,适合于节点少的电路,适
12、合于网孔少的电路,独立的方程,n,1,个节点,KCL,方程,b,(,n,1),个网孔,KVL,方程,独立的变量,n,1,个节点电压,b,(,n,1),个网孔电流,变量完备性,之差为支路电压,之差,/,和为支路电流,20,割集法,回路法,A,B,C,D,1,2,3,4,5,6,独立的方程,n,1,个基本割集,KCL,方程,b,(,n,1),个基本回路,KVL,方程,独立的变量,n,1,个树支电压,b,(,n,1),个连支电流,变量完备性,可求连支电压,可求树支电流,21,以电流为变量,L,个连支电流为变量,(回路法),L,=,b,n,+1,L,个网孔电流为变量,(网孔法),,仅适合于平面图,以电压为变量,n,1,个,树支电压为变量(,割集法,),n,1,个节点电压为变量(,节点法,),22,作业,6,,,7,,,8,(第,8,题:题,a,以,E,为参考点,题,b,以,F,为参考点,,支路和节点均以序号递增排列),23,






