2009-8-20
1
第九章 树与平面图树是一类结构较为简单的图，是用途极为广泛的离散数学模型，特别是二叉树，
它在计算机科学中用得最多,因此在学习时应很好地掌握好诸如树的充要条件、
生成树、最优生成树、根树、树的各种算法、及二叉树的访问次序等内容,平面图是实际背景很强的一类图，能用本章介绍的方法判断一个图是否为平面图,
返回首页
2009-8-20
2
第一节 树的概念
本节介绍树的一些最基本的概念与结论,
1.概念有,树,树叶,分支点 (或内点 ),森林,
平凡树等
2.结论,设 G是 n阶无向图，则下列条件等价：
（ 1） G是树； (2） G连通并且删去 G的任一边,所得之图都不连通； (3） 对 G中的任意两点 u,v(u≠v),恰有一条从 u到 v
的简单路； (4） G不含回路,且 G有 n-1
条边； (5） G连通,且 G有 n-1条边,
返回本章首页
2009-8-20
3
第二节 生成树与最优支撑树
本节讨论连通图的生成树与连通权图的最优生成树 (或称为最优支撑树 ).
1.基本概念,生成树,余树,树枝,最优 (小 )
生成树等 ;
2.定理,图 G有生成树当且仅当 G是连通的；
3.算法,(1)无向连通图可采用破坏回路与不形成回路两种方法寻找生成树；
(2)权图中求最优生成树的两种算法,即克鲁斯卡尔算法与管梅谷的破圈法,
返回本章首页
2009-8-20
4
第三节 有向树与根树 (1)
有向树是有向图中结构最为简单的一类图,它是一种典型的非线性结构，在计算机算法分析、数据结构等方面有广泛的应用；在有向树中，根树最为重要，
我们主要考虑根树,
1.概念,有向树,根树,树叶,内点,分支点,
层数,树高,祖先,后代,父亲,儿子,兄弟,
有序树,m叉树,完全 m叉树,根子树,左子树,右子树,带权二叉树,最优二叉树,前缀,前缀码,二元前缀码,二叉树遍历等 ;
返回本章首页
2009-8-20
5
第三节 有向树与根树 (2)
2.定理,设 T是一棵根树,r是 T的树根,则对于 T的任一顶点 v,存在唯一的有向路从 r到 v；
3.算法,最优二叉树的 Huffman算法 ;
4.前缀码问题,前缀码与二叉树的对应关系；
5.二叉树的遍历,三种遍历方法,即先根遍历,中根遍历,后根遍历法,
返回本章首页
2009-8-20
6
第四节 平面图
平面图是很多实际问题的模型,例如在集成电路的布线设计中就遇到了平面图的问题,
1.基本概念,平面图,平面嵌入,面,无限面
(外部面 ),内部面,边界,次数等 ;
2.基本非平面图,K3,3与 K5；
3.平面图的欧拉公式；
4.平面图的判定,库拉图斯基定理,
返回本章首页
2009-8-20
7
本章小结
本章我们介绍树与平面图,但以介绍树为主,给出树的定义及树的充要条件,
生成树,最优生成树及最优生成树的克鲁斯卡尔算法,特别是二叉树,我们讨论了二叉树的 Huffman算法,前缀码,
二叉树的遍历等问题,最后介绍了一类实际背景很强的一类图 —— 平面图,
返回本章首页
1
第九章 树与平面图树是一类结构较为简单的图，是用途极为广泛的离散数学模型，特别是二叉树，
它在计算机科学中用得最多,因此在学习时应很好地掌握好诸如树的充要条件、
生成树、最优生成树、根树、树的各种算法、及二叉树的访问次序等内容,平面图是实际背景很强的一类图，能用本章介绍的方法判断一个图是否为平面图,
返回首页
2009-8-20
2
第一节 树的概念
本节介绍树的一些最基本的概念与结论,
1.概念有,树,树叶,分支点 (或内点 ),森林,
平凡树等
2.结论,设 G是 n阶无向图，则下列条件等价：
（ 1） G是树； (2） G连通并且删去 G的任一边,所得之图都不连通； (3） 对 G中的任意两点 u,v(u≠v),恰有一条从 u到 v
的简单路； (4） G不含回路,且 G有 n-1
条边； (5） G连通,且 G有 n-1条边,
返回本章首页
2009-8-20
3
第二节 生成树与最优支撑树
本节讨论连通图的生成树与连通权图的最优生成树 (或称为最优支撑树 ).
1.基本概念,生成树,余树,树枝,最优 (小 )
生成树等 ;
2.定理,图 G有生成树当且仅当 G是连通的；
3.算法,(1)无向连通图可采用破坏回路与不形成回路两种方法寻找生成树；
(2)权图中求最优生成树的两种算法,即克鲁斯卡尔算法与管梅谷的破圈法,
返回本章首页
2009-8-20
4
第三节 有向树与根树 (1)
有向树是有向图中结构最为简单的一类图,它是一种典型的非线性结构，在计算机算法分析、数据结构等方面有广泛的应用；在有向树中，根树最为重要，
我们主要考虑根树,
1.概念,有向树,根树,树叶,内点,分支点,
层数,树高,祖先,后代,父亲,儿子,兄弟,
有序树,m叉树,完全 m叉树,根子树,左子树,右子树,带权二叉树,最优二叉树,前缀,前缀码,二元前缀码,二叉树遍历等 ;
返回本章首页
2009-8-20
5
第三节 有向树与根树 (2)
2.定理,设 T是一棵根树,r是 T的树根,则对于 T的任一顶点 v,存在唯一的有向路从 r到 v；
3.算法,最优二叉树的 Huffman算法 ;
4.前缀码问题,前缀码与二叉树的对应关系；
5.二叉树的遍历,三种遍历方法,即先根遍历,中根遍历,后根遍历法,
返回本章首页
2009-8-20
6
第四节 平面图
平面图是很多实际问题的模型,例如在集成电路的布线设计中就遇到了平面图的问题,
1.基本概念,平面图,平面嵌入,面,无限面
(外部面 ),内部面,边界,次数等 ;
2.基本非平面图,K3,3与 K5；
3.平面图的欧拉公式；
4.平面图的判定,库拉图斯基定理,
返回本章首页
2009-8-20
7
本章小结
本章我们介绍树与平面图,但以介绍树为主,给出树的定义及树的充要条件,
生成树,最优生成树及最优生成树的克鲁斯卡尔算法,特别是二叉树,我们讨论了二叉树的 Huffman算法,前缀码,
二叉树的遍历等问题,最后介绍了一类实际背景很强的一类图 —— 平面图,
返回本章首页
