离散数学教案 编号.C1601 课时安排 2学时 牧学课型：理论课) 实验课口 习题课口实践课口其它口 题日（教学章、节或主题）： Ch16树 §16.1无向树及其性质 §162生成树 教学目的要求（分掌握、熟悉、了解三个层次）： 1.了解树的基本定义及性质 2.了解生成树 教学重点、难点： 1)重点：树的基本定义及性质，求最小生成树的算法 2)难点：求最小生成树的算法 教学方法 利用黑板，CAl课件等教学 教学用具： 黑板，CAI课件及其辅助设备 救学内容（注明：◆重点 #难点 ?疑点) ,基本概念(45分钟) 1.定义连通而不含回路的无向图称为无向树，简称树，常用T表示树 2.定义连通分支数大于等于2，且每个连通分支均是树的非连通无向图称为森林 平凡图称为平凡树」 3定义设T=为一棵无向树，v∈V若d(v)=1,则称v为T的树叶.若dv)≥2，则称v为T的分支点 4.定理设G=,则下面各命题是等价的： 1)G连通而不含回路 (2)G的每对顶点之间具有唯一的一条路径： (③)G是连通的且n=m+1 (4)G中无回路且n=m+1 (5)G中无回路，但在G中任两个不相邻的顶点之间增加一条边，就形成唯一的一条初级回路， (6)G是连通的且G中每条边都是桥 (⑦)G是连通的，但删除任何一条边后，就不连通了 其中n为G中顶点数，m为边数 例16.1(5161) 例16.2（§16.1） 二、生成树基本概念(45分钟) 1.定义设G=是无向连通图，T是G的生成子图，并且T是树，则称T是G的生成树 G在T中的边称为T的树枝， G不在T中的边称为T的弦 T的所有弦的集合的导出子图称为T的余树 2.定理任何连通图G至少存在一棵生成树。 推论1设n阶无向连通图G有m条边，则m≥n-l
1601 离 散 数 学 教 案 编号：C1601 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch16 树 §16.1 无向树及其性质 §16.2 生成树 教学目的要求（分掌握、熟悉、了解三个层次）： 1． 了解树的基本定义及性质 2． 了解生成树 教学重点、难点： 1） 重点：树的基本定义及性质，求最小生成树的算法 2） 难点：求最小生成树的算法 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、基本概念（45 分钟） 1.定义 连通而不含回路的无向图称为无向树,简称树,常用 T 表示树. 2.定义 连通分支数大于等于 2,且每个连通分支均是树的非连通无向图称为森林. 平凡图称为平凡树. 3 .定义 设 T＝为一棵无向树,v∈V,若 d(v)＝1,则称 v 为 T 的树叶.若 d(v)≥2,则称 v 为 T 的分支点. 4.定理 设 G＝,则下面各命题是等价的: (1) G 连通而不含回路; (2) G 的每对顶点之间具有唯一的一条路径; (3) G 是连通的且 n＝m+1; (4) G 中无回路且 n＝m+1; （5） G 中无回路,但在 G 中任两个不相邻的顶点之间增加一条边,就形成唯一的一条初级回路; (6) G 是连通的且 G 中每条边都是桥; (7) G 是连通的,但删除任何一条边后,就不连通了. 其中 n 为 G 中顶点数, m 为边数. 例 16.1 (§16.1) 例 16.2 (§16.1) 二、生成树基本概念（45 分钟） 1．定义 设 G＝是无向连通图,T 是 G 的生成子图,并且 T 是树,则称 T 是 G 的生成树. G 在 T 中的边称为 T 的树枝, G 不在 T 中的边称为 T 的弦. T 的所有弦的集合的导出子图称为 T 的余树. .2．定理 任何连通图 G 至少存在一棵生成树. 推论 1 设 n 阶无向连通图 G 有 m 条边, 则 m≥n-1
推论2设n阶无向连通图G有m条边，T是G的生成树，T是T的余树，则T中有m-n+1条边 1.定义设无向连通带权图G=,T是G的一棵生成树.T各边带权之和 称为T的权，记作W(①.G的所有生成树中带权最小的生成树称为最小生成树 例16.3（§16.2） 三、最小生成树的构造 *普里姆Prim)算法。 假设G是连通网，TE是G上最小生成树中边的集合。 (1)初始化：TV=d(VeV),TE=0 (②)选取：在所有u∈TV,v∈V-TV的边(u,）∈E中找一条权中最小的边e=(u,) (3)修改：TE=TE+{e},TV=TV+{w} (4)重复：(2)(3)至TV=y为止。 此时TE中必有n-1条边，则T=(TV,(TE)为N的最小生成树。 克鲁斯卡尔(KrTVskal)算法（避圈法） 假设G=W,E,D是连通网，TE是G上最小生成树中边的集合。 (1)初始化：TV=,TE=0: (2)选取：在所有边(u,v)中选取不在TE、权中最小、添加它之后不能形成回路的边： (③)修政：TE=TE+{e: (4重复：(2)(3)至|Tv=n-1为止。 此时E中必有-1条边，则T=(化，E)为N的最小生成树。假设连通网（化，E,),则令最小生成树 的初始状态为只有个顶点而无边的非连通图T=(仪，0)，图中每个项点自成一个连通分量。在E中远 择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边 而选择下一条权中最小的边。依次类推，直至于中所有项点都在同一连通分量上为止 四、课堂小结（约5分钟） 1602
1602 推论 2 设 n 阶无向连通图 G 有 m 条边, T 是 G 的生成树,T'是 T 的余树, 则 T'中有 m-n+1 条边. 1． 定义 设无向连通带权图 G=, T 是 G 的一棵生成树 .T 各边带权之和 称为 T 的权,记作 W(T) . G 的所有生成树中带权最小的生成树称为最小生成树. 例 16.3 (§16.2) 三、最小生成树的构造 *普里姆(Prim)算法。 假设 G=是连通网，TE 是 G 上最小生成树中边的集合。 (1) 初始化：TV={V0}( V0∈V)，TE={} (2) 选取：在所有 u∈TV，v∈V-TV 的边(u，v) ∈E 中找一条权中最小的边 e=（u0，v0) (3) 修改：TE=TE+{e}，TV=TV+{v0} (4) 重复：(2)(3)至 TV=V 为止。 此时 TE 中必有 n-1 条边，则 T=(TV,{TE})为 N 的最小生成树。 克鲁斯卡尔（KrTVskal）算法（避圈法） 假设 G=是连通网，TE 是 G 上最小生成树中边的集合。 (1)初始化：TV=V, TE={}; (2)选取：在所有边(u，v)中选取不在 TE、权中最小、添加它之后不能形成回路的边 e； (3)修改：TE=TE+{e}； (4)重复：(2)(3)至|TV|=n-1 为止。 此时 TE 中必有 n-1 条边，则 T=(V,{TE})为 N 的最小生成树。假设连通网 N=(V，E，W)，则令最小生成树 的初始状态为只有 n 个顶点而无边的非连通图 T=(V，{})，图中每个顶点自成一个连通分量。在 E 中选 择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中，否则舍去此边 而选择下一条权中最小的边。依次类推，直至于中所有顶点都在同一连通分量上为止 四、课堂小结（约 5 分钟）
离散数学教案 编号，C1601 课时安排： 2学时 牧学课型：理论课 实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch16树 §16.3根树及其应用 教学目的要求（分掌握、热悉、了解三个层次） 3.了解根树的定义 4.了解根树的应用 教学重点、难点： 1)重点：根树的定义、根树的应用 2)难点：根树的应用 教学方法 利用黑板，CAI课件等教学 牧学用具： 黑板，CAI课件及其辅助设备 教学内容（注明：重点#难点？疑点） 根树 定义若一个有向图D的基图是无向树，则称D为有向树。 定义若一个有向图满足下列条件：(1)恰有一个顶点的入度为0（称之为树根）：(2)其他顶点的入度都 为1：则称这个有向图是一棵有向树。 在一棵有向树中，出度为零的结点称为树叶，其余结点称为分支点。 注：有根树常采用倒置形式表示，根在上方，叶都在下方，每一条有向边的方向向下，从而可省略 边的方向。 定义在一棵有向树T=中，从树根到某个顶点的通路的长度，称为该顶点的层数，层数的最大者 称为该树的高（度）。根结占的层新为0 一棵有】 E>中，若<u,veE,则称v是u的儿子 u是v的父亲 :同一分支点的儿手 。达，则称是Y湘先，V是u的后代：若醇个分支点的曲度 血元树。若每个分支点的出度都等于m,则称T为血元正则树。 最有用和最常用的是二元树和二元正则树。 二、最优二叉树 定义设二元正则树T有k片树时，分别带有权，。称（们） 1(:)为 的权，其中1(w)是树叶v的层数。 在所有带权 ，W2 .,的有k片树叶的二元正则树中权最小的称为带权，.，的最优 二元 求最优二元树的哈夫曼算法的基本思想是用带权的k一1片树叶的最优二元树求出带权的k片树 的最优二元树。 Huffman算法：在带权W,.,W且W≤w≤.≤W ()对权重数列已有小到大排序：≤≤.≤， 1603
1603 离 散 数 学 教 案 编号：C1601 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch16 树 §16.3 根树及其应用 教学目的要求（分掌握、熟悉、了解三个层次）： 3． 了解根树的定义 4． 了解根树的应用 教学重点、难点： 1） 重点：根树的定义、根树的应用 2） 难点：根树的应用 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： 一、 根树 定义 若一个有向图 D 的基图是无向树，则称 D 为有向树。 定义若一个有向图满足下列条件：（1）恰有一个顶点的入度为 0(称之为树根)；（2）其他顶点的入度都 为 1；则称这个有向图是一棵有向树。 在一棵有向树中，出度为零的结点称为树叶，其余结点称为分支点。 注： 有根树常采用倒置形式表示，根在上方，叶都在下方，每一条有向边的方向向下，从而可省略 边的方向。 定义 在一棵有向树 T=中，从树根到某个顶点的通路的长度，称为该顶点的层数，层数的最大者 称为该树的高(度)。根结点的层数为 0。 定义 在一棵有向树 T=中，若 E，则称 v 是 u 的儿子，u 是 v 的父亲；同一分支点的儿子 称为兄弟；若 u 可达 v，则称 u 是 v 的祖先，v 是 u 的后代；若每个分支点的出度都不大于 m，则称 T 为 m 元树。若每个分支点的出度都等于 m，则称 T 为 m 元正则树。 最有用和最常用的是二元树和二元正则树。 二、最优二叉树 定义设二元正则树 T 有 k 片树叶 v1，v2，.，vk，分别带有权 w1，w2，.，wk。称 w(T)= = k i 1 wil(vi)为 T 的权，其中 l(vi)是树叶 vi 的层数。 在所有带权 w1，w2，.，wk 的有 k 片树叶的二元正则树中权最小的称为带权 w1，w2，.，wk 的最优 二元树。 求最优二元树的哈夫曼算法的基本思想是用带权的 k－1 片树叶的最优二元树求出带权的 k 片树叶 的最优二元树。 Huffman 算法： 在带权 w1，w2，.，wn 且 w1≤w2≤.≤wn (1)对权重数列已有小到大排序：w1≤w2≤.≤wn
(2)连接和为全的两片树叶，的一个分支点，权重为+W: (3)权重数列中，别除，.增加W+W,对权重数列重新排序。 (4)重复(2)(3)直到形成-1个分支点，n片树叶 二、一元树的应用-一一前编码哈夫曼编码) 定义设A 字符串集，若其中的任 符串都不是其它字符串的前缀，则称A为一个前缀码（哈夫 若组成A的字符串的只有字符0和1，则称A为二元前缀码。 [例]{000,001,01,10,110,111}是一个二元前缀码，而{(000,001,01,10,11,111}不是一个 二元前缀码。 如何构造一个二元前绶码： 1构造一棵二元树，树根的左侧用0标记，右侧用1标记： 2分支点 的左侧（右侧）的标记就是标记的 二进制数最右端加上0（①）： 3任一片树叶的标记串不是其它树叶的标记串的前缀： 4将所有树叶的标记串取来就可构成一个二元前缀码。 [例]在通信中0,1,2,3,4,5,6,7的传输比例为 0.30% 1.20% 2.15% 310%. 4:10% 5:5%, 6:5% 7:5% 求传输他们的最佳前缀码 四、二元树的遍历 ()前序端历：访问根结点，前序端历左子树，前序病历右子树 (②)中序遍历：中序遍历左子树，访问根结点，中序遍历右子树： (③)后序遍历：后序遍历左子树，后序遍历右子树，访问根结点 [例]写出三种遍历的结果 6 h 五、课堂小结（约5分钟 1604
1604 (2)连接 w1 和 w2 为全的两片树叶，的一个分支点，权重为 w1+w2； (3) 权重数列中，删除 w1，w2， 增加 w1+w2n，对权重数列重新排序。 (4)重复(2)(3)直到形成 n-1 个分支点,n 片树叶 三、二元树的应用-前缀码(哈夫曼编码) 定义设 A 是一个字符串集，若其中的任一字符串都不是其它字符串的前缀，则称 A 为一个前缀码(哈夫曼 编码)。若组成 A 的字符串的只有字符 0 和 1，则称 A 为二元前缀码。 ［例］ {000，001，01，10，110，111}是一个二元前缀码，而{000，001，01，10，11，111}不是一个 二元前缀码。 如何构造一个二元前缀码： 1 构造一棵二元树，树根的左侧用 0 标记，右侧用 1 标记； 2 分支点 v 的左侧(右侧)的标记就是标记 v 的二进制数最右端加上 0(1)； 3 任一片树叶的标记串不是其它树叶的标记串的前缀； 4 将所有树叶的标记串取来就可构成一个二元前缀码。 [例］在通信中 0，1，2，3，4，5，6，7 的传输比例为 0：30%， 1：20%， 2：15% 3：10%， 4：10%， 5：5%， 6：5% 7：5% 求传输他们的最佳前缀码 四、二元树的遍历 (1)前序遍历：访问根结点，前序遍历左子树，前序遍历右子树； (2)中序遍历：中序遍历左子树，访问根结点，中序遍历右子树； (3)后序遍历：后序遍历左子树，后序遍历右子树，访问根结点。 [例］写出三种遍历的结果 a b c d e f g h i j 五、课堂小结（约 5 分钟）