《第2章图论讲解》由会员分享，可在线阅读，更多相关《第2章图论讲解（43页珍藏版）》请在金锄头文库上搜索。
1、第二章 网络图论,图论是工程数学的分支，在许多其他领域均有应用。 如：城市规划，交通，系统工程，物流，医学等,第一节 网络与图 第二节 图的基本概念 第三节 关联矩阵、回路矩阵、割集矩阵 第四节 路径矩阵 第五节 矩阵A、B和Q的关系,第一节 网络与图,图 点和线的集合（二元关系）； 反映网络的拓扑结构，与元件无关。,1、 KCL：在节点上的支路，KVL：回路上的支路； 2、方向：信号的转移。,第二节 图的基本概念,一、图与子图 图 G =（V，E） 支路连接两个节点： 相邻 两节点（同类）， 节点与支路关联（非同类）,图G的一个子图Gs ,Gs G , GS中节点VS与支路ES均属于G中的一
2、部分，分别是V，E的子集。 若 VS = V，GS称为G的生成子图。,二、全通图、连通图及分离图,全通图：G中任意两节点均有支路.,连通图：任意两节点间均至少有一条路径（支路序列）.,三、平面图、有向图及无向图,平面图：可使各支路不相交；否则为非平面图,有向图：各支路标有方向图 无向图： 各支路无方向图,四、断点与可断图,G中任一节点移去时，与之相连的所有支路必须同时移去， 由此所得的子图不再连通了，该点就称为断点。 具有断点的图称为可断图。,五、路径、树和树支、连支和补树、林,路径：两节点的通路，有始端点和终端点，各节点和支路只能出现一次； 有向图与无向图有差别，有向图不能逆向走。,林：分离
3、图G的各部分子图的树构成林；K个分离部分构成K个树的林。,树和树支：连接所有节点，但不构成回路的最少支路集合； 至少有两个悬挂节点，树中支路称树支,树支数=n-1。,连支和补（余）树：G中除去树支以外的支路为连支，连支数=b-(n-1); 连支的集合称为补（余）树。,六、 单连支回路（基本回路）和单树支割集（基本割集）,树支: 1、2、 3; 连支：4、5、6 单连支回路: l1(1、2、4) ， l2(2、3、5)， l3(1、3、6) 单树支割集: c1(1、4、6)， c2(2、4、5)， c3(3、5、6),若按2、4、5为树支，1、3、6为连支，情况如何？,一、 关联矩阵 图G的节点
4、与支路的关系数字化，用矩阵的形式表示。,第三节 关联矩阵、回路矩阵、割集矩阵,节点和支路关联性,图的拓扑结构用nb的矩阵描述,-1 -1 0 1 0 0,0 0 1 -1 -1 0,1 0 0 0 1 1,0 1 -1 0 0 -1,1 支路k与结点j 关联，方向背离节点;,-1 支路k与结点j 关联，方向指向节点;,0 支路k与结点j无关.,A为降阶的关联矩阵(n-1)b,增广矩阵,关联矩阵,选支路1、2、3为树支，则,例,选树支: 1、2、 3; 连支：4、5、6; 列写Aa 和A.,二、 回路矩阵 图G中的回路与支路的关系矩阵。,基本回路矩阵Bf,2. 支路排列顺序为先树支后连支， 3.
5、 回路顺序与连支顺序一致,1 支路j 在回路i中方向一致;,-1 支路j 在回路i中方向相反;,0 支路j 不在回路i中.,(描述基本回路和支路的关联性质),规定： 1. 连支电流方向为回路电流方向,l b的矩阵描述,1 2 3,1 -1 0 1 0 0,1 -1 1 0 1 0,0 1 -1 0 0 1,= Bt 1l ,选树支: 4、5、 6;,基本回路（单连支回路）矩阵：,例 列写基本回路（单连支回路）矩阵.,选树支: 1、2、 3,定理1:,由A可得B：,三、 割集矩阵 主要讲单树支割集矩阵，也称基本割集矩阵Qf 。,基本割集与支路的关联性质,规定：(1)割集方向为树支方向 (2)支路
6、排列顺序先树支后连支 (3)割集顺序与树支次序一致,1 支路 j 在割集i中且与割集方向一致,-1 支路 j 在割集i中且与割集方向相反,0 支路 j 不在割集中,1 0 0 -1 -1 0,0 1 0 1 1 -1,0 0 1 0 -1 1,C1:1,2,4 C2:1,2,3,5 C3:2,3,6,选树支: 4、5、 6,例 选树支: 1、2、 3, 列写Qf .,基本割集?,定理2,由A可得Q：,四. 拓扑矩阵及KCL、KVL方程,约定,假设支路电流与支路电压的参考方向相关联, 电压源支路的电压参考方向从电源的正端指向负端， 电流源支路的电流参考方向与电流源的电流方向相同。,设:,1. 关
7、联矩阵与KCL、KVL,矩 阵形式的KCL: A i = 0,A i =,矩阵形式KVL ：,1 0 0 -1 -1 0,0 1 0 1 1 -1,设,矩阵形式的KCL： Q i =0,0 0 1 0 -1 1,树支电流用连支电流表示,2. 割集矩阵与KCL、KVL,选树支: 4、5、 6,矩阵形式的KVL： Qf Tut= u,连支电压用树支电压表示,l b的矩阵描述,1 2 3,1 -1 0 1 0 0,1 -1 1 0 1 0,0 1 -1 0 0 1,= Bt 1l ,3. 回路矩阵与KCL、KVL,设,矩阵形式的KVL： Bf u = 0, Bf u = 0 可写成,Btut+ul=
8、0,ul= - Btut,矩阵形式的KCL： Bf T il = i ,Bf= Bt 1 ,树支电流用连支电流表出,设,则 Bf T il = i ,Qf,Qf i=0,QfTut=u,小结：,ul= - Btut,A,Bf,KCL,Ai = 0,BTil=i,KVL,ATun=u,Bfu=0,l1 l2 l3,1 -1 0 1 0 0,-1 0 1 0 1 0,0 - 1 1 0 0 1,1 0 0 -1 1 0,0 1 0 1 0 1,0 0 1 0 -1 -1,练习 列写基本回路矩阵和基本割集矩阵。,选树支: 3、4、 5,矩阵A、Bf和Qf的关系,关联矩阵与回路矩阵，以及割集矩阵与回路
9、矩阵并不是独立的，存在如下关系：,设连通图G，按先树支后连支顺序编号，各矩阵可分解成相应的子矩阵，即,则可得,或：,又,于是矩阵Bf和Qf均可由关联矩阵A获得，即 :,关于独立变量,连枝电流可作为电路的独立电流变量，此时独立电流源支路（电流是独立的）应该作为连枝 ；,树枝电压可作为电路的独立电压变量，此时独立电压源支路（电压是独立的）应该作为树枝 。,因为设树支电流向量为it ，连支电流向量为il ，利用割集矩阵有,同理：设树支电压向量和连支电压向量分别为ut和ul ，利用回路矩阵有,（1）将独立电压源作为树枝，独立电流源作为连枝；,扩展矩阵,（2）按树的规则完成一个树的选择；,（3）先从独立
10、电压源支路开始，完成对树枝的编号；,（4）再对连枝进行编号，其中将电流源支路的编号放在最后.,一般原则如下：,按照以上规则列写的矩阵称为扩展的矩阵并用下标“a”表示。,Aa,Ba,Qa,例 列写图示电路扩展的割集矩阵。,解 选1、2、3、4为树支，c1、c2、c3、c4为对应的基本割集，扩展的割集矩阵为,分别与电压源 和电流源支路有关。,第四节 路径矩阵,由图G选一个树和参考节点，从各独立节点至参考节点的路径上，各支路与节点的关联矩阵，称路径矩阵。,支路,节点,例1,特点：每行非零元素同号；对支路2、移去后分为两部分， 点0只能在某一部分，左边部分各节点以同一方向 经过支路2，右边部分各节点以
11、反方向经过支路2。,例2,节点,支路,路径矩阵为求At-1提供了方便。,证明：,在原图G中，从参考节点至每个独立节点增加一个支路，方向为离开参考节点，增加的这些支路只能为连支。,连支,支路,第五节 矩阵A、B和Q的生成,一、A的生成,将G送入计算机： 支路号 始节点 终节点,3,建立一个数组:A(n-1, b) 支路1：A(1,1)=1 A(2,1)=-1 支路2：A(1,2)=0 A(2,2)=1 ,A的生成求树,1 2 3 4 5 6 7 8,由A经一系列行变换：,第一行加到第四行； b. 第四行乘（-1）与第二行互换； c. 第四行乘（-1）与到第三行互换； d. 第四行加乘（-1）。,1 2 3 4 5 6 7 8,再经列变换：第四行与第五行互换，,1 2 3 5 4 6 7 8,可知支路1、2、3、5是树支。,由A可求得Q和B。,习题 选图中支路1、2、3为树支，列写A、Bf、Qf、P 矩阵。,
