《树与最小树》教案.docx

§ 1—2树与最小树
教学目的：1、理解树的相关概念
2、 理解最小树问题
3、 掌握求最小树的方法
教学重点：避圈法、破圈法
教学难点：树的概念的理解
教学过程：
一、树与图的部分树
1、 定义：一个无圈的连通图称为树
§ 1—2树与最小树
教学目的：1、理解树的相关概念
2、 理解最小树问题
3、 掌握求最小树的方法
教学重点：避圈法、破圈法
教学难点：树的概念的理解
教学过程：
一、树与图的部分树
1、 定义：一个无圈的连通图称为树
L团支书
例1 12级会计一班班级结构如图：
—班长 学习委员
班主任
1-劳动委员
—心理委员
I—组织委员
—副班长 %乙委页
（日常生活中还有很多树形图的运用，例如黄石冶钢集团组织结构, 家族族谱等等，大家可以想想平时还看到过哪些树形图）
从最简单的树开始观察起，大家能发现有什么规律吗？
0——o V:2 E:1
2、 树的性质：设T是一棵有p个顶点的树，则树T的边数是（p-1）
条
图有部分图，树有部分树，什么是部分树呢？
3、 定义：如果G的一个部分图T是棵树，则称T为G的一棵部分
树
注：部分树首先得是部分图，必须包含图G的所有顶点。
二、最小树
1、 定义：如果图G中的每一条边相应地有一个数明•，称为边
m,七］的权。图g连同在它边上的权称为赋权图.
2、 定义：在赋权图G中，部分树T的各边上权的总和称为部分树T
的权.
3、最小树问题：求赋权图G中权最小的部分树.
二、最小树算法
1、避圈法
步骤：(1) .画出赋权图G的各个顶点。
.在G中画一条权最小的边。
.在G中余下的边中，选一条权最小的边加在图上，并
要使它与已选入的边不形成圈(避圈).
.重复步骤(3),直至各顶点都连通为止(此时的边数
应等于顶点数减1)
例2本学院要沿如图所示的道路架设电话线，将六个部门连成网. 已知每条道路的长度，求使电话线总长最小的架设方案.
粹:
v