《计算机数学基础(上) 第3编 图论》由会员分享，可在线阅读，更多相关《计算机数学基础(上) 第3编 图论（26页珍藏版）》请在金锄头文库上搜索。
1、计算机数学基础(上)第3编 图 论第六章 几种特殊的图本章主要内容： 欧拉图 哈密顿图 平面图 树重点：欧拉图、哈密顿图、平面图、欧拉 公式、生成树 难点：哈密顿图、平面图、最小生成树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不是欧拉图， 也 不存在欧拉通路。20
3、01年7月化简解答题13。试问n为何值时，无向完全图Kn存在一条欧拉回路？ 解：因为无向连通图存在欧拉回路的充分必要条件 是 图中不含有奇数度结点。所以，无向完全图Kn的结 点 度数应为偶数，即n-1为偶数，则n为奇数。三、中国邮路问题邮递员从邮局出发，走遍辖区内所有的街道至 少 一次(可以重复)，最后回到邮局。要走怎样的路线全程才最短，这一问题就称为中国邮路问题。中国邮路问题可以转化成图的问题来解。以街道为边，街道的长度为边的权，以邮局和 街 道的交叉点为结点，得到带权图G。如G中不含有奇数度结点，则G是欧拉图。以邮 局 为起点的欧拉回路就是问题的解。如G中含有奇数度结点，则可在这些奇数度结
4、点 间 添加新的边，使原有的某些边成为双边，并且使添 加 的边的权数之和最小。这样一来G的结点就都成为偶 数度的结点，G就成了欧拉图，从而求出问题的解。因此，求中国邮路问题的解就是在G中添加一些边，使图中所有的结点的度数都变成偶数。求添加 的 边的权数之和最小的添法。6.2 哈密顿图和货郎担问题 一、哈密顿图的定义从图中的某一结点出发，如果存在一条只经过 每个结点一次(不必经过所有的边)的通路，则此通 路 称为哈密顿通路。如果还能回到起点，则称为哈密 顿回路。存在哈密顿回路的图称为哈密顿图。哈密顿图不仅可以是无向图，也可以是有向图 。显然，非连通图一定不是哈密顿图。 哈密顿通路与欧拉通路的区别
5、是：欧拉通路是经过每一边一次而且仅一次，但可 以经过某些结点多次的通路，哈密顿通路是经过每一结点一次而且仅一次， 但可以不经过某些边的通路。二、哈密顿图的判定1。在哈密顿图G中删除结点集V1后，GV1的 连 通分支数 。不满足这一条件的图一 定 不是哈密顿图。2。如果无向简单图G中任何一对结点的度数之 和都大于等于结点数，则G中存在一条哈密顿回路。2001年1月填空题9设图G=是简单图，若图中每对结点的度 数 之和 ，则G一定是哈密顿图。3。把有n个结点的有向图D中边的方向去掉，如 果 其中包含子图Kn，则D中存在哈密顿通路，当n3时 ， 则D中存在哈密顿回路。6.3 平面图与图的着色一、平面
6、图的定义如果把无向图G的所有结点和所有的边(可任意 弯曲)画在平面上，使任何两条边都没有交叉点， 则 称G为平面图。否则，称为非平面图。例如K4 可画为 是平面图。二、平面图的判定1。如果把图G中的某些边弯曲可以使任何两 边 都不交叉，则G是平面图。否则是非平面图。 例如，课本 P.229 图6-55 (a)、(b)、(c)，可画为2。如果图G与图G同构，而G是平面图，则G 是 平面图。也就是说，把图G中的各结点重新排列，把原来连接各结点的边，关联到这些结点重新排列后的位 置 上，如果可得到平面图。则原图是平面图。 课本 P.338 的解答就是这样的。 例如，图6-55 (a)三、面的次数1。
7、在连通平面图中，由图的边所包围的，并且 其 内部不包含图的结点和边的区域称为图的一个面。面分为有限面和无限面。例如， r1 有两个面r1、r2，其中r2是无限面 。2。包围一个面的各边的回路称为面的边界，面 的边界的回路的长度称为面的次数，记作deg(r)。 注意： 环内部的面的次数为1， 面内部的边在计算次数是要算2遍。例如， r1 r1的次数deg(r1)=6。四、次数定理在平面图G=中，所有面的次数之和等于 边数的2倍。即 。2001年7月填空题10在平面图G=中，则 ， 其中 是G的面。五、欧拉公式 1。欧拉公式在连通平面图G=中，有v个结点，e条边 ， r个面，则 ，该公式称为欧拉公
8、式。欧拉公式的应用非常广泛，应当记牢。 推论在简单连通平面图中，若v3，则证明：2001年7月选择题5设G是连通平面图，有v个结点，e条边，r个面， 则 r= 。A) e-v+2 B) v+e-2 C) e-v-2 D)e+v+2 2000年7月填空题8设G是连通平面图，v,e,r 分别表示G的结点数、 边 数和面数，则 v,e,r 满足的关系式是 。 2000年1月证明题19设G是平面图，并且G的所有面的次数均为3，证 明,其中e是G的边数，v是G的结点数。证明：A六、库拉托夫斯基定理1。K5和K3,3不是平面图。2。一个图是平面图的充分必要条件是它不含K5 或 K3,3的子图。 3。当n5
9、时，Kn一定不是平面图。它一定含K5 。2000年1月选择题3设图G如右，那么G是 。A) 平面图 B) 完全图 C) 欧拉图 D) 哈密顿图2000年7月选择题4设G是有5个结点的完全图，则G是 。A) 无哈密顿通路 B) 无欧拉回路 C) 平面图 D) 欧拉图DD6.4 树一、树的定义1。连通且无回路的无向图称为树，用T表示。T中的1度结点称为树叶，大于1度的结点称为 分 支点。孤点称为平凡树，仅由树组成的无向图称为森 林。2。树的性质连通且无回路，|E|=|V|-1，增加任意一 条 边必出现回路，删除任意一条边必不连通，每对结点间仅有一条通路。3。任何非平凡树中至少有2片树叶。2000年
10、7月化简解答题13在一棵有2个2度结点，4个3度结点，其余为 树 叶的无向图中应该有几片树叶？画出两棵不同构的满足条件的无向树T1、T2 。 解：设有k片树叶，则v=k+6， 解得 ，故有6片树叶。二、生成树1。生成树若图G的生成子图是一棵树，则称此树是G的 生 成树。2。树的补图G中不属于生成树T的边的集合称为树T的 补。3。生成树的求法一般可用破圈法做，即把图G中的回路去掉一条边，使它不再是回路。如此做下去，直到恰好把 所有的回路都破坏掉，就得到了生成树。用破圈法一共要去掉 条边。2000年1月填空题8设G=是有p个结点，s条边的连通图，则从 G 中删去 条边，才能确定G的一棵生成树。 解
11、：设要删去k条边， 2000年7月选择题3设G是有6个结点的完全图，从G中删去 条边则能得到树。A) 6 B) 9 C) 10 D) 15 解：G是有6个结点的完全图，G中共有 65/2=15 条边，要使G成为树，G中只应留下5条边，故应删 去 10条边，选C。C4。最小生成树在带权图G中所生成的总权数最小的生成树称 为 最小生成树。 5。最小生成树的求法选取权数最大的边所在的回路，去掉其中权数 最大的边，如此做下去，直到求出生成树为止。这 样求出的生成树一定是最小生成树。还有一种方法称为克鲁斯特尔算法。先去掉所 有 的边，然后从权数最小的边的开始，从小到大逐步 选 取，如果所选取的边和已选取
12、的边构成了回路，则 不 选取这条边重新选取，直到连接完所有的结点。这 样 求出的树就是最小生成树。2000年1月化简解答题14(2)带权图如右，求图的最小生成树解：选取含最大边(c,d)的回路cdec， 删去其中权数最大的边(c,d)，然后 再选取含最大边(a,b)的回路abea， 删去其中权数最大的边(a,b)，再选取含最大边(c,e) 的 回路bceb，删去其中权数最大的边(c,e)，再选取含 最 大边(a,d)的回路adea，删去其中权 数最大的边(a,d)，即得最小生成树。 T=。2001年1月计算题17求图G的一棵最小生成树。解：解法二：用克鲁斯特尔算法做，先去掉所有的边。从最小 边(d,e)开始选取，再选取(d,a)， 再选取(e,a)和(b,c)，但(e,a)构成 回路，所以应去掉，再选取(c,a)，这时已连接了所有的结点，最小 生成树求出。 T=。
