网络分析与综合网络图论.

网络分析与综合——网络图论上一页2020/2/271在前面所学的“电工原理”等课程中，由于网络（即所谓的“电路”）结构比较简单，人们可以比较容易地利用“电工原理”中介绍的各种方法去求解网络参数。然而随着科学技术的不断发展和提高，网络的结构日趋复杂（支路数和节点数大大地增加），再用那些传统的方法来分析和设计已经是力不从心了，因此有必要寻找一种全新的系统化的即能够把计算机作为辅助计算工具的方法来进行网络分析和设计，这种方法就是网络图论。返回网络分析与综合——网络图论上一页2020/2/272图论虽然属于拓扑学的范畴，但是它的应用已渗透到许多学科领域，它在电路（网络）中的应用称为网络图论或网络拓扑。本章介绍图的一些基本知识，并结合电路分析的方法，应用网络拓扑的知识，系统地建立各种网络方程的基本矩阵形式，以便进行分析和计算。网络分析与综合——网络图论上一页2020/2/273本章主要内容图的基本知识拓扑矩阵电网络的矩阵分析法返回网络分析与综合——网络图论上一页2020/2/274图的基本知识图论的发展简史网络拓扑的基本概念树基本回路、基本割集基本回路割集基本割集割集分析法返回网络分析与综合——网络图论上一页2020/2/275图论的发展简史哥尼斯堡桥汉密尔登圈平面图与非平面图电网络方程四色定理返回网络分析与综合——网络图论上一页2020/2/276哥尼斯堡桥瑞士数字家欧拉（Euler）发表了一篇讨论哥尼斯堡（这是原十八世纪东普鲁士、现为立陶宛的一个城市）七桥（如图所示，其中A、B、C、D为四块陆地，其余为连接为四地的七座桥梁）难题的论文。ABCD网络分析与综合——网络图论上一页2020/2/277哥尼斯堡桥这篇论文讨论的主要内容是：从A、B、C、D任何一地出发，走遍七座桥，但每座桥只能经过一次（一笔画）。这个想法能不能实现？欧拉经过多次实验都没有成功；最后欧拉认为上述目的是无法实现的，并总结出一个通用判定准则：网络分析与综合——网络图论上一页2020/2/278哥尼斯堡桥⑴连接奇数个桥的陆地只有一个或超过两个以上时，不能实现一笔画；⑵连接奇数个桥的陆地仅有二个时，则从两者中的任一块陆地出发，可以实现一笔画，但终止在另一块陆地上；⑶每块陆地都接有偶数个桥时，则从任一块陆地出发都能实现一笔画，并且回到原出发点。网络分析与综合——网络图论上一页2020/2/279哥尼斯堡桥将陆地用点来表示，桥用线段来表示，就构成了一个图。要想一笔画出这个图，就要求这个图满足下面的条件：图必须是连通的，且每个顶点所关联的边的条数都是偶数，此时，一笔画的起点与终点相同；若其中仅有一对顶点关联的边数是奇数，则可以从这两顶点之一出发，终止于另一个顶点完成一笔画。网络分析与综合——网络图论上一页2020/2/2710哥尼斯堡桥哥尼斯堡七桥等效模拟图见图，由于该图中A、B、C、D四点所关联的边都是奇数，因而不可能实现不重复地走遍七座桥。欧拉最先一个实际问题化为一个图论的问题，并加以解决，所以后来人们公认欧拉为图论的创始人，把一笔画出来的路称为欧拉路。ABCDABCD返回网络分析与综合——网络图论上一页2020/2/2711汉密尔登圈英国数学家汉密尔登（Hamiltonian）发明了一种称为EulerTrail的游戏：在一个画在平面上有20个顶点的图中，把这20个顶点当作20个城市，旅行者从其中某一个城市出发，能否找出一条经过所有城市，但只能经过一次的闭合路径？回答是肯定的（如图中按从小到大的数字即1→2→3→…→19→20→1的路径就是满足要求的一条路径）。该回路称为汉密尔登圈，而含有汉密尔登圈的图称为汉密尔登图。网络分析与综合——网络图论上一页2020/2/2712汉密尔登圈1234567891011121314151617181920网络分析与综合——网络图论上一页2020/2/2713汉密尔登圈欧拉路与汉密尔登圈的区别：前者的一条路必须经过每一条边且只能经过一次，而经过各顶点的次数不限；后者的一条路必须经过每一个顶点且只能经过一次，而经过边的次数不限，也可以不经过。返回网络分析与综合——网络图论上一页2020/2/2714如果图中的所有边在顶点以外的地方均不相交，那么这个图就称为平面图，否则就是非平面图。判断一个图是不是一个平面图，可以看它是否满足公式：n–b+f=2（其中n、b、f分别为图的顶点数、边数和面数），如果满足，这个图就是平面图，反之，这个图就是非平面图。平面图与非平面图返回网络分析与综合——网络图论上一页2020/2/2715电网络方程如何确定及列出给定电网络的独立方程是较长时间困扰人们的问题。基尔霍夫（Kirchhoff）由树的概念提出了解决确定独立方程数的方法；还提出了列出集总（或分布）参数电网络的相应方程的两个基本方法：KVL（基尔霍夫回路电压定律）、KCL（基尔霍夫节点电流定律）。返回网络分析与综合——网络图论上一页2020/2/2716四色定理四色定理起源于对地图的染色：一个英国人提出，他只需四种颜色，就能使平面地图上任两个相邻国家的颜色不同，这里所谓的相邻是指两个国家有一段公共边界。将这个四色问题转化成图论的问题则为：用一个顶点代表一个国家，如果某二个国家相邻，就用一条线（边）将对应二个顶点连接起来，证明只需要有四种颜色，就可以使所有相邻的顶点有不同颜色，这就是四色定理（该定理在1976年得到了证明）。返回网络分析与综合——网络图论上一页2020/2/2717网络拓扑的基本概念节点的度子图通路连通图和非连通图回路图的定义及电网络图的表示与图有关的几个名词返回网络分析与综合——网络图论上一页2020/2/2718图的定义及电网络图的表示图：一组顶点与线段（边）的集合，边的两端终止于顶点，又称为“线图”，可用G（graph）表示。它把实际的网络结构用顶点和线段抽象地表示成几何图形。电网络中各支路两端的电压、流过各支路的电流之间的规律服从于定理KVL、KCL，它们只与网络的连接形式有关，而与各支路中所含的元件类型无关。网络分析与综合——网络图论上一页2020/2/2719图的定义及电网络图的表示3b①②③④1b2b4b5b6b图或线性图，还可以简称为“图”。为了习惯或方便，我们仍可称图中的顶点为节点（Node），称线段为支路（Branch）。我们用圆点表示节点（或称结点），用线段表示支路，这样就可以得到一个抽象的描述网络连接情况的图，把它称为网络的拓扑图，也可以称为线网络分析与综合——网络图论上一页2020/2/2720图的定义及电网络图的表示其中线段上没有方向箭头的图称为无向图；如果各线段上有箭头，它表示所对应支路的电流或电压降的参考方向的图称为有向图，又称为有向线图，在实际应用中，有向图用得比较多。6b①②③④1b2b3b4b5b6b①②③④1b2b3b4b5b3b①②③④1b2b4b5b6b返回网络分析与综合——网络图论上一页2020/2/2721与图有关的几个名词——节点的度G中某节点的度，表示与该节点相关联的支路数。如图中节点①、②、③、④的度都为3，因为与它们相关联的支路都有3条。6b①②③④1b2b3b4b5b返回网络分析与综合——网络图论上一页2020/2/2722与图有关的几个名词——子图G中的任一部分节点与支路的集合，可以用表Gs示（Sub-graph）。如图中节点①、②、③与支路b2、b4构成一个子图，节点①、②、③、④与支路b1、b5、b6构成一个子图，节点①、②、③、④与支路b3、b5也构成一个子图……。6b①②③④1b2b3b4b5b返回网络分析与综合——网络图论上一页2020/2/2723与图有关的几个名词——通路两个端节点，通过内节点及相应支路相连而构成的子图（或路径）。端节点：仅与一条支路相连的节点，它的度为1。内节点：与二条或二条以上的支路相连的节点，其度大于等于2（但通路的内节点的度只能为2）。网络分析与综合——网络图论上一页2020/2/2724与图有关的几个名词——通路在图中如果单看节点①、②、④与支路b1、b2就构成一条通路（其中节点②、④为端节点，节点①为内节点），节点①、②、③、④与支路b2、b3、b5也构成一条通路（其中节点③、④为端节点，节点①、②为内节点）。6b①②③④1b2b3b4b5b返回网络分析与综合——网络图论上一页2020/2/2725与图有关的几个名词——连通图和非连通图若G中任二个节点间至少有一条通路，则称G为连通图（ConnectedGraph），否则G为非连通图（UnconnectedGraph）。如图中节点①、②、④与支路b1、b2构成的子图和节点①、②、③、④与支路b1、b5、b6构成的子图都是连通图，而节点①、②、③、④与支路b3、b5构成的子图就是非连通图。6b①②③④1b2b3b4b5b返回网络分析与综合——网络图论上一页2020/2/2726与图有关的几个名词——回路通路的两端节点重合时形成的一个闭合路径就是回路（Loop或Circuit）。回路的特点是：当移去其中任何一条支路时，路径则没有闭合，或者它其中每个节点的度均为2。如图中节点①、②、③与支路b2、b3、b4构成的子图，节点①、③、④与支路b1、b3、b6构成的子图，节点②、③、④与支路b4、b5、b6的子图……。特殊地，一个节点和一条支路也可以构成一个回路，我们把它称为“自环”。6b①②③④1b2b3b4b5b返回网络分析与综合——网络图论上一页2020/2/2727树树在拓扑理论尤其在我们这里的网络拓扑中是一个非常重要的概念。网络拓扑中的树是一组支路及与它们相关节点的集合，对于每个连通图来说，其树的选择不是唯一的，而一旦确定了树以后，整个图就分成了树枝和连枝二部分：构成树的各支路称为树枝，而图中除树以外的剩余部分支路则被称为连枝，其集合又称为对应树的“补树”。返回网络分析与综合——网络图论上一页2020/2/2728树树的定义两种特殊类型的树：线树、星树树的几个基本定理返回网络分析与综合——网络图论上一页2020/2/2729树的定义包含有图G中所有节点但又无回路的连通子图。详细来说就是：具有n+1个节点，b条支路连通图G的一个连通子图，若具有下列特性中的任意两个：⑴包含图G的所有节点；⑵具有n条支路；⑶没有回路。这就是图G的一个树（Tree），可以用T表示。网络分析与综合——网络图论上一页2020/2/2730下面是左图所示网络的部分树。6b①②③④1b2b3b4b5b④①②③1b5b6b2b3b①②③④1b①②③④3b4b5b②③1b4b5b①④6b①②③④1b2b树的定义返回网络分析与综合——网络图论上一页2020/2/2731两种特殊类型的树——线树如果其所有树枝仅连成了一条通路（路径），那么这个树就称为线树，如下图所示的树；①②③④3b4b5b②③1b4b5b①④6b①②③④1b2b返回网络分析与综合——网络图论上一页2020/2/2732两种特殊类型的树——星树如果其所有树枝有一个公共的顶点，那么这个树就称为星树，如下图所示的树（它们的公共顶点分别是节点④和节点①）；④①②③1b5b6b2b3b①②③④1b返回网络分析与综合——网络图论上一页2020/2/2733树的几个基本定理定理一：每一个连通图G至少存在一个树：⑴如果G中不含有回路，则G就是一个树；⑵如果G中含有回路，那么在保证G连通的前提下，移去某一回路的一条支路，并按照这种方法，破坏掉所有的回路，剩下的就是树。定理二：若连通图中包含有n+1个节点，那么它的树必定有n条树枝。定理三：如果连通图G中的任意两节点之间，当且仅当存在一条通路（路径）时，则G就是一个树。网络分析与综合——网络图论上一页2020/2/2734树的几个基本定理定理四：在含有n+1个节点的连通图G中，若具有如下性质之一，则G就是一个树；反之，如果G是一个树，则它就具有以下性质：⑴G连通但没有回路；⑵G有n条支路，且无回路；⑶G连通，且含有n条支路；⑷G没有回路，但任意在两节点间加一条支路，就会出现一个回路；⑸G连通，但移去一条支路后，G就不连