第3讲最小生成树.ppt

下下回回停停 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的一个边割集。 1v (1) T表示. 树中的边称为树枝. 树中度为 1的顶点称为树叶. 3v 4v 5v 平凡树(2)找图中生成树的方法(2)找图中生成树的方法可分为两种:避圈法和破圈法 A 避圈法 : 深探法和广探法 B 破圈法 A 避圈法 A 避圈法定理 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 的一棵生成树图10 0 1234 5 6 789 10 11 12 13 13 a) 深探法图10 0 1234 5 6 789 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 的一棵生成树图10 1 0122 1 3 212 2 34 3 b)广探法步骤如下: i) 在点集 V中任取一点 u, ii) 令所有标号 i的点集为是否均已标号. 对所有未标号之点均标以 i+1, 记下这些 iii) 对标号 i+1 的点重复步步骤 ii),直到全部点得到给u以标号 0. Vi, 检查[Vi,V\Vi] 中的边端点边. 例用广探法求出下图 10 的一棵生成树图10 1 0122 1 3 212 2 34 标号为止. 显然图 10 的生成树不唯一.