1、 计算机数学基础(上)第3编 图 论第六章 几种特殊的图本章主要内容：1.欧拉图2.哈密顿图3.平面图4.树重点：欧拉图、哈密顿图、平面图、欧拉公式、生成树难点：哈密顿图、平面图、最小生成树6.1 拉 和中 路欧 图 国邮 问题 一、欧拉图的定义在无向图中，从某一个结点出发，经过每边一次并且经过图中所有的结点(不一定一次)到达终点。如果终点与起点重合，则称为存在欧拉回路，如果终点与起点不重合，则称为存在欧拉通路。存在欧拉回路的图称为欧拉图。直观地说，一个无向图如果可以从一点出发，笔不离纸地一笔画出，就存在欧拉回路或欧拉通路，如果还能回到起点，就是欧拉图。二、欧拉图的判定1。无向连通图是欧拉图的
2、充分必要条件是图中不含有奇数度的结点。2001年1月选择题4。无向图G是欧拉图，当且仅当 。A) G中所有的结点的度数全为偶数B) G中所有的结点的度数全为奇数C) G连通且所有的结点的度数全为偶数D) G连通且所有的结点的度数全为偶数C2000年1月化简解答题14(1)。设G是无向图如右(彼得森图)，说明G不是欧拉图。解：因为无向图G中所有的结点的度数全为奇数，所以G不是欧拉图。2。无向连通图存在欧拉通路的充分必要条件是图中只有两个奇数度的结点。3。当n为奇数时，完全无向图Kn是欧拉图。例如，K3、K5等。4。当n为偶数时，完全无向图Kn不是欧拉图，也不存在欧拉通路。2001年7月化简解答题
3、13。试问n为何 时，无向完全图Kn存在一条欧拉回路 解：因为无向连通图存在欧拉回路的充分必要条件是图中不含有奇数度结点。所以，无向完全图Kn的结点度数 为偶数， n-1为偶数，则n为奇数。、中国邮路问题邮 从邮 出发， 所有的 一次(可以重 )，最 回到邮 。要 的路 全最 ， 一问题就称为中国邮路问题。中国邮路问题可以 化成图的问题 解。以 为边， 的 度为边的 ，以邮 的 点为结点，得到 图G。如G中不含有奇数度结点，则G是欧拉图。以邮 为起点的欧拉回路就是问题的解。如G中含有奇数度结点，则可在 奇数度结点的边，currency1有的某边成为边，并且的边的 数“ 最小。 一 G的结点就成
4、为偶数度的结点，G就成欧拉图，从fi出问题的解。因fl，fi中国邮路问题的解就是在G中一边，图中所有的结点的度数 成偶数。fi的边的 数“ 最小的。6.2 哈密 和 担顿图 问题一、哈密顿图的定义从图中的某一结点出发，如果存在一条只经过每个结点一次(不必经过所有的边)的通路，则fl通路称为哈密顿通路。如果还能回到起点，则称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。哈密顿图不仅可以是无向图，也可以是有向图。 ，连通图一定不是哈密顿图。哈密顿通路与欧拉通路的 是：欧拉通路是经过每一边一次且仅一次，可以经过某结点次的通路，哈密顿通路是经过每一结点一次且仅一次，可以不经过某边的通路。二、哈密顿图的判定1。在哈密顿图G中”结点V1 ，GV1的连通分 数 。不 一条件的图一定不是哈密顿图。2。如果无向简图G中何一结点的度数“等结点数，则G中存在一条哈密顿回路。2001年1月题9设图G=是简图， 图中每结点的度数“ ，则G一定是哈密顿图。3。有n个结点的有向图D中边的向 ，如果中含图Kn，则D中存在哈密顿通路，当n3时，则D中存在哈密顿回路。|)( 11 VVGP |V6.3 平面 的着色图与图一、平面图的定义如果无向图G的所有结点 所有的边(可 )画在平面 ，何两条边 有 点，则称G为平面图。 则，称为平面图。例如K4 可画为 是平面图。
