离散数学 第4-5章

1、计算机数学基础(上)第2编 图 论第四章第四章 几种特殊图几种特殊图第五章第五章 树树4.1 欧拉图一、欧拉图 在无向图中，从某一个结点出发，经过每边一次并且经过图中所有的结点(不一定一次)到达终点。如果终点与起点重合，则称为存在欧拉回路，如果终点与起点不重合，则称为存在欧拉通路。 存在欧拉回路的图称为欧拉图。 直观地说，一个无向图如果可以从一点出发，笔不离纸地一笔画出，就存在欧拉回路或欧拉通路，如果还能回到起点，就是欧拉图。欧拉图的判定 1。无向连通图是欧拉图的充分必要条件是图中不含有奇数度的结点。例题1： 无向图G是欧拉图，当且仅当 。 A) G中所有的结点的度数全为偶数 B) G中所有的

2、结点的度数全为奇数 C) G连通且所有的结点的度数全为偶数 D) G连通且所有的结点的度数全为奇数例题2： 无向连通图G含有欧拉回路的充分必要条件是C。不含有奇数度的结点例题3： 设G是无向图如右(彼得森图)，说明G不是欧拉图。解：因为无向图G中所有的结点的度数全为奇数，所以G不是欧拉图。 2。无向连通图存在欧拉通路的充分必要条件是图中只有两个奇数度的结点。 3。当n为奇数时，完全无向图Kn是欧拉图。例如K3、K5等。 4。当n为偶数时，完全无向图Kn不是欧拉图，也不存在欧拉通路。例题4：下列结论不正确的是（ ）。 A）无向连通图G是欧拉图的充分必要条件是G不含奇数度结点 B）非平凡连通图G有

3、欧拉通路的充分必要条件是G最多有两个奇数度结点 C）有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度 D）有向连通图D是有向欧拉图的充分必要条件是除两个结点外，每个结点的入度等于出度D例题5： 试问n为何值时，无向完全图Kn存在一条欧拉回路？解：因为无向连通图存在欧拉回路的充分必要条件是图中不含有奇数度结点。所以，无向完全图Kn如果存在一条欧拉回路，则它的每一个结点的度数都应为偶数，即n-1应为偶数，故n必为奇数。4.2 汉密尔顿图一、汉密尔顿图的定义 从图中的某一结点出发，如果存在一条只经过每个结点一次(不必经过所有边)的通路，则此通路称为汉密尔顿通路。如果还能回到起点，则称为

4、汉密尔顿回路。有汉密尔顿回路的图称为汉密尔顿图。 汉密尔顿图不仅可以是无向图，也可以是有向图。显然，非连通图一定不是汉密尔顿图。汉密尔顿通路与欧拉通路的区别是： 欧拉通路是经过每一边一次而且仅一次，但可以经过某些结点多次的通路， 汉密尔顿通路是经过每一结点一次而且仅一次，但可以不经过某些边的通路。汉密尔顿图的判定： 必要条件但不是充分条件定理： 1。在汉密尔顿图G中删除结点集V1后，GV1的连通分支数 。不满足这一条件的图一定不是汉密尔顿图。 充分条件但不是必要条件定理： 2。如果无向简单图G中任何一对结点的度数之和都大于等于结点数，则G中存在一条汉密尔顿回路。 3。把有n个结点的有向图D中边

5、的方向去掉，如果其中包含子图Kn，则D中存在汉密尔顿通路，当n3时，则D中存在汉密尔顿回路。|)(11VVGW例题6： 设图G=是简单图，若图中每对结点的度数之和 ，则G一定是汉密尔顿图。例题7： 设无向图=是汉密尔顿图，则V的任意子集V1，都有 |V1|。 |V)(1VGW4.3 平面图一、平面图的定义 如果把无向图G的所有结点和所有的边(可任意弯曲)画在平面上，使任何两条边都没有交叉点，则称G为平面图。否则，称为非平面图。例如K4 可画为 是平面图。 二、平面图的判定 1。如果把图G中的某些边弯曲可以使任何两边都不交叉，则G是平面图。否则是非平面图。例如，图 (a)、(b)、(c)，可用此

6、法画为平面图)(a)(b)(c 2。如果图G与图G同构，而G是平面图，则G是平面图。 也就是说，把图G中的各结点重新排列，把原来连接各结点的边，关联到这些结点重新排列后的位置上，如果可得到平面图。则原图是平面图。例如上例图(a)的解答可这样进行。abcdefgaebcdfg例题8： 设图G如右，作图G的嵌入图，说明图G是平面图。解：图G的嵌入图如下，故图G是平面图。 三、面的次数 1。在连通平面图中，由图的边所包围的，并且其内部不包含图的结点和边的区域称为图的一个面。 面分为有限面和无限面。 例如， r1 有两个面r1、r2，其中r2是无限面。 2。包围一个面的各边的回路称为面的边界，面的边界

7、的回路的长度称为面的次数，记作deg(r)。注意： 环内部的面的次数为1， 面内部的边在计算次数是要算2遍。2r例如， r1 r1的次数deg(r1)=6。四、次数定理 在平面图G=中，所有面的次数之和等于边数的2倍。即 。例题9： 在平面图G=中，则 ，其中 是G的面。|2)deg(Erriir1)deg(|2 Eir例题10： 设平面图G如右图求该平面图有多少个面，并用 等标出。 (2) 写出每个面的边，指出每个面的次数。解：(1)该平面图有3个面，环内的面为 ，矩形面为 ，外边的无限面为 ； (2) 的边有 ，次数为1， 的边有 ，次数为4， 图中所有的边都是的 边， 的次数为9。 ,1

8、0rr),(),(),(),(13344221vvvvvvvv0r1r2r0r1r0r),(11vv2r五、欧拉公式1。欧拉公式 在连通平面图G=中，有v个结点，e条边，r个面，则 ，该公式称为欧拉公式。 欧拉公式的应用非常广泛，应当记牢。推论 在简单连通平面图中，若v3，则证明：2rev63 veerrrrv2)deg(,3)deg(, 3)deg(, 3eveevreverre31322 ,32,3263,36veev则例题11： 设G是连通平面图，有v个结点，e条边，r个面，则 r= 。 A) e-v+2 B) v+e-2 C) e-v-2 D)e+v+2例题12： 设G是连通平面图，v

9、,e,r 分别表示G的结点数、边数和面数，则 v,e,r 满足的关系式是 。例题13：证明题 设G是平面图，并且G的所有面的次数均为3，证明 ,其中e是G的边数，v是G的结点数。证明：2revA63 ve3/2| |,|3)(deg2, 3)deg(errrer证毕, 63,36 , 3/|2veevevrev例题14： 设G是简单连通平面图，则它一定有一个度数不超过5的结点。（提示：用反证法）证明：假设G中不存在度数不超过5的结点， 则 由握手定理有 但G是连通简单平面图，根据欧拉公式应有 ，两者矛盾。 故G中一定有一个度数不超过5的结点。证毕。, 6)deg(ivvevvei3,6)deg

10、(2即63 ve六、库拉托夫斯基定理 1。K5和K3,3不是平面图。 2。一个图是平面图的充分必要条件是它不含K5或K3,3的子图。 3。当n5时，Kn一定不是平面图。它一定含K5。5K3,3K例题15： 设图G如右，那么G是 。 A) 平面图 B) 完全图 C) 欧拉图 D) 汉密尔顿图例题16： 设G是有5个结点的完全图，则G是 。 A) 无汉密尔顿通路 B) 无欧拉回路 C) 平面图 D) 欧拉图DD5.1 树的定义及性质一、树的定义与表示 1。连通且无回路的无向图称为树，用T表示。 T中的1度结点称为树叶，大于1度的结点称为分支点。 孤点称为平凡树，仅由树组成的无向图称为森林。 2。树

11、的性质 连通且无回路，|E|=|V|-1，增加任意一条边必出现回路，删除任意一条边必不连通，每对结点间仅有一条通路。 3。任何非平凡树中至少有2片树叶。二、生成树 1。生成树 若图G的生成子图是一棵树，则称此树是G的生成树。 2。树的补 图G中不属于生成树T的边的集合称为树T的补。 3。生成树的求法 一般可用破圈法做，即把图G中的回路去掉一条边，使它不再是回路。如此做下去，直到恰好把所有的回路都破坏掉，就得到了生成树。 用破圈法一共要去掉 条边。ve14。最小生成树 在带权图G中所生成的总权数最小的生成树称为最小生成树。5。最小生成树的求法破圈法 选取权数最大的边所在的回路，去掉其中权数最大的

12、边，如此做下去，直到求出生成树为止。这样求出的生成树一定是最小生成树。 还有一种方法称为避圈法。先去掉所有的边，然后从权数最小的边的开始，从小到大逐步选取，如果所选取的边和已选取的边构成了回路，则不选取这条边重新选取，直到连接完所有的结点。这样求出的树就是最小生成树。例题1： 设G=是有p个结点s条边的连通图，则从G中删去 条边，才能确定G的一棵生成树。解：设要删去k条边，例题2： 设G是有6个结点的完全图，从G中删去 条边则能得到树。 A) 6 B) 9 C) 10 D) 15 解：G是有6个结点的完全图，G中共有65/2=15条边，要使G成为树，G中只应留下5条边，故应删去10条边，选C。

13、Cpskpks1, 1例题3：以下命题为真的是（ ）。 A）无向完全图都是欧拉图 B）有n个结点n-1条边的无向图都是树 C）无向完全图都是平面图 D）树的每条边都是割边 例题4： 无向完全图 是（ ）。 A欧拉图 B. 汉密尔顿图 C. 树 D. 非平面图例题5： 设无向图G, 那么图G中V与E满足什么条件，图G一定是树。4KBD解：图G连通且EV1，那么图G一定是树。例题6： 带权图如右，求图的最小生成树解：选取含最大边(c,d)的回路cdec，删去其中权数最大的边(c,d)，然后再选取含最大边(a,b)的回路abea，删去其中权数最大的边(a,b)，再选取含最大边(c,e)的回路bceb

14、，删去其中权数最大的边(c,e)，再选取含最大边(a,d)的回路adea，删去其中权数最大的边(a,d)，即得最小生成树。T=。ab5dce3341216caedb1123 7)(TW例题7： 用避圈法求图G的最小生成树。 先去掉所有的边。从最小边(d,e)开始选取，再选取(d,a)，再选取(e,a)和(b,c)，但(e,a)构成回路，所以应去掉，再选取(c,a)，这时已连接了所有的结点，最小生成树求出。T=。abcde67548119161365764 6daebc5.2 根树的有关定义一、根树的定义 1。恰有一个顶点的入度为0，其余顶点的入度均为1的有向图称为根树。 根树中入度为0顶点称为树根，出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，树根和内点统称为分支点。 2。正则树与完全树 每个分支点的出度最多为m的树称为m叉树， 每个分支点的出度恰为m的树称为m叉正则树， 顶点到树根的长度称为该顶点的层树， 每个树叶的层数都相同的正则树称为完全树， m=2的二叉正则树简称为