10.2生成树与割集 、割集与断集 1定义10.4(割集) 设D是图G的一个边集,若在G中删去 D的全部边后所得图的秩减少1,而D的 任何真子集均无此性质,则称D为G的割 集。 例图10.2
10.2 生成树与割集 二、割集与断集 1 定义10.4（割集） 设D是图G的一个边集，若在G中删去 D的全部边后所得图的秩减少1，而D的 任何真子集均无此性质，则称D为G的割 集。 例 图10.2
10.2生成树与割集 2定义10.5(断集) 设图G顶点非空子集为VcV,在 G中一个端点在V1中,另一个端点在V1 中的所有边组成的集合称为G的一个断集 (或称边割),记为E(V1xV1) 割集是断集,反之不一定 连通图中删去一个割集,得两个连通分支 删去一个断集;得两个以上连通分支
10.2 生成树与割集 2 定义10.5（断集） 设图G顶点非空子集为V1V，在 G中一个端点在V1中，另一个端点在 中的所有边组成的集合称为G的一个断集 （或称边割），记为E(V1 )。 割集是断集，反之不一定。 连通图中删去一个割集，得两个连通分支； 删去一个断集；得两个以上连通分支。 V 1 V1
10.2生成树与割集 三、割集与回路 1定理104 任何一条回路和任何生成树的余树至 少有一条公共边。 (反证法
10.2 生成树与割集 三、割集与回路 1 定理10.4 任何一条回路和任何生成树的余树至 少有一条公共边。 (反证法)
证:若G中一条回路和一生成树的补无公 共边,则表示该回路在该生成树中。这 与生成树定义矛盾
证：若G中一条回路和一生成树的补无公 共边，则表示该回路在该生成树中。这 与生成树定义矛盾
2定理10.5 任何一个割集和任何生成树至少有 条公共边
2 定理10.5 任何一个割集和任何生成树至少有一 条公共边