网络图论和网络方程

本章要求

一、重点掌握有关网络的拓扑图中的基本知识。

二、熟练掌握节点关联矩阵，基本回路矩阵和基本割集矩阵以及网孔矩阵的列写方法。

三、着重掌握网络图论中的节点分析法。

四、简介网络图论中的网孔分析法，回路分析法和割集分析法。

说明：补充教材中的§11-6

含受控源电路的节点分析法和§11-8灵敏度分析，不作要求。目前一页\总数二十三页\编于十九点概述图论的起源与发展1．哥尼斯堡七桥难题问题：能否从任一陆地出发，走遍七桥，且每桥只走一次，又回到原出发点。欧拉结论：实现一笔画的充要条件，奇次点数等于0或2。欧拉圈：奇次点数=0，从任一点出发，一笔画回到原出发点。欧拉路：奇次点数=2，一笔能画出来的路。

目前二页\总数二十三页\编于十九点2．哈密尔顿环球旅行问题1857年英国数学家哈密尔顿发明了一个玩具。一个木制的正12面体，每面是个五角星，三面交于一角，共20个角，每个角标注世界上一个重要城市。

问题：旅行者沿着12面体的边，找一条经过所有城市恰好一次而最后返回原来的出发城市的闭合回路。该回路称为哈密尔顿圈。目前三页\总数二十三页\编于十九点3．四色问题问题：一张画在球面或平面上的地图，相邻国家如果涂以不同的颜色，只用四种颜色是否足够？4．求电路的拓扑解问题

1845年，基尔霍夫提出了电路中两个最重要的定律KVL和KCL。目前四页\总数二十三页\编于十九点11-1网络的图一、网络的拓扑图

1.拓扑关系式实例设一电路如图uS1-+iS2R3R4L5C6i1abcd12i2i3i4i5i63结构数据：网孔数m=3；节点数n=4

；支路数b=6

。元件编号即为支路编号。2b法方程理论KCLKVLVCR｛｝取决于电路结构－取决于支路元件

选支路电压和支路电流为电路变量，设其为关联方向，沿网孔方向巡行有i1+i3-i2=0i4+i5-i3=0i6-i4-i1=0u1-u4-u3=0u2+u3+u5=0u4+u6-u5=0

此方程组只取决于电路结构。

将此方程组称为电网络的一组“拓扑”关系式。topology“拓扑”

汉译有“结构”之意。

结论：若已知电网络的结构，即可列出各支路电压和电流的一组拓扑关系式，此组关系式与各支路元件的种类和性质无关。目前五页\总数二十三页\编于十九点2.网络的拓扑图定义：

对一个电网络，为突出其结构特点，将电网络中的每个元件用一条线段代替后所得到的联接图形称为该电网络的拓扑图，简称网络的图，一般用G表示。123456G123456G123456G123456G

图的特点：

(1)图只保留原电网络的联接关系；

(2)图中的线段长短和曲直无关紧要。如uS1-+iS2R3R4L5C6i1acdi2i3i4i5i6b目前六页\总数二十三页\编于十九点也可以这样定义：由有限个点的集合以及连接两点的若干条线段所组成的图形。

—顶点集（节点）

—边集（支路）V={a,b,c,d}E={1,2,3,4,5,6}|V|=N顶（节）点数边数|E|=B

说明：

（1）关联相邻；

（2）几个元件可算作一个支路；（3）电路与拓扑图中的编号一致；（4）图的形状；（5）点和边的删除。目前七页\总数二十三页\编于十九点二、图的边(支路)、顶点(节点)

1.边(支路)：

图中所替代每个元件的线段称为图的边，或称图的支路。用B表示边数(支路数)

2.顶点(节点)：

图中每边的两个端点，或两个和两个以上边的联接点称为图的顶点，或称图的节点。用N表示顶点数(节点数)

。

注意：图中的节点与原基础理论中的节点不同，两个元件串联线段的联接点就是图中的一个节点(顶点)。

注意：图中的支路与原基础理论中的支路不同，代表每个元件的线段就是图中的一个支路(边)。目前八页\总数二十三页\编于十九点三、连通图、有向图和子图

1.连通图和非连通图

在图中的任两个节点(顶点)之间至少存在一条沿着支路(边)相连通的图称为连通图，否则称为非连通图。非连通图今后凡不特别指明时，皆为研究连通图。连通图·abcd目前九页\总数二十三页\编于十九点

2.有向图

所有支路都指定了方向的图，则称为有向图，在有向图中，支路方向用于表示电路中电压与电流的关联参考方向。uS1-+iS2R3R4L5C6i1abcdi2i3i4i5i6123456G有向图acbd两条规定：

(1)图中各边的方向与所对应电路中各元件上的电流方向一致；

(2)取各支路的电压与电流方向为关联方向。如ab3i3+-u3目前十页\总数二十三页\编于十九点

3.子图和补图实例123456acbdG=+c213abdG1456cbdG2

G1和G2的总和包括了G的全部支路和节点。

子图：如果图G1

是图G

的一部分，即G1中的每个支路和节点都是图G中的支路和节点，则称图G1为图G的一个子图。

G1和G2都是G的子图。目前十一页\总数二十三页\编于十九点

补图：123456acbdGc213abd子图G1互为补图

如果把一个图G

分成两个子图，而且两个子图中没有相同的支路，但它们共同包括了原图G

中的全部支路，则称此两个子图互为补图。456cbd子图G2如补图特点：(1)互补性只对支路而言；(2)互补的子图之间必有共同的节点。目前十二页\总数二十三页\编于十九点四、图的树

1.树的定义：

一个图G

的树是指具备下述3个条件的子图。

条件(1)：该子图包括原图G中的全部节点。

条件(2)：该子图是一个连通图。

条件(3)：该子图不含有回路。

包括原图中的全部节点，但不含有回路的一个连通子图称为原图的一个树，用T

表示。123456acbdG256acbdT1:{2,5,6}356acbd如集合写法36acbd4T3:{3,4,6}，T2:{3,5,6}，目前十三页\总数二十三页\编于十九点

2.树支、连支和树余(连支集)

(1)树支：组成树的每个支路称为树支，用T支表示。

(2)连支：对一个图G除去所选树的树支以外的每个支路称为连支，用L支表示。T支为2,5和6T支为3,5和6L支为1,3和4L2:{1,2,4}L支为1,2和4

(3)树余(连支集)：与树互补的子图称为树余，又称连支集，用L表示。L1:{1,3,4}树支：连支：树余：256acbdT1:{2,5,6}356acbdT2:{3,5,6}123456acbdG如目前十四页\总数二十三页\编于十九点316c

3.找树的方法

先选取一个支路为树支，然后每次增加一个支路，直到再增加新的树支就要构成回路为止。123456acbdG如5b2ad

为此，树也可定义为：构成一个不含回路的连通子图的最多支路集。

4.树数、树支数和连支数

(1)树数：是指一个图中所含树的数目，用T数表示。对任意两个顶点都有边的完全图，可有N为节点(顶点)数如图G为完全图，N=4N-2T数=N则T数=44-2=16即，对图G可有16个树。4目前十五页\总数二十三页\编于十九点

(2)树支数：是指一个树中所含支路的数目，用T支数表示。T支数=N-1123456acbdG如N=4每个树中的支路数为

T支数=4-1=3256acbdT1:{2,5,6}356acbdT2:{3,5,6}36acbd4T2:{3,4,6}

(3)连支数：是指构成树余中所含支路的数目用L支数表示。L支数=B-(N-1)=B-N+1如图G中B=6,N=4L支数=6-4+1=3目前十六页\总数二十三页\编于十九点c3a2

例题已知：电路结构和各支路电流如图。求:(1)画出该电路的有向图。

(2)找出该图的4个树和相应的树余(连支集)。

(3)

写出该图的树数T数。解：(1)有向图abcd123456(2)找4个树和相应树余b1d

T支数=4-1=3

T1:{1,2,3}

L1:{4,5,6}连支集d5c3a2b

T2:{2,3,5}

L2:{1,4,6}连支集c45b1da

T4:{1,5,4}

L4:{2,3,6}树余d5c3a4b

T3:{3,4,5}

L3:{1,2,6}树余(3)树数N-2T数=N=44-2=16R2R3R5R6R4bdac+-uSi1i2i3i4i5i6目前十七页\总数二十三页\编于十九点回路：

从图中的某一个顶点出发，沿着边和顶点不重复地巡行一周回到原出发的顶点所得到的闭合路径称为回路。回路数用M表示。练习题电网络为下图，各元件下标按序编号。IS1L3L2R4R6R5C7C8abcdgefM**(1)画出该电网络的图(2)支路(边)数B=8。(3)节点(顶点)数N=7。(4)回路数M=4。23678abcdefg145五、回路和基本回路目前十八页\总数二十三页\编于十九点从图中任一节点出发，沿支路循行一周，又回到原出发点的闭合路径。也可定义为：

…

环加（求和）：两个集合相加去掉公共部分。

独立回路

｛自然网孔

每选一个新回路，至少包含一个新支路基本回路

目前十九页\总数二十三页\编于十九点基本回路：一个连支+若干树支组成的回路

基本回路数=连支数=b-n+1

基本回路方向与连支方向一致

基本回路环加可以求得一个图的全部回路

（

100

010

001

110

011

101

111

0000无效回路L个基本回路

有效回路数为

目前二十页\总数二十三页\编于十九点六、割集和基本割集割集：可将一连通图分割为两个连通部分的极小边集

Q1=｛