老师在课上讲的时候表示这段比较抽象,他的老师当初讲的并不清楚。鉴于我曾经学过一点点图论,我并不知道他讲的是否清楚,但我想在某些环节提出一些我认为较为易于理解的思路。
参考书籍:电路理论高级篇(颜秋容 著)。
在第十九章我们研究电路的计算机辅助分析方法。其思路主要分两个方向:分析电路图的拓扑构成,以及单一之路的电压电流关系(即VCR)。这里我们要讨论的问题是电路图的拓扑。
以书上给出的样例电路图为例,我们进行相关的分析举例。
(注:此处不对支路的方向性进行讨论,因为根据在课上听的结果、书上的理论与举例、我自身对后续推导原理的推测,这里的方向性会存在诸多问题且没有方向并不影响此处的讨论。)
我们从树的性质开始讨论(前置内容如连通图性质略)
树
此处树的定义是不含回路的连通图。可以很容易证明一下三条等价且都可作为树的定义:
- 不含回路的连通图
- 任意两点间有且仅有一条简单路径的连通图
- 支路数为节点数-1的连通图
根据定义,一个连通图中可能可以抽离出很多棵不同的树。例如书上p174图19-2-3给出的例子。此处我们以下图这棵作为后续举例。
这里,我们定义这棵树中的所有支路为树支,而剩余未被选中的支路为连支。在样例图中,支路2,3,4,7为树支;支路1,5,6,8为连支。
基本回路
我们知道,此前学习的电路图中,每一个网孔都对应着一个KVL方程。但是,在一张较为复杂的图中,通过计算机直接找出所有网孔并不容易(在非平面图也无法找出)。实际上每一个回路也对应着一个KVL方程,但是回路数量远大于网孔数量,而实际有效的KVL方程数量则等于网孔数量,多余的KVL方程一定可以用其余KVL方程线性组合而成。因此,为了不重不漏地找出所有KVL方程,就需要一定技巧性地选择回路。
在这里,我们采用的方法是先找出一棵树(以上文为例),然后逐个连接连支,每次找的回路由连接的连支与连支所连两点间在树上的简单路径构成,以下图为例:分别是连接支路8与支路1对应的情况。
接下来我们证明为什么这样连线找到的回路集合是不重不漏的:
首先,我们找到的回路数等与连支数,也就等于网孔数,说明如果不重则不漏。
其次,我们找到的所有回路都仅包含一条连支,我们也把这样的回路叫做单连支回路。由于每条连支与一个单连支回路一一对应,因此它们之间是相互独立的,不存在重复。
所以,我们找到的就是一组不重不漏的回路集合,称为一组基本回路。
基本割集
割集是一个支路集合,其定义包括两个条件:
- 将集合中的支路全部从图中移走,支路两端的节点保留,连通图分离成两个部分切仅有两个部分(孤立节点也算一个部分)
- 若少移走任何一条支路,则图仍联通
每一个割集就对应了一个KCL方程。
这个描述可能还不算难理解,但是具体怎么找就有些抽象了。我们不妨换一个角度来看这个问题:既然割集最终的结果是将一个连通图切割成两份,那么我们可以考虑先将连通图的节点分成两组,然后切割组间的连线,这样就满足了割集的性质。以下图为例:将连通图的节点分成左右两组,那么组间连线,即支路1,8,7,3的集合就是一个割集。
但是这个方法还缺少一个条件:如果在分完组以后某一组中的节点内部并不连通(如选取节点3,4),那么实际上所有组间连线删去后就产生了大于两个部分,不符合割集的定义。为了避免这一现象,我们要求:分割的两组点集内部必须连通。
实际上,每一种节点分组方式都对应了一个KCL方程,但是显然存在大量重复,为了找出一组不重不漏的KCL方程组,我们需要找到一组基本割集。也因此出现了如此多的限制。
我们根据这些限制条件寻找基本割集的办法是:找出一棵树(同例),枚举每一条树支,显然每一条树支都将这棵树分成两部分,这两部分的点集分组就是我们要找的目标分组。再根据分组找出对应的割集。由此,我们找到了与树支相等数量的割集,它们之间存在一一对应关系。一下图为例:分别是选择树支2和树支3对应的情况。
接下来我们证明为什么这样求割集找到的是一组基本割集:
首先,由于树的性质,我们分成的两部分内部一定连通,因此我们这样找出来的割集都是合法的。
同基本回路,我们找到的割集数等于树支数,也就等于实际有效KCL方程数,说明如果不重则不漏。
我们找到的每一个割集都包含且仅包含一条树支,也称作单树支割集。由于每条树支都与一个单树支割集一一对应,因此所有的单树支割集相互独立,不存在重复。
所以,我们找到的就是一组不重不漏的割集集合,称为一组基本割集。