定义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 } 都 是 断集(边割)。 割集是断集, 反 之不一定
对于连通图G,E,删去一个割集D,得 到两个分支, 顶点集分别为V1和v(G)-V1, 割集D是G中一个端点在v1中,另一端点 在ⅴ(G)V中的边的全体。 如果在连通图G中,删去一个断集而不是 一个割集,那么将得到多于两个分支
对于连通图G(V,E), 删去一个割集D, 得 到两个分支, 顶点集分别为V1和V(G)-V1 , 割集D是G中一个端点在V1中, 另一端点 在V(G)-V1中的边的全体。 如果在连通图G中, 删去一个断集而不是 一个割集, 那么将得到多于两个分支
三、割集与回路 定理74:任何一条回路和任何生成树的余树至 少有一条公共边。 证明:如果一条回路和一棵生成树的余树没有 公共边,则这回路含在该生成树中,这是不可能 的。 定理75:任何一个割集和任何生成树至少有一 条公共边。 证明:如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说,删去一个割集后,不能将图G分为两 个分支,这与割集的定义相矛盾
三、割集与回路 定理7.4：任何一条回路和任何生成树的余树至 少有一条公共边。 证明：如果一条回路和一棵生成树的余树没有 公共边, 则这回路含在该生成树中, 这是不可能 的。 定理7.5：任何一个割集和任何生成树至少有一 条公共边。 证明：如果一个割集和一棵生成树没有公共边, 则删去该割集后留下一棵完整的生成树, 也就是说, 删去一个割集后, 不能将图G分为两 个分支, 这与割集的定义相矛盾
D 人玩何一个割集有 个割集D后,得 图7.3 v2)中,则C与D 没有公共边。 (2)如果C中顶点既有一些在V1中,又有一些 在V2中,先看D中任何一边, 它的一个端点在V1中,另一个端点在V2中, 且G中除D中边以外,不再有任何边连接V1 与V2中的顶点
定理7.6：任何一个回路和任何一个割集有 偶数条公共边。 证明：从连通图G中删去一个割集D后, 得 到两个顶点子集V1和V2 , 考察G中任一条回路C : (1) 如果C中所有顶点在V1 (或V2 )中, 则C与D 没有公共边。 (2)如果C中顶点既有一些在V1中, 又有一些 在V2中, 先看D中任何一边, 它的一个端点在V1中, 另一个端点在V2中, 且G中除D中边以外, 不再有任何边连接V1 与V2中的顶点
定义76:设连通图G中给定生成树T,对 于只包含T中一条枝的割集称此割集为 关于T的基本割集。 在连通图G中,对于给定的生成树T,每 枝恰对应唯一的一个基本割集。 因为从生成树T中删去一条枝,将T分为 两棵树,它将G的顶点集Ⅴ划分为V1和V V1,在G中这两个顶点集之间的连边,便 对应这一枝的唯一的基本割集
定义7.6：设连通图G中给定生成树T, 对 于只包含T中一条枝的割集,称此割集为 关于T的基本割集。 在连通图G中, 对于给定的生成树T, 每一 枝恰对应唯一的一个基本割集。 因为从生成树T中删去一条枝, 将T分为 两棵树, 它将G的顶点集V划分为V1和VV1 , 在G中这两个顶点集之间的连边, 便 对应这一枝的唯一的基本割集