第3讲最小生成树

1 树及其性质 2 割点 割边 割集 3 最小生成树及其算法 第三讲最小生成树 一 树及其性质 树 图论中把不包含圈的连通图称为树 记为T 不包含圈的图称为无权圈图 图G的连通无圈子图称为G的树 包含图G的所有顶点的G的树为图G的一棵生成树或支撑树 定理1 树T的任意两个顶点之间存在唯一的路 定理2 若G是树 则 边数 顶点个数 1 二 割点 割边 割集 割点 设简单图G V E 满足w G u w G 的顶点u称为割点 割边 在简单图G V E 中 满足w G e w G 的边e称为割边 顶点割集 设V1是V中任一非空子集 若图G连通而图G V V1 不连通 则称V1是G的顶点割集 最小顶点割集中顶点的个数叫做图G的连通度 边割集 设S是V中任一非空子集 记S2 V S 在图G中连接S与S2之间的边集 记作 S S2 称为G的一个边割集 三 最小生成树及其算法 1 树的定义与树的特征 定义连通且不含圈的无向图称为树 常用T表示 树中的边称为树枝 树中度为1的顶点称为树叶 孤立顶点称为平凡树 平凡树 2 找图中生成树的方法 可分为两种 避圈法和破圈法 A避圈法 深探法和广探法 B破圈法 A避圈法 定理3的充分性的证明提供了一种构造图的生 成树的方法 这种方法就是在已给的图G中 每步选出一条边使它与已选边不构成圈 直到选够n 1条边为止 这种方法可称为 避圈法 或 加边法 在避圈法中 按照边的选法不同 找图中生成树的方法可分为两种 深探法和广探法 a 深探法 若这样的边的另一端均已有标号 就退到标号为 步骤如下 i 在点集V中任取一点u ii 若某点v已得标号 检 端是否均已标号 若有边vw之w未标号 则给 w代v 重复ii i 1的r点 以r代v 重复ii 直到全部点得到标号为止 给以标号0 查一端点为v的各边 另一 w以标号i 1 记下边vw 令 例用深探法求出下图10的一棵生成树 0 1 2 3 4 5 6 7 8 9 10 11 12 13 13 a 深探法 0 1 2 3 4 5 6 7 8 9 10 11 12 步骤如下 若这样的边的另一端均已有标号 就退到标号为 i 在点集V中任取一点u ii 若某点v已得标号 检 端是否均已标号 若有边vw之w未标号 则给 w代v 重复ii i 1的r点 以r代v 重复ii 直到全部点得到标号为止 给u以标号0 查一端点为v的各边 另一 w以标号i 1 记下边vw 令 例用深探法求出下图10的一棵生成树 3 b 广探法 步骤如下 i 在点集V中任取一点u ii 令所有标号i的点集为 是否均已标号 对所有未标 号之点均标以i 1 记下这些 iii 对标号i 1的点重复步 步骤ii 直到全部点得到 给u以标号0 Vi 检查 Vi V Vi 中的边端点 边 例用广探法求出下图10的一棵生成树 1 0 1 2 2 1 3 2 1 2 2 3 4 标号为止 3 b 广探法 步骤如下 i 在点集V中任取一点u ii 令所有标号i的点集为 是否均已标号 对所有未标 号之点均标以i 1 记下这些 iii 对标号i 1的点重复步 步骤ii 直到全部点得到 给u以标号0 Vi 检查 Vi V Vi 中的边端点 边 例用广探法求出下图10的一棵生成树 1 0 1 2 2 1 3 2 1 2 2 3 4 标号为止 显然图10的生成树不唯一 B破圈法 相对于避圈法 还有一种求生成树的方法叫做 破圈法 这种方法就是在图G中任取一个圈 任意舍弃一条边 将这个圈破掉 重复这个步骤直到图G中没有圈为止 例用破圈法求出 下图的一棵生成树 B破圈法 例用破圈法求出下图的另一棵生成树 不难发现 图的生成树不是唯一的 3 最小生成树与算法 介绍最小树的两种算法 Kruskal算法和Prim破圈法 AKruskal算法 或避圈法 步骤如下 1 选择边e1 使得w e1 尽可能小 2 若已选定边 则从 中选取 使得 i 为无圈图 ii 是满足i 的尽可能小的权 3 当第2 步不能继续执行时 则停止 定理由Kruskal算法构作的任何生成树 都是最小树 例 用Kruskal算法求下图的最小树 在左图中权值 最小的边有任取一条 在中选取权值 最小的边 中权值最小边有 从中选 任取一条边 会与已选边构成圈 故停止 中选取在中选取 中选取 但与都 Kruskal算法的MATLAB实现 function Tc krusf d flag ifnargin 1n size d 2 m sum sum d 0 2 b zeros 3 m k 1 fori 1 nforj i 1 nifd i j 0b 1 k i b 2 k j b 3 k d i j k k 1 endendendelseb d end n max max b 1 2 m size b 2 B i sortrows b 3 B B c 0 T k 1 t 1 n fori 1 mift B 1 i t B 2 i T 1 2 k B 1 2 i c c B 3 i k k 1 tmin min t B 1 i t B 2 i tmax max t B 1 i t B 2 i forj 1 nift j tmaxt j tmin endendendifk nbreak endendT c B Prim算法 步骤如下 从图G中某一顶点出发 任选一最小权边 2 将其顶点加入到生成树的顶点集合U中 3 从一个顶点在U中 一个顶点不在U中的各条边中任取最小权边 加入到生成树中 例用Prim算法求下图的最小树 Prim算法的MATLAB实现 function Tc Primf a l length a a a 0 inf k 1 l listV k 0 listV 1 1 e 1 while ea i j min a i j b a i j s i d j endendendend listV d 1 distance e b source