离散数学点割集和边割集判断

1、点割集V是一些顶点的集合，如果删除V中的所有顶点之后，G不在连通，但是对于V的任何真子集V1,删除V1后G仍然连通。2、边割集E是一些边的集合，如果删除E里的所有边之后G不在连通，但是对于E的任何真子集E1,删除E1之后G仍然连通，则称E是边割集。

性质

1、点割集连通图G的一个割集C至少包含G的任意生成树的一个树枝。

2、边割集如果把C移去而仍有一棵树T存在，则图是连通的，那么C将不是一个割集。

特点

1、点割集同一割集的所有支路上的电流满足KCL。当割集中的\'所有支路都连接在同一结点上时，割集上的KCI方程就变成了结点上的KCL方程。

2、边割集一个连通图，可以列出与割集数目相等的KCI方程，但这些方程并非都是线性独立的。对于结点数为n支路数为b的连通图来说，其独立的KCI方程数为n-1个。