离散数学第4章几种特殊图

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)，可用此法画为平面图)(a

6、)(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如右图(1) 求该平面图有多少个面，并用 等标出。 (2) 写出每个面的边，指出每个面的次数。解：(1)该平面图有3个面，环内的面为 ，矩形面为 ，外边的无限面为 ； (2) 的边有 ，次数为1， 的边有 ，次数为4， 图中所有的边都是的 边， 的次数为9。 ,10rr),

8、(),(),(),(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,e,r

9、分别表示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(2即63 ve六、库拉托夫斯基定理 1。K5和K3,3不是平面图。 2。一个图是平面图的充分必要条件是它不含K5或K3