证:若G中一个割集和一生成树无公共 边,则表示该割集所分离的结点不在生 成树中,这导致与生成树的定义矛盾
证：若 G中一个割集和一生成 树无公共 边，则表示该割集所分离的结点不在生 成树中，这导致与生成树的定义矛盾
10.2生成树与割集 3定理10.6 任何一条回路和任何一个割集有偶数 条公共边
10.2 生成树与割集 3 定理10.6 任何一条回路和任何一个割集有偶数 条公共边
证明:从连通图G中删去一个割集D后,得到两个 顶点子集V1和V2,考察中任一条回路C (1)如果C中所有顶点在V1(或V2)中,则C与D没有 公共边; (2)如果C中顶点既有一些在V中,又有一些在V2中, 先看D中任何一边,它的一个端点在V1中,另一个 端点在V2中,且G中除D中边以外,不再有任何连 接V1与V2中的顶点。然而,从V1中(也可以从V2中) 的一个顶点出发,沿C行走到V2中的某些顶点又回 到V1,这样在V1与V2之间来回行走,最后回到V1的 出发点。 因此,回路C中必有偶数条割集D中的边
证明：从连通图 G中删去一个割集 D后，得到两个 顶点子集 V 1 和 V 2，考察中任一条回路 C： (1)如果 C中所有顶点在 V 1（或 V 2）中，则 C 与 D没有 公共边； (2)如果 C中顶点既有一些在 V 1中，又有一些在 V 2中， 先看 D中任何一边，它的一个端点在 V 1中，另一个 端点在 V 2中，且 G中除 D中边以外，不再有任何连 接 V 1 与 V 2中的顶点。然而，从 V 1中（也可以从 V 2中） 的一个顶点出发，沿 C行走到 V 2中的某些顶点又回 到 V 1，这样在 V 1 与 V 2之间来回行走，最后回到 V 1 的 出发点。 因此，回路 C中必有偶数条割集 D中的边
10.2生成树与割集 定义106(基本割集/基本割集组) 设连通图G中给定生成树T,对于 包含T中的一条枝的割集,称此割集为关 于T的基本割集。 连通图G有e条边,n个顶点,给定的 生成树T应有n-1条枝,所以恰有n-1个基 本割集,这些割集的全体称为生成树T的 基本割集组
10.2 生成树与割集 4 定义10.6（基本割集/基本割集组） 设连通图G中给定生成树T，对于只 包含T中的一条枝的割集，称此割集为关 于T的基本割集。 连通图G有e条边，n个顶点，给定的 生成树T应有n-1条枝，所以恰有n-1个基 本割集，这些割集的全体称为生成树T的 基本割集组
10.2生成树与割集 5定义10.7(基本回路基本国路组) 设连通图G中给定生成树T,在T中加 条弦,恰产生一条回路,称此回路为 关于T的基本回路 连通图G有e条边,n个顶点,给定的生 成树T应有n-1条枝,e-n+1条弦,所以恰 有e-n+1条基本回路,这些回路的全体称 为生成树T的基本回路组
10.2 生成树与割集 5 定义10.7（基本回路/基本回路组） 设连通图G中给定生成树T，在T中加 一条弦，恰产生一条回路，称此回路为 关于T的基本回路。 连通图G有e条边，n个顶点，给定的生 成树T应有n-1条枝，e-n+1条弦，所以恰 有e-n+1条基本回路，这些回路的全体称 为生成树T的基本回路组