3-4割集分析法.doc

.3-6 割 集 分 析 法一、割集与基本割集 1）、割集 割集是支路的集合，它必须满足以下两个条件： （1） 移去该集合中的所有支路，则图被分为两部分。 （2） 当少移去该集合中的任何一条支路，则图仍是连通的。612345图326 图G及其割集(a)(b)(c)(d)612345612345612345 需要说明的是，在移去支路时，与其相连的结点并不移去。图G是一个连通图，如图326(a)所示，支路集合1，5，2、1，5，3，6、2，5，4，6均为图G割集。将以上割集的支路用虚线表示，分别如图326(b)、(c)、(d)所示，不难看出，去掉虚线支路后，各图均被分成了两部分，但是(a)(b)图327 非割集说明612345612345只要少去掉其中的一条虚线支路，图仍然是连通的