离散数学 树.ppt

第九章 常用图 补充：二元树的应用 练习： 给出与前缀码{00,10,11,010,011}对应的二元树。 0 0 1 1 0 1 0 1 00 010 011 10 11 §9.2 平面图 印刷电路布线 电路布线 a b c 1 2 3 9.2.1 平面图的基本概念 (a) 平面图：设无向图 ,如果能把G的 所有结点和边画在平面上，使得任何两条边 除公共结点外没有其他的交点。 (b) 9.2.1 平面图的基本概念 (c) 当且仅当一个图的每个 连通分支都是平面图时， 这个图是平面图。 9.2.1 平面图的基本概念 (a) (b) (d) (c) (e) 9.2.1 平面图的基本概念 无回路的图是平面图。 一种判别平面图的直观方法： 对于有回路的图找出一个长度尽可能大的且 边不相交的基本回路。 (2) 将图中那些相交于非结点的边，适当放置在已选定 的基本回路内侧或外侧，若能避免除结点之外边的 相交，则该图是平面图；否则，便是非平面图。 9.2.1 平面图的基本概念 (a) (b) (d) 9.2.1 平面图的基本概念 (b) 波兰数学家 库拉托夫斯基 (K.Kuratowski) 1930 判别平面图充要条件 9.2.2 平面图的区域 a b c d e 1 2 3 平面图的区域:平面图中四周 为边所包围的最小平面块。 边界：包围区域的回路称为此 区域的边界。 区域面积为有限者称为有限区域。 1，2 无限区域 长度称为面的次数 deg(1) 9.2.2 平面图的区域 a b d e h c f g 1 2 3 4 ?区域 1：(a,b,c,a) 2: (b,d,e,b) 3:(b,c,e,b) 4:(a,b,d,e,c,a) 一个平面图有一个惟一的无限区域。 9.2.2 平面图的区域 1750 定理9.4：设图G是一个(n,m)连通平面图， 它的区域数为r，则有欧拉公式 归纳法(m) 9.2.2 平面图的区域 定理9.5 设图G是一个(n,m)连通平面图， 且图G中无环，其边数大于1，则必有 (d) 9.2.2 平面图的区域 3n-6=910=m 2n-4=89=m 定理:若G是每个面由4条或4条以上的边围成的连通平面图，则有 9.2.3 判别平面图的库拉托夫斯基定理 库拉托夫斯基图 A B C D E a b c d e w1 w2 w3 w4 w5 彼得松图 9.2.3 判别平面图的库拉托夫斯基定理 9.2.3 判别平面图的库拉托夫斯基定理 库拉托夫斯基定理： 一个图是平面图 它的任何子图都不可能减缩到 9.2.3 判别平面图的库拉托夫斯基定理 练习：判断下图是否为平面图。 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 8 练习：如果无向图G的节点数n≥11，证明G与G的补图 至少有一个不是平面图。 练习： 证明：若G与补图均为平面图，设它们的边数 分别为m1和m2. m1≦3n-6≦33-6=27 m2≦3n-6≦33-6=27 m1+m2≦54 * * 9.1.1 树及其基本性质 树：不含回路的简单连通无向图。 (a) 叶：在树中，次数为1的结点。 分支结点 树枝 (b) 森林 4 9.1.1 树及其基本性质 定理9.1 在(n,m)树中必有m=n-1。 连通 不包含回路 树 定理9.3 图G是树的充分必要条件是图G的每对 结点间只有一条通路。 在T中不相邻接的任意两结点间添加一条边后形成的图有且仅有一个圈 9.1.1 树及其基本性质 定理9.2 具有两个结点以上的树必至少 有两片叶。 例1 1~4个结点的树： 树是最小连通图，也是最大无回路图。 9.1.2 有向树 有向树：在有向图中如果不考虑边的方向 而构成树。 (a) (b) 外向树、内向树 9.1.2 有向树 图1 外向树:有向树T满足 1)T仅有且仅有一个结点 它的引入次数为0; 2)T的其他结点的引入 次数均为1； 3)T有一些结点，它的 引出次数为0 根 叶 分支结点 根树 9.1.2 有向树 图1 结点的级：由外向树的根到结点的通路长度。 0级 2级 9.1.2 有向树 例2. 用外向树表示家族中的人员关系。 a c b 父子关系 8.3 二元树 d e f h g i j 兄弟结点 有序树 9.1.2 有向树 图2 内向树:有向树T满足 1)T仅有且仅有一个结点 它的引出次数为0; 2)T的其他结点的引出 次数均为1； 3)T有一些结点，它的 引入次数为0。 根 叶 分支结点 9.1.3 二元树 m元树：一n个结点的外向树如果满足 例3.