二、割集与断集 定义74:设D是图G的一个边集,若在G中删 去D的全部边后所得图的秩减少1,而删去D 的任何真子集均无此性质,称D为G的割集。 图(a)中边集{e1,e3,ese6,e}是 割集,但删去任何真子集不 具有此性质 8 e3 e7
二、割集与断集 定义7.4：设D是图G的一个边集, 若在G中删 去D的全部边后所得图的秩减少 1 , 而删去D 的任何真子集均无此性质, 称D为G的割集。 图 (a) 中边集{e1 , e3 ,e5 ,e6 ,e8 }是 割集，但删去任何真子集不 具有此性质
图(b)中边集{el,e2}是割集 边集{e1,e2,e3,e4}不是割集, e3 e3 4 (b)
图(b)中边集{e1, e2} 是割集 边集{ e1,e2,e3,e4} 不是割集
定义75:设图G的顶点非空真子集为VcV,在G 中一个端点在V1中,另一端点在v(G)V1中的所 有边组成的集合称为G的一个断集或称边割,记 为E(1×(V(G)V1),简记为(VV(G)-V) 当(V1,V(G-V1)=1时,(V1,V(G)-V1)中的那条 边称为割边或桥。 图72(b)中边集 ei.? 和 {e1,e2,e3,e4}都是 断集(边割)。 e8 e4 e3 割集是断集,反 之不一定。 图7.2
定义7.5:设图G的顶点非空真子集为V1V, 在G 中一个端点在V1中, 另一端点在V(G)-V1中的所 有边组成的集合称为G的一个断集或称边割,记 为 E(V1(V(G)-V1 )), 简记为(V1 , V(G)-V1 )。 当|(V1 , V(G)-V1 )|=1时, (V1 , V(G)-V1 )中的那条 边称为割边或 桥。 图 7.2(b) 中边集 {e1 ,e2 } 和 {e1 ,e2 ,e3 ,e4 } 都 是 断集(边割)。 割集是断集, 反 之不一定