推荐离散数学树

1、1第九章 常用图29.1.1 树及其基本性质树及其基本性质树树：不含回路的简单连通无向图。：不含回路的简单连通无向图。(a)1v2v3v4v5v叶叶：在树中，次数为：在树中，次数为1 1的结点。的结点。分支结点分支结点树枝树枝(b)森林森林439.1.1 树及其基本性质树及其基本性质定理定理9.1 在在(n,m)树中必有树中必有m=n-1。连通连通不包含回路不包含回路树定理定理9.3 图图g是树的充分必要条件是图是树的充分必要条件是图g的每对的每对结点间只有一条通路。结点间只有一条通路。在在t t中不相邻接的任意两结点间添加一条边后形中不相邻接的任意两结点间添加一条边后形成的图有且仅有一个圈成

2、的图有且仅有一个圈 49.1.1 树及其基本性质树及其基本性质定理定理9.2 具有两个结点以上的树必至少具有两个结点以上的树必至少 有两片叶。有两片叶。例1 14个结点的树：个结点的树：树是最小连通图，也是最大无回路图。树是最小连通图，也是最大无回路图。59.1.2 有向树有向树有向树：在有向图中如果不考虑边的方向有向树：在有向图中如果不考虑边的方向 而构成树。而构成树。(a)(b)外向树、内向树外向树、内向树 69.1.2 有向树有向树1v2v3v4v图1 外向树外向树: :有向树有向树t满足满足1)1)t仅有且仅有一个结点仅有且仅有一个结点 它的引入次数为它的引入次数为0;0;2)2)t的

3、其他结点的引入的其他结点的引入 次数均为次数均为1 1；3)3)t有一些结点，它的有一些结点，它的引出次数为引出次数为0 05v7v6v8v9v根叶分支结点分支结点根树79.1.2 有向树有向树1v2v3v图1 4v5v7v6v8v9v结点的级结点的级：由外向树的根到结点的通路长度。：由外向树的根到结点的通路长度。0 0级级2 2级级89.1.2 有向树有向树例例2. . 用外向树表示家族中的人员关系。用外向树表示家族中的人员关系。a ac cb父子关系父子关系 8.3 二元树de ef fhgij兄弟兄弟结点结点有有序序树树99.1.2 有向树有向树1v2v3v4v图2 内向树内向树: :有

4、向树有向树t满足满足1)1)t仅有且仅有一个结点仅有且仅有一个结点 它的引它的引出出次数为次数为0;0;2)2)t的其他结点的引的其他结点的引出出 次数均为次数均为1 1；3)3)t有一些结点，它的有一些结点，它的引引入入次数为次数为0 0。5v7v6v8v9v根叶分支结点分支结点109.1.3 二元树二元树), 2 , 1( ,)(degnimvim元树：一元树：一n个结点的外向树如果满足个结点的外向树如果满足 例例3. 3. 3 3元树元树2 2元树元树3 3元完全树元完全树2 2元完全树元完全树m元完全树：元完全树：如满足如满足( (除叶外除叶外) ) ), 2 , 1( ,)(degn

5、imvi11abcdefghijk(a)1)1)从根开始，保留每个父亲与从根开始，保留每个父亲与 其最左边儿子的连线，撤消其最左边儿子的连线，撤消 与别的儿子的连线；与别的儿子的连线；9.1.3 二元树二元树有序树转化为二元树的一般步骤：有序树转化为二元树的一般步骤：2) 2) 兄弟间用从左向右的有向边连接；兄弟间用从左向右的有向边连接；3)3)左儿子为直接处于给定结点下面的结点；左儿子为直接处于给定结点下面的结点；右儿子为处于同一水平线上与给定结点右邻的结点。右儿子为处于同一水平线上与给定结点右邻的结点。 129.1.3 二元树二元树abcdefghijk(a)abcdefghijk(b)a

6、bdcefgjikh(c)二元树省略边的方向139.1.3 二元树二元树v1v2v3v4v5v6v7v8v9v10v11(a)v1v2v5v3v6v4v7v9v8v10v11149.1.3 二元树二元树一个森林转换为二元树的一般步骤：一个森林转换为二元树的一般步骤：1) 先把森林中的每棵树表示成二元树；先把森林中的每棵树表示成二元树；2) 除第一棵二元树外，依次将每棵二元除第一棵二元树外，依次将每棵二元 树作为左边二元树的根的右子树。树作为左边二元树的根的右子树。159.1.3 二元树二元树abcdfgjihe图图1 1beacdfigjh169.1.4 生成树生成树生成子图evg,evgvv

7、 ee 生成树：若连通图生成树：若连通图g的生成子图是一棵树。的生成子图是一棵树。 无向图无向图179.1.4 生成树生成树- -破圈法破圈法破圈法：破圈法： 在在g中寻找基本回路，找到后在此回路中中寻找基本回路，找到后在此回路中删除一条边，重复该过程，直至删除一条边，重复该过程，直至g g中无基本中无基本回路出现为止。回路出现为止。189.1.4 生成树生成树- -破圈法破圈法abcdeabcde 一个连通图可以有很多个生成树一个连通图可以有很多个生成树。199.1.4 生成树生成树- -避圈法避圈法abcdeabcde避圈法209.1.4 生成树生成树- -避圈法避圈法练习：练习：5219

8、.1.4 生成树生成树- -练习练习例 设有6个城市，它们间有输油管道连通，为了保卫油管不受破坏，在每段油管间必须派一连士兵看守，为保证正常供应，最少需多少连士兵看守？ 1v2v3v4v5v6v229.1.4 最小最小生成树生成树设设 是一连通的有权图，则是一连通的有权图，则g中中具有最小权的生成树。具有最小权的生成树。 最小生成树evg,现实意义239.1.4 最小最小生成树生成树kruskal算法算法要点：在与已选取的边不成圈的边中要点：在与已选取的边不成圈的边中 选取最小者。选取最小者。构造249.1.4 最小最小生成树生成树例 设有6个城市，它们间有输油管道连通，为了减少消耗，应如何铺

9、设输油管道？ 1v2v3v4v5v6v215421223441v2v3v4v5v6vkruskal破圈法8259.1.4 最小最小生成树生成树练习：41210615871192326补充：补充：二元树的应用二元树的应用1.表达式方法是：将表达式的运算符作为分支结点，方法是：将表达式的运算符作为分支结点， 将运算量作为叶结点画出二叉树。将运算量作为叶结点画出二叉树。 27)/(/ )(7654321vvvvvvv例1+/3v-2v1v4v*-5v/6v7v补充：补充：二元树的应用二元树的应用28补充：补充： 二元树的应用二元树的应用- -练习练习)6/()2(cbbaa练习：练习：/*-a+*c

10、a*2b6b29补充：补充：二元树的应用二元树的应用2.前缀码由由0 0和和1 1的字符串组成的集合叫前缀码，其中集合的的字符串组成的集合叫前缀码，其中集合的每个元素都不是另一元素的前缀（即左子串）。每个元素都不是另一元素的前缀（即左子串）。 如集合00,10,11,010,011是前缀码? 00,01,00130补充：补充：二元树的应用二元树的应用给定一棵二元树，对每个分支点引出的给定一棵二元树，对每个分支点引出的左侧的边标记为左侧的边标记为0 0，右侧的边标记为，右侧的边标记为1 1。 abdcfe0011000,010,011任一二元树的树叶集合任一二元树的树叶集合一个前缀码一个前缀码3

11、1补充：补充：二元树的应用二元树的应用练习：给出与前缀码给出与前缀码00,10,11,010,011对应的二元树。对应的二元树。00110101000100111011329.2 平面图平面图印刷电路布线33电路布线abc123349.2.1 平面图的基本概念(a)平面图平面图：设无向图：设无向图 , ,如果能把如果能把g的的所有结点和边画在平面上，使得任何两条边所有结点和边画在平面上，使得任何两条边除公共结点外没有其他的交点。除公共结点外没有其他的交点。 evg,(b)359.2.1 平面图的基本概念(c)当且仅当一个图的当且仅当一个图的每个每个连通分支都是平面图连通分支都是平面图时，时，这

12、个图是平面图。这个图是平面图。 369.2.1 平面图的基本概念(a)(b)5k(d)3 , 3k(c)(e)379.2.1 平面图的基本概念无回路的图是平面图。无回路的图是平面图。一种判别平面图的直观方法：一种判别平面图的直观方法： 对于有回路的图找出一个长度尽可能大的且对于有回路的图找出一个长度尽可能大的且 边不相交的基本回路。边不相交的基本回路。(2) (2) 将图中那些相交于非结点的边，适当放置在已选定将图中那些相交于非结点的边，适当放置在已选定 的基本回路内侧或外侧，若能避免除结点之外边的的基本回路内侧或外侧，若能避免除结点之外边的 相交，则该图是平面图；否则，便是非平面图。相交，则

13、该图是平面图；否则，便是非平面图。389.2.1 平面图的基本概念(a)(b)1v2v3v4v5v1v3v4v5v2v1v2v3v4v5v39(d)9.2.1 平面图的基本概念3 , 3k(b)5k波兰数学家库拉托夫斯基库拉托夫斯基(k.kuratowski)1930判别平面图充要条件判别平面图充要条件409.2.2 平面图的区域abcde123平面图的区域平面图的区域: :平面图中四周平面图中四周 为边所包围的最小平面块。为边所包围的最小平面块。边界：包围区域的回路称为此边界：包围区域的回路称为此 区域的边界。区域的边界。 区域面积为有限者称为有限区域。区域面积为有限者称为有限区域。1，2无

14、限区域长度称为面的次数deg(1)419.2.2 平面图的区域abdehcfg1234?区域1：(a,b,c,a)2: (b,d,e,b)3:(b,c,e,b)4:(a,b,d,e,c,a)一个平面图有一个惟一的无限区域。 429.2.2 平面图的区域1750定理定理9.4：设图设图g是一个是一个(n,m)连通平面图，连通平面图， 它的区域数为它的区域数为r，则有欧拉公式，则有欧拉公式2rmn归纳法(m)439.2.2 平面图的区域定理定理9.5 设图设图g是一个是一个(n,m)连通平面图，连通平面图， 且图且图g g中无环，其边数大于中无环，其边数大于1 1，则必有，则必有 63 nm44(

15、d)9.2.2 平面图的区域3 , 3k5k3n-6=910=m2n-4=89=m定理定理: :若若g g是每个面由是每个面由4 4条或条或4 4条以上的边围成的连通平面条以上的边围成的连通平面图，则有图，则有 42 nm459.2.3 判别平面图的库拉托夫斯基定理5k3 , 3k库拉托夫斯基图abcdeabcdew1w2w3w4w55k彼得松图彼得松图469.2.3 判别平面图的库拉托夫斯基定理479.2.3 判别平面图的库拉托夫斯基定理库拉托夫斯基定理：库拉托夫斯基定理：一个图是平面图一个图是平面图它的任何子图都不可能减缩到它的任何子图都不可能减缩到3 , 3k489.2.3 判别平面图的

16、库拉托夫斯基定理练习：判断下图是否为平面图。123456781234567849练习：如果无向图g的节点数n11，证明g与g的补图 至少有一个不是平面图。g练习：证明：若g与补图均为平面图，设它们的边数分别为m1和m2.m13n-633-6=27 m23n-633-6=27 m1+m25450练习：n个结点的无向完全图的边数 2) 1(2nncmn55211 c根据补图的定义根据补图的定义m1+m2=mm1+m255 矛盾519.3 9.3 两步图两步图二部图偶图52两步图1v2v3v4v5v6v7v,7654321vvvvvvvv 两步图两步图互补结点子集53两步图1v2v3v4v5v6v7v4定理定理9.7 图图g是一个两步图的充分条件是