计算机数学基础(上)第3编图论本章主要内容：6.1欧拉图和中国邮路问题二、欧拉图的判定1。无向连通图是欧拉图的充分必要条件是图中不含有奇数度的结点。[2001年1月选择题4]。无向图G是欧拉图，当且仅当。A)G中所有的结点的度数全为偶数B)G中所有的结点的度数全为奇数C)G连通且所有的结点的度数全为偶数D)G连通且所有的结点的度数全为偶数[2000年1月化简解答题14(1)]。设G是无向图如右(彼得森图)，说明G不是欧拉图。解：因为无向图G中所有的结点的度数全为奇数，所以G不是欧拉图。2。无向连通图存在欧拉通路的充分必要条件是图中只有两个奇数度的结点。3。当n为奇数时，完全无向图Kn是欧拉图。例如，K3、K5等。4。当n为偶数时，完全无向图Kn不是欧拉图，也不存在欧拉通路。[2001年7月化简解答题13]。试问n为何值时，无向完全图Kn存在一条欧拉回路？解：因为无向连通图存在欧拉回路的充分必要条件是图中不含有奇数度结点。所以，无向完全图Kn的结点度数应为偶数，即n-1为偶数，则n为奇数。三、中国邮路问题邮递员从邮局出发，走遍辖区内所有的街道至少一次(可以重复)，最后回到邮局。要走怎样的路线全程才最短，这一问题就称为中国邮路问题。中国邮路问题可以转化成图的问题来解。以街道为边，街道的长度为边的权，以邮局和街道的交叉点为结点，得到带权图G。如G中不含有奇数度结点，则G是欧拉图。以邮局为起点的欧拉回路就是问题的解。如G中含有奇数度结点，则可在这些奇数度结点间添加新的边，使原有的某些边成为双边，并且使添加的边的权数之和最小。这样一来G的结点就都成为偶数度的结点，G就成了欧拉图，从而求出问题的解。因此，求中国邮路问题的解就是在G中添加一些边，使图中所有的结点的度数都变成偶数。求添加的边的权数之和最小的添法。6.2哈密顿图和货郎担问题二、哈密顿图的判定1。在哈密顿图G中删除结点集V1后，G－V1的连通分支数。不满足这一条件的图一定不是哈密顿图。2。如果无向简单图G中任何一对结点的度数之和都大于等于结点数，则G中存在一条哈密顿回路。[2001年1月填空题9]设图G=<V,E>是简单图，若图中每对结点的度数之和，则G一定是哈密顿图。3。把有n个结点的有向图D中边的方向去掉，如果其中包含子图Kn，则D中存在哈密顿通路，当n≥3时，则D中存在哈密顿回路。6.3平面图与图的着色二、平面图的判定1。如果把图G中的某些边弯曲可以使任何两边都不交叉，则G是平面图。否则是非平面图。例如，课本P.229图6-55(a)、(b)、(c)，可画为2。如果图G与图G’同构，而G’是平面图，则G是平面图。也就是说，把图G中的各结点重新排列，把原来连接各结点的边，关联到这些结点重新排列后的位置上，如果可得到平面图。则原图是平面图。课本P.338的解答就是这样的。例如，图6-55(a)三、面的次数1。在连通平面图中，由图的边所包围的，并且其内部不包含图的结点和边的区域称为图的一个面。面分为有限面和无限面。例如，r1有两个面r1、r2，其中r2是无限面。2。包围一个面的各边的回路称为面的边界，面的边界的回路的长度称为面的次数，记作deg(r)。注意：⑴环内部的面的次数为1，⑵面内部的边在计算次数是要算2遍。例如，r1r1的次数deg(r1)=6。四、次数定理在平面图G=<V,E>中，所有面的次数之和等于边数的2倍。即。[2001年7月填空题10]在平面图G=<V,E>中，则，其中是G的面。五、欧拉公式1。欧拉公式在连通平面图G=<V,E>中，有v个结点，e条边，r个面，则，该公式称为欧拉公式。欧拉公式的应用非常广泛，应当记牢。[推论]在简单连通平面图中，若v≥3，则证明：[2001年7月选择题5]设G是连通平面图，有v个结点，e条边，r个面，则r=。A)e-v+2B)v+e-2C)e-v-2D)e+v+2[2000年7月填空题8]设G是连通平面图，v,e,r分别表示G的结点数、边数和面数，则v,e,r满足的关系式是。[2000年1月证明题19]设G是平面图，并且G的所有面的次数均为3，证明,其中e是G的边数，v是G的结点数。证明：六、库拉托夫斯基定理1。K5和K3,3不是平面图。2。一个图是平面图的充分必要条件是它不含K5或K3,3的子图。3。当n≥5时，Kn一定不是平面图。∵它一定含K5。[2000年1月选择题3]设图G如右，那么G是。A)平面图B)完全图C)欧拉图D)哈密顿图[2000年7月选择题4]设G是有5个结点的完全图，则G是。A)