网络图论简介

1.网络的图

对于任意一个集中参数元件组成的网络N，如果撇开元件的性质，只考虑元件间的连接情况，可将每一个元件用一条线段代替，仍称之为支路，将每个元件的端点或若干元件的连接点用一圆点表示，仍称之为节点。这样得到一个点、线的集合，称为网络N的图，用G表示。所以网络的图是一组节点和一组支路的集合，其中每一条支路的两端都连到相应的节点上。图8-1画出了两个网络及其图。

对于网络中的独立源和受控源，除了单独作为一条支路外，还可采用如下处理方法：将电压源（含受控电压源）连同串联的无源元件作为一个复合支路；将电流源连同并联的无源元件也作为一个复合支路，在图G中用一个支路表示。对于以无源元件为核心的复合支路的处理方法，在8.5节中将作介绍。

根据网络图的定义和绘制原则，网络的图只表明网络中各支路的连接情况，与元件的性质无关。所以，网络的图只是用来表示网络的几何结构（拓扑结构）的图形。网络图中的支路和节点与相应网络中的支路和节点一一对应，如图8-1（b）为图8-1（a）所示网络的图。由于网络中的互感是表示耦合电感内部的磁耦合关系，是属于元件的内部性质，而不属于网络的几何结构，因此在网络的图中不予反映的，如图8-1（d）为图8-1（c）所示网络的图。

在网络分析中，一般都要规定支路电流和电压的参考方向。在网络图中也规定了支路的参考方向。标明支路参考方向的图称为有向图，如图8-1（b）、（d）所示。没有标明支路方向的图称为无向图。

如果图8-2（b）所示图Ga中的每个节点和支路都是图8-2（a）图G中的节点和支路，则图Ga称为图G的子图。图8-2中的图Ga、Gb、Gc都是图G的子图。如果图G的两个子图包含了图G的全部支路和节点，并且又无公共支路，则称这两个子图互为补图。图8-2中，图Gb和Gc互为补图。

在图G中，与一个节点相关联的支路数称为节点的次数。图8-2（a）中的图G中节点的次数都是3。

在图G中，从一个节点出发连续经过不同的支路达到另一个节点，若这条通路中除了始节点和终节点的次数是1之外，其他中间节点的次数都是2，则这条通路称为路径。例如图8-2（a）的图G中，支路2、3 、6便构成节点①到节点②的一条路径。

图8-1　网络及其图

图8-2　图及其子图、补图

在图G中，任何两个节点间至少存在一条路径，则图称为连通图（见图8-1（b））；否则，称为非连通图（见图8-1（d））；在图8-1（d）中存在两个分离部分，不是所有节点间都有路径，例如节点①与节点④之间就没有路径存在，故称为非连通图。

如果路径的始节点和终节点相重合，则得节点次数都是2的闭合路径，称为回路。图8-2（a）的图G中，支路1、2、3就构成一个回路。

2.树和树余

在任一连通图G中符合下列条件的子图称为图G的树，用符号T表示：

（1）该子图是一连通图。

（2）该子图包含了图G的全部节点。

（3）该子图中不含有任何回路。

图8-3（b） 、（c） 、（d）所示子图T1 、T2 、T3都是图8-3（a）图G的树。

连通图G中与树互补的子图称为图G的树余。图8-2中子图Gc就是图G的树余。

树中的支路称为树支，树余中的支路称为连支。图8-3中的树T1的树支为4、5、6，相应的连支为1、2、3 。

根据树的定义，可得如下结论：

图8-3　图的树

（1）树的任何两个节点之间只可能存在一条路径，否则势必成回路；割断任一树支，则树的全部节点被分成互相分离的两组，而每一组节点仍是连通的。

（2）在树中任意两节点间加一连支，则该连支必定与该两点之间的若干树支构成回路。这种单连支回路称为基本回路。由每个连支构成的基本回路是唯一的，否则树中必有回路，违反树的定义。

任一连通图G可以选出不同的树，树数的计算是图论中的难题之一。

3.割集

在任何一个连通图G中，符合下列条件的支路集合称为图G的割集，用符号Ck表示。

（1）移去该支路集中的所有支路，留下的图形是两个分离的而又各自连通的子图。

（2）该支路集中，保留任一支路而将其余的支路都移去，留下的图形仍是连通的。

在图8-4（a）中，画出一个封闭面，该封闭面把连通图两部分，节点①、②在其内部，节点③、④在其外部，如果把封闭面切割的支路（2、3、5、6）移去，则将图分成两个分离的连通子图，所以支路集（2、3、5、6）构成一个割集。通常是用作封闭面的方法来确定割集，与一封闭面相切割的支路集一般都是割集。但也有例外，例如图8-4（b）中封闭面所切割的支路集（2、3、5、6 、7 、9）则不是割集，因为把该支路集从图中移去，留下的图形则是三个分离的各自连通的子图。

图8-4　图的割集示意图

在图8-4（c）中，选择一棵树，实线表示树支，虚线表示连支。根据树的定义，每一树支必定与若干连支构成一个割集。例如图中树支1与连支3、6构成割集C1 （1、3、6），树支5与连支2 、3 、6构成割集C2（2、3、5、6），树支4与连支2、6构成割集C3 （2、4、6）。这种只含一个树支的割集称为基本割集。由图8-4（c）不难看出，每一树支只能与其所在的各基本回路中的连支一起构成一基本割集，而不能与其他连支一起构成基本割集。因此，由每一树支决定的基本割集是唯一的。

4.图的基本回路数和基本割集数

一个节点数为n、支路数为b的连通图G，无论如何选树，其基本割集数为n-1，基本回路数为b-n+1。证明如下：

设想把连通图G的b条支路全部去掉，它的n个节点全部保留。为了形成一棵树，先用一个支路连接其中两个节点，把已连接的节点称作连通节点；以后每增加一个支路，要把一个新的节点与一个连通节点相连接。依次类推，把n个节点全部连接并形成一棵树，需要而且仅需要（n-1）条支路，因此，树支数为（n-1）。

因为每一树支必定与若干连支构成一基本割集，所以具有n个节点的连通图G，恒有（n-1）个基本割集。

树余中的连支数目等于连通图G的支路数b减去树支数（n-1），即连支数等于（b-n+1）。由于每一个连支必定与若干树支组成一个基本回路，所以具有n个节点、b条支路的连通图G，恒有（b-n+1）个基本回路。