离散数学 第4-5章.ppt

计算机数学基础(上)第2编 图 论 第四章 几种特殊图 第五章 树 4.1 欧拉图 一、欧拉图 在无向图中，从某一个结点出发，经过每边一次 并且经过图中所有的结点(不一定一次)到达终点。如 果终点与起点重合，则称为存在欧拉回路，如果终 点与起点不重合，则称为存在欧拉通路。 存在欧拉回路的图称为欧拉图。 直观地说，一个无向图如果可以从一点出发，笔 不离纸地一笔画出，就存在欧拉回路或欧拉通路， 如果还能回到起点，就是欧拉图。 欧拉图的判定 1。无向连通图是欧拉图的充分必要条件是图中 不含有奇数度的结点。 例题1： 无向图G是欧拉图，当且仅当 。 A) G中所有的结点的度数全为偶数 B) G中所有的结点的度数全为奇数 C) G连通且所有的结点的度数全为偶数 D) G连通且所有的结点的度数全为奇数 例题2： 无向连通图G含有欧拉回路的充分必要条件是 例题3： 设G是无向图如右(彼得森图)， 说明G不是欧拉图。 解：因为无向图G中所有的 结点的度数全为奇数，所以 G不是欧拉图。 2。无向连通图存在欧拉通路的充分必要条件是图 中只有两个奇数度的结点。 3。当n为奇数时，完全无向图Kn是欧拉图。例 如K3、K5等。 4。当n为偶数时，完全无向图Kn不是欧拉图，也 不存在欧拉通路。 例题4： 下列结论不正确的是（ ）。 A）无向连通图G是欧拉图的充分必要条件是G不含奇数度结点 B）非平凡连通图G有欧拉通路的充分必要条件是G最多有两个奇数度结点 C）有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度 D）有向连通图D是有向欧拉图的充分必要条件是除两个结点外，每个结点的入度等于出度 例题5： 试问n为何值时，无向完全图Kn存在一条欧拉回 路？ 解：因为无向连通图存在欧拉回路的充分必要条件是 图中不含有奇数度结点。所以，无向完全图Kn如果存 在一条欧拉回路，则它的每一个结点的度数都应为偶 数，即n-1应为偶数，故n必为奇数。 4.2 汉密尔顿图 一、汉密尔顿图的定义 从图中的某一结点出发，如果存在一条只经过 每个结点一次(不必经过所有边)的通路，则此通路称 为汉密尔顿通路。如果还能回到起点，则称为汉密 尔顿回路。有汉密尔顿回路的图称为汉密尔顿图。 汉密尔顿图不仅可以是无向图，也可以是有向 图。显然，非连通图一定不是汉密尔顿图。 汉密尔顿通路与欧拉通路的区别是： 欧拉通路是经过每一边一次而且仅一次，但可 以经过某些结点多次的通路， 汉密尔顿通路是经过每一结点一次而且仅一 次，但可以不经过某些边的通路。 汉密尔顿图的判定： 必要条件但不是充分条件定理： 1。在汉密尔顿图G中删除结点集V1后，G－V1的 连通分支数 　　。不满足这一条件的图一 定不是汉密尔顿图。 充分条件但不是必要条件定理： 2。如果无向简单图G中任何一对结点的度数之和 都大于等于结点数，则G中存在一条汉密尔顿回路。 3。把有n个结点的有向图D中边的方向去掉，如果 其中包含子图Kn，则D中存在汉密尔顿通路，当n≥3 时，则D中存在汉密尔顿回路。 例题6： 设图G=V,E是简单图，若图中每对结点 的度数之和 ，则G一定是汉密尔顿图。 例题7： 设无向图Ｇ=V,E是汉密尔顿图，则V的 任意子集V1，都有 |V1|。 4.3 平面图 一、平面图的定义 如果把无向图G的所有结点和所有的边(可任意 弯曲)画在平面上，使任何两条边都没有交叉点，则 称G为平面图。否则，称为非平面图。 例如K4 可画为 是平面图。 二、平面图的判定 1。如果把图G中的某些边弯曲可以使任何两边 都不交叉，则G是平面图。否则是非平面图。 例如，图 (a)、(b)、(c)，可用此法画为平面图 2。如果图G与图G’同构，而G’是平面图，则G是 平面图。 也就是说，把图G中的各结点重新排列，把原来 连接各结点的边