电网络理论2013第二章图论

第2章网络图论基础§2-1图论的基本知识•图(Graph)图是拓扑（Topological）图的简称节点和支路的一个集合分类：无向图：未赋以方向的图。混合图：只有部分支路赋以方向的图。有向图：所有支路都赋以方向的图。::图并不反映支路之间的耦合关系。二端元件的图三端元件的图双口元件的图1321i2i213－＋－＋1u1i2u2i12元件的图连通图•连通图如果图G中的任何两个节点之间都至少存在一条路径，则G称为连通图(ConnectedGraph)，否则称为非连通图。•铰链图由电路中的多口元件造成的非连通图，可以把不连通的各部分中的任一节点(一部分只能取一个节点)之间假设有一条短路线相连。把这些假设短路线连接的节点合并成一个节点，这样所得的图称为铰链图(HingedGraph)。铰链图示例•可断图若将连通图G中的一个节点移去后(把一个节点移去意味着把它以及与它相连的支路全部移去)所得子图不再连通，则称该节点为可断节点。含有可断节点的图称为可断图(SeparableGraph)。12345铰链图原图12354子图如果图G1中的每个节点和每条支路都是G图中的一部分，则称G1为G的子图(Subgraph)。141122233442134回路线树星树•回路、树和割集•回路(Loop)(1)是连通的(2)Gl的每个节点都连接着两条支路。•树(Tree)(1)Gt是连通的；(2)Gt包含的所有节点；(3)Gt不包含回路。补树•余树或补树图G中对应树T的余子图称为余树或补树(Cotree).•树支和连支构成树的支路称为树支(TreeBranchorTwig)其余的支路称为连支(ChordorLink)。163452163452163452补树图若连通图G存在树的补树T也是G的一个树，则称为补树图(ComplementarytreeGraph),或具有补树结构(ComplementarytreeStructure)。•2-树移去树中的任一支路后所得子图称为图G的2-树(2-tree)。•生成子图(SpanningSubgraph)包含图G所有节点的子图。::树和2-树均为生成子图。afdgebhcTabcdcTefgh补树图割集•割集(Cutset)：一组支路(1)移去这组支路后，图变为两个分别连通的子图(2)任意留下这组支路中的一条支路，图仍然是连通的。::割集是把一个连通图分成两个连通的子图所需的最少支路。123456123456123456123456基本回路与基本割集•基本回路(FundamentalLoop)只含有一条连支的回路（单连支回路）::基本回路数＝连支数•基本割集(FundamentalCutset)只含有一条树支的割集（单树支割集）::基本割集数＝树支数145236425254123456§2-2图的矩阵表示及其性质•有向图拓扑性质的描述：（1）关联矩阵(IncidenceMatrix)（2）回路矩阵(LoopMatrix)（3）割集矩阵(CutsetMatrix)一、关联矩阵•任一元素aij定义为1ji1ji0jiija表示支路与节点关联，且方向为离开节点表示支路与节点关联，且方向为指向节点表示支路与节点非关联•Aa的秩定理:对于任意n个节点、b条支路的有向连通图，它的关联矩阵Aa中有(n－1)个线性无关的行，即Aa的秩为(n－1)。(增广）关联矩阵Aa关联矩阵（续）(降阶)关联矩阵A若把Aa中的任一行划去(相当于相应的节点选作参考点)，剩下的(n－1)×b矩阵足以表征有向图中支路与节点的关联关系，并且(n－1)行是线性无关的。这种(n－1)×b阶矩阵称为降阶(Reduced)关联矩阵，简称关联矩阵。::关联矩阵A的任何阶方子矩阵A0，detA0为0、1或－1幺模矩阵(UnimodularMatrix)一个矩阵如果它的每个方子矩阵的行列式值均为＋1、－1或0，则称该矩阵为单模矩阵或幺模矩阵.有关的定理对于n个节点的连通图G，G的关联矩阵A的一个(n－1)阶子方阵非奇异的充分必要条件是此子方阵的列对应图G的一个树的树支。tAdet1tAtA::一个树的关联矩阵是非奇异的，且大子矩阵(MajorSubmatrix)一个秩为n的n×m矩阵的大子矩阵定义为该矩阵阶数为n的非奇异子矩阵。::At为大子矩阵。树的数目的计算方法•比内—柯西(Binet-Cauchy)定理设矩阵B为m×n阶矩阵，C是n×m阶矩阵，且m＜n，则所有大子式与CB)det(TAA22)1()det(非零大子式）的（树的数目全部非零大子式AAATdet(BC)＝的对应大子式的乘积结论：设图G是连通的，其关联矩阵为A，则全部树的数目为。二、基本回路矩阵Bf•任一元素bij定义ij0ij1ij1非关联与基本回路表示支路关联，且二者方向相反与基本回路表示支路关联，且二者方向一致与基本回路表示支路ijb基本回路的方向与其关联的连支的方向相同。::回路矩阵的性质连通图G的回路矩阵的一个l×l子矩阵是大子矩阵的充分必要条件是:此子矩阵的列与图G的一个补树对应。三、基本割集矩阵Qf•任一元素qij定义为ij0ij1ij1非关联与基本割集表示支路关联，且二者方向相反与基本割集表示支路关联，且二者方向一致与基本割集表示支路ijq基本割集的方向与其关联的树支的方向相同。::割集矩阵的性质:连通图G的割集矩阵的一个大子矩阵与G的树具有一一对应关系。四、树的路径矩阵•定义：树T的路径与各树支的关联关系矩阵P，称为树的路径矩阵（PathMatrix）。•任意元素pij定义为ji0ji1ji1上不在路径表示支路上，且二者方向相反在路径表示支路上，且二者方向一致在路径表示支路ijp::矩阵P的特点：每行的非零元素具有相同的符号。路径矩阵示例与性质示例111101001P①②③213011110001tA100010001tPA1tAP五、矩阵A、Bf和Qf之间的关系对于任一连通图，在支路排列顺序相同的情况下，矩阵A、Bf和Qf满足正交关系(OrthogonalityRelations):0ABTf0ABTf0BQTff0QBTfftlAAAtlfB1Btlf1QQ按先连支、后树支的顺序对支路编号或者或者矩阵A、Bf和Qf之间的关系（续）0ABAB1AAABlTttTtltlTfltTtAAB1TtlBQ0ltTtlAABQ1lTtlPABQ即同理§2-3网络的互联规律性KCLKVL基尔霍夫电流定律（）基尔霍夫定律基尔霍夫电压定律（）功率守恒特勒根定理拟功率守恒差分形式回路－割集不相容原理★★★一、基尔霍夫定律基尔霍夫电流定律(KCL)：电荷守恒基尔霍夫电压定律(KVL)：能量守恒表示矩阵AfbBu0fbQi0bAi0lTfbiBifQnTbuAufBtTfbuQuKCLKVL定律基尔霍夫定律的矩阵形式二、特勒根定理1.功率守恒定律对于一个具有n个节点、b条支路的网络，令ub和ib分别表示支路电压列向量和支路电流列向量，且各支路的电压和电流采用关联参考方向，则0bTbbTbuiiu01bkkkiu或者功率守恒定律的证明0Tbbui01bkkkiu或者TbnuAuKVL：TTbnuuATTTbbnbnbuiuAiuAi利用KCL：bAi00Tbbiu功率守恒定律的证明同理ˆAAˆbiˆˆ0TTbbbbuiiu1ˆ0bkkkui1ˆ0bkkkui扩展：ˆˆ0TTbbbbuiiuTTbnuuAˆTTbnuuAˆˆˆˆˆTTTbbnbnbuiuAiuAi利用KCL：ˆˆbAi02.拟功率守恒定理设网络N和具有相同的拓扑结构(即),支路电压列向量和支路电流列向量分别为ub、ib和、,则有NˆAAˆbuˆbiˆ0ˆˆbTbbTbuiiu0ˆˆbTbbTbuiiu0ˆ1bkkkiu0ˆ1bkkkiu或者3.特勒根定理的差分形式设网络N和具有相同的拓扑结构，在t时刻，的支路电压和电流分别为和，N的支路电压和电流的变化量分别为和，则Nˆbuˆbiˆbubi0ˆˆbTbbTbiuui1ˆˆ0bkkkkkiuui或者一条支路Nˆ功率守恒定律的证明同理ˆbiTbbnnuuAuuKVL：利用KCL：ˆˆˆˆˆTTTbbnbnbuiuAiuAiˆˆbAi0TbnuAuˆ0Tbbuiˆ0Tbbiuˆ0Tbbui0ˆˆbTbbTbiuui1ˆˆ0bkkkkkiuui或者三、基尔霍夫定律和特勒根定理的广义形式•线性变换变换称为线性的，是指对于任意实数α和β)(L)()()(2121xLxLxxL0)0(LdtetfjFtj)()(dejFtftj)(21)(::常用线性变换反变换(1)傅立叶变换正变换常用线性变换（续）(2)相量变换tjetFjtFF2)sin(2)cos(2)2Re()(tjeFtf)2Im()(tjeFtf0)()(dtetfsFstjjstdsesFjtf)(21)((3)拉普拉斯变换或反变换正变换正变换反变换(4)其它线性变换一维变换：取增量、取共轭、小波变换多维变换：派克变换、相模（解耦）变换、相序变换等基尔霍夫定律和特勒根定理的广义形式变换域的KCL方程和KVL方程1()bLAi0)()(22nTbLLuAubAI0TbnUAUfbBU0lTfbIBIfbQI0tTfbUQU0IUbTb记为由基本回路矩阵和基本割集矩阵表示的基尔霍夫定律的广义形式特勒根定理的广义形式多口网络的特勒根定理设n口网络的端口电流列向量ip为，端口电压列向量为up，内部b条支路的电压、电流列向量分别为ub和ib，则由特勒根定理得0bTbpTpiuiubTbpTpiuiubkkknipipiiuiu11bTbpTpIUIUbkkknipipiIUIU11•变换域n口网络的特勒根定理为即标量方程形式为或者四、着色边定理（ColoredBranchTheorem）•给定一有向图G,任取一条支路着成深绿色，其它支路任意着上红色、蓝色或绿色(至少有1条支路着绿色）。由此得到的图称为有向着色图(DirectedColoredGraph)。则下述两条中有且仅有一条成立:(1)存在一个由深绿色支路及绿色支路和／或红色支路形成的回路,该回路中所有绿色支路的方向皆相同,即它们的方向都与回路的方向一致或相反。(2)存在一个由深绿色支路及绿色支路和／或蓝色支路形成的割集,该割集中所有绿色支路的方向皆相同,即它们的方向都与割集方向一致或相反。着色边定理示例形成定理中的割集b5r8b4b3g1g*g2r1r6*125{,,,}gggb不存在定理中的回路！r12g*g1b10b9b3b8g2b7g5r4r6r11不存在定理中的割集！着色边定理的备注（3条）(1)有向图中支路的着色是任意的,但只能有一条支路着成深绿色。(2)有向图中至少有一条支路着绿色。但是,红色支路集和蓝色支路集可以是空集（有向着色图中不存在红色支路和／或蓝色支路）。(3)定理中所提到的那种回路和割集并不是唯一的。推论：回路－割集不相容原理::同方向回路(SimilarityDirectedLoop)该回路中的所有支路的方向皆相同,即它们的方向都与回路的方向一致或相反。::同方向割集(SimilarityDirectedCutset)该割集中的所有支路的方向皆相同,即它们的方向都与割集的方向一致或