kcl方程独立性的图论证明

这是困惑了本人很久的问题，最近得闲，去b站观光了部分的离散数学课程并参考了一些资料，对这个问题做个总结，也算是笔记吧。电路原理和离散数学都还没学完，小白一只，各位如有发现任何错误，恳请指出。

支路电流法解线性电路的一般方法

已知在求解线性电路的过程当中，可以列出n-1条kcl独立的kcl方程，b-（n-1）条kvl独立的方程，从而可以解出b条支路的电压电流参数。作为一般性的理论，在电路的求解过程当中常会用到。但我们是否有思考过，为什么电路的节点之中一定就能够找到n-1条kcl方程呢？下面用图论的割集理论对这一现象做出解释（作图不太熟悉，先打着字，图过段时间补）

图与电路

电路图本质上可以生成由节点和边作为基本参数的无向图。
节点就是电路的分叉点，节点数记为n，边即为电路上的各个支路，边数记为b。

割集

参照百度百科定义：
设S是G的边集E的一个子集，如果在连通图G中删除S的所有边．则G-S不连通，并且不存在S的真子集使G-S不连通，就称边集S是图G的一个割集。
也就是说在图上删除掉一个最小数量的边可以将一个连通的图拆分成不联通的两个部分，那么这个边组成的集合就称为割集。
图上有n个节点，一个显然的结论是，假如删除掉某一个节点上连接的所有边，那么这一个节点将和图上的其他部分，分割成两个互不连通的子图。所以，每个节点上关联的所有边都可以成为这个图的割集。

kcl与割集

显然，由上可知，一个连通图上至少可以写出n个割集，而这刚刚好是电路当中通过单个节点分析能够列出的kcl方程的数目，将割集的概念迁移到电路分析当中，可以看作割集上的边存在对被割离部分电流的流入与流出。所以分析图上独立的割集的最大独立方程数目也就是分析能列出来的kcl方程数目。那么现在问题转换成了求图上独立的割集数。但是在正式求解kcl独立方程数目前 ，还需要对独立性做一点思考。

独立性概念

参考线性代数的概念，将列出的一个kcl方程系数看作行向量，记作pi列出的n-1个方程的将组成一个（n-1）b的系数矩阵，当任意的ci不全等于0时：
有：
c1p1+c2p2+c3p3+…cn*pn不等于0
那么说明所有的pi相互独立。
由于同一条边在列出的kcl方程中最多可以出现两次（分别表示电流的流入和流出）
在对系数矩阵经过初等行变换后，独立的kcl方程可以使每一行都有一个非0项，如果能够证明n-1个kcl方程当中有n-1个不重复的支路，那么就可以证明该方程的秩R=n-1（证明略去）

证明

1.考察一个遍历图上所有顶点的生成树，树的长度为n-1，对树的顶点进行编号（1,2…n），那么n-1条边可以分别记作：1–2, 2–3 ，3–4…n-1–n。
其中n-1—n表示n-1号点与n号点之间的边。
2.依次过这n-1条边做割集，如过1–2边将点1与其他部分分割，过2—3将1,2与其他部分分割，过3–4将点1,2,3与其他部分分割，依次操作，可以列出n-1个割集，并且每一个割集都包含在其他割集中唯一的不重复出现的边，这个不重复的边也即是各个树枝。也即是可以证明这n-1个割集是相互独立的。由上，也可以证明可以列出的独立kcl方程数目为n-1.
3.证明n个kcl方程必定不独立：若列出n个kcl方程，可以证明，kcl方程覆盖所有节点，所有支路在kcl方程中均出现两次（分别代表电流的流入与流出），故：p1+p2+p3…pn恒等于0.
4.n个节点能列出的最大独立kcl方程数目为n-1个.

对kvl的延伸。

可以证明最大独立kvl方程数目为b-(n-1)
未想到严格证明方法：
1.这里提供一种仅供想通的思路：假设电路的b个支路在拓扑情况与元件特性均是已知状态下是可求的，那么在要求列出b个独立方程求解b个变量，kcl可以列出n-1个方程，故kvl应该可以列出b-（n-1）个独立方程。
2.可以看出独立kcl方程数=树枝数=支路数-连枝数=支路数-独立kvl方程数。