树与图的最小树 Page 26 树是图论中结构最简单但又十分重要的图。在自然和社会领 域应用极为广泛。 例62乒乓求单打比赛抽签后，可用图来表示相遇情况，如 下图所示。 运动员A
树与图的最小树 Page 26 树是图论中结构最简单但又十分重要的图。在自然和社会领 域应用极为广泛。 例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如 下图所示。 运动员 A B C D E F G H
树与图的最小树 Page 27 例6.3某企业的组织机构图也可用树图表示。 厂长 人事科 财务科 总 生产副 经营副 程师 厂长 厂长 开发科 技术科 生产科 设备科 供应科 动力科 销售科 检验科
树与图的最小树 Page 27 例6.3 某企业的组织机构图也可用树图表示。 厂长 人事科 财务科 总工 程师 生产副 厂长 经营副 厂长 开发科 技术科 生产科 设备科 供应科 动力科 销售科 检验科
树与图的最小树 Page 28 树：无圈的连通图即为树 性质1：任何树中必存在次为1的点。 V6 3 性质2：n个顶点的树必有n-1条边。 V 性质3：树中任意两个顶点之间，恰有且仅有一条链。 性质4：树连通，但去掉任一条边，必变为不连通。 性质5：树无回圈，但不相邻的两个点之间加一条边，恰 得到一个圈
树与图的最小树 Page 28 树：无圈的连通图即为树 性质1：任何树中必存在次为1的点。 性质2：n 个顶点的树必有n-1 条边。 性质3：树中任意两个顶点之间，恰有且仅有一条链。 性质4：树连通，但去掉任一条边，必变为不连通。 性质5：树无回圈，但不相邻的两个点之间加一条边，恰 得到一个圈。 v1 v2 v3 v4 v5 v6
树与图的最小树 Page 29 。图的最小部分树（支撑树） 如果G2是G1的部分图，又是树图，则称G2是G1的部分树 (或支撑树)。树图的各条边称为树枝，一般图G1含有多 个部分树，其中树枝总长最小的分树，称为该图的最小 分树（或最小支撑树）。 V: G1 G2
树与图的最小树 Page 29 图的最小部分树(支撑树) 如果G2是G1的部分图，又是树图，则称G2是G1的部分树 （或支撑树）。树图的各条边称为树枝，一般图G1含有多 个部分树，其中树枝总长最小的部分树，称为该图的最小 部分树（或最小支撑树）。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 G1 G2
树与图的最小树 Page 30 d b
树与图的最小树 Page 30 a b c f e d g h b f e d