计算机数学基础上 第编 图论优秀PPT.ppt

《计算机数学基础上 第编 图论优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机数学基础上 第编 图论优秀PPT.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机数学基础上 第编 图论现在学习的是第1页，共26页本章主要内容本章主要内容：1.欧拉图欧拉图2.哈密顿图哈密顿图3.平面图平面图4.树树重点：欧拉图、哈密顿图、平面图、欧拉公重点：欧拉图、哈密顿图、平面图、欧拉公式、生成树式、生成树难点：哈密顿图、平面图、最小生成树难点：哈密顿图、平面图、最小生成树现在学习的是第2页，共26页6.1 欧拉图和中国邮路问题 一、欧拉图的定义 在无向图中，从某一个结点出发，经过每边一次并且经过图中所有的结点(不一定一次)到达终点。如果终点与起点重合，则称为存在欧拉回路，如果终点与起点不重合，则称为存在欧拉通路。存在欧拉回路的图称为欧拉图。直观地说，一个无向图

2、如果可以从一点出发，笔不离纸地一笔画出，就存在欧拉回路或欧拉通路，如果还能回到起点，就是欧拉图。现在学习的是第3页，共26页二、欧拉图的判定 1。无向连通图是欧拉图的充分必要条件是图中不含有奇数度的结点。2001年1月选择题4。无向图G是欧拉图，当且仅当 。A)G中所有的结点的度数全为偶数 B)G中所有的结点的度数全为奇数 C)G连通且所有的结点的度数全为偶数 D)G连通且所有的结点的度数全为偶数 C现在学习的是第4页，共26页2000年1月化简解答题14(1)。设G是无向图如右(彼得森图)，说明G不是欧拉图。解：因为无向图G中所有的结点的度数全为奇数，所以G不是欧拉图。2。无向连通图存在欧拉

3、通路的充分必要条件是图中只有两个奇数度的结点。3。当n为奇数时，完全无向图Kn是欧拉图。例如，K3、K5等。4。当n为偶数时，完全无向图Kn不是欧拉图，也不存在欧拉通路。现在学习的是第5页，共26页2001年7月化简解答题13。试问n为何值时，无向完全图Kn存在一条欧拉回路？解：因为无向连通图存在欧拉回路的充分必要条件是图中不含有奇数度结点。所以，无向完全图Kn的结点度数应为偶数，即n-1为偶数，则n为奇数。三、中国邮路问题 邮递员从邮局出发，走遍辖区内所有的街道至少一次(可以重复)，最后回到邮局。要走怎样的路线全程才最短，这一问题就称为中国邮路问题。现在学习的是第6页，共26页 中国邮路问题

4、可以转化成图的问题来解。以街道为边，街道的长度为边的权，以邮局和街道的交叉点为结点，得到带权图G。如G中不含有奇数度结点，则G是欧拉图。以邮局为起点的欧拉回路就是问题的解。如G中含有奇数度结点，则可在这些奇数度结点间添加新的边，使原有的某些边成为双边，并且使添加的边的权数之和最小。这样一来G的结点就都成为偶数度的结点，G就成了欧拉图，从而求出问题的解。因此，求中国邮路问题的解就是在G中添加一些边，使图中所有的结点的度数都变成偶数。求添加的边的权数之和最小的添法。现在学习的是第7页，共26页6.2 哈密顿图和货郎担问题一、哈密顿图的定义 从图中的某一结点出发，如果存在一条只经过每个结点一次(不必

5、经过所有的边)的通路，则此通路称为哈密顿通路。如果还能回到起点，则称为哈密顿回路。存在哈密顿回路的图称为哈密顿图。哈密顿图不仅可以是无向图，也可以是有向图。显然，非连通图一定不是哈密顿图。哈密顿通路与欧拉通路的区别是：欧拉通路是经过每一边一次而且仅一次，但可以经过某些结点多次的通路，哈密顿通路是经过每一结点一次而且仅一次，但可以不经过某些边的通路。现在学习的是第8页，共26页二、哈密顿图的判定 1。在哈密顿图G中删除结点集V1后，GV1的连通分支数 。不满足这一条件的图一定不是哈密顿图。2。如果无向简单图G中任何一对结点的度数之和都大于等于结点数，则G中存在一条哈密顿回路。2001年1月填空题

6、9 设图G=是简单图，若图中每对结点的度数之和 ，则G一定是哈密顿图。3。把有n个结点的有向图D中边的方向去掉，如果其中包含子图Kn，则D中存在哈密顿通路，当n3时，则D中存在哈密顿回路。现在学习的是第9页，共26页6.3 平面图与图的着色一、平面图的定义 如果把无向图G的所有结点和所有的边(可任意弯曲)画在平面上，使任何两条边都没有交叉点，则称G为平面图。否则，称为非平面图。例如K4 可画为 是平面图。现在学习的是第10页，共26页二、平面图的判定 1。如果把图G中的某些边弯曲可以使任何两边都不交叉，则G是平面图。否则是非平面图。例如，课本 P.229 图6-55 (a)、(b)、(c)，可

7、画为现在学习的是第11页，共26页 2。如果图G与图G同构，而G是平面图，则G是平面图。也就是说，把图G中的各结点重新排列，把原来连接各结点的边，关联到这些结点重新排列后的位置上，如果可得到平面图。则原图是平面图。课本 P.338 的解答就是这样的。例如，图6-55 (a)现在学习的是第12页，共26页三、面的次数 1。在连通平面图中，由图的边所包围的，并且其内部不包含图的结点和边的区域称为图的一个面。面分为有限面和无限面。例如，r1 有两个面r1、r2，其中r2是无限面。2。包围一个面的各边的回路称为面的边界，面的边界的回路的长度称为面的次数，记作deg(r)。注意：环内部的面的次数为1，面

8、内部的边在计算次数是要算2遍。现在学习的是第13页，共26页例如，r1 r1的次数deg(r1)=6。四、次数定理 在平面图G=中，所有面的次数之和等于边数的2倍。即 。2001年7月填空题10 在平面图G=中，则 ，其中 是G的面。现在学习的是第14页，共26页五、欧拉公式1。欧拉公式 在连通平面图G=中，有v个结点，e条边，r个面，则 ，该公式称为欧拉公式。欧拉公式的应用非常广泛，应当记牢。推论 在简单连通平面图中，若v3，则证明：现在学习的是第15页，共26页2001年7月选择题5 设G是连通平面图，有v个结点，e条边，r个面，则 r=。A)e-v+2 B)v+e-2 C)e-v-2 D

9、)e+v+22000年7月填空题8 设G是连通平面图，v,e,r 分别表示G的结点数、边数和面数，则 v,e,r 满足的关系式是 。2000年1月证明题19 设G是平面图，并且G的所有面的次数均为3，证明 ,其中e是G的边数，v是G的结点数。证明：A现在学习的是第16页，共26页六、库拉托夫斯基定理 1。K5和K3,3不是平面图。2。一个图是平面图的充分必要条件是它不含K5或K3,3的子图。3。当n5时，Kn一定不是平面图。它一定含K5。现在学习的是第17页，共26页2000年1月选择题3 设图G如右，那么G是 。A)平面图 B)完全图 C)欧拉图 D)哈密顿图2000年7月选择题4 设G是有

10、5个结点的完全图，则G是 。A)无哈密顿通路 B)无欧拉回路 C)平面图 D)欧拉图DD现在学习的是第18页，共26页6.4 树一、树的定义 1。连通且无回路的无向图称为树，用T表示。T中的1度结点称为树叶，大于1度的结点称为分支点。孤点称为平凡树，仅由树组成的无向图称为森林。2。树的性质 连通且无回路，|E|=|V|-1，增加任意一条边必出现回路，删除任意一条边必不连通，每对结点间仅有一条通路。3。任何非平凡树中至少有2片树叶。现在学习的是第19页，共26页2000年7月化简解答题13 在一棵有2个2度结点，4个3度结点，其余为树叶的无向图中应该有几片树叶？画出两棵不同构的满足条件的无向树T

11、1、T2。解：设有k片树叶，则v=k+6，解得 ，故有6片树叶。现在学习的是第20页，共26页二、生成树 1。生成树 若图G的生成子图是一棵树，则称此树是G的生成树。2。树的补 图G中不属于生成树T的边的集合称为树T的补。3。生成树的求法 一般可用破圈法做，即把图G中的回路去掉一条边，使它不再是回路。如此做下去，直到恰好把所有的回路都破坏掉，就得到了生成树。用破圈法一共要去掉 条边。现在学习的是第21页，共26页2000年1月填空题8 设G=是有p个结点，s条边的连通图，则从G中删去 条边，才能确定G的一棵生成树。解：设要删去k条边，2000年7月选择题3 设G是有6个结点的完全图，从G中删去

12、 条边则能得到树。A)6 B)9 C)10 D)15 解：G是有6个结点的完全图，G中共有65/2=15条边，要使G成为树，G中只应留下5条边，故应删去10条边，选C。C现在学习的是第22页，共26页4。最小生成树 在带权图G中所生成的总权数最小的生成树称为最小生成树。5。最小生成树的求法 选取权数最大的边所在的回路，去掉其中权数最大的边，如此做下去，直到求出生成树为止。这样求出的生成树一定是最小生成树。还有一种方法称为克鲁斯特尔算法。先去掉所有的边，然后从权数最小的边的开始，从小到大逐步选取，如果所选取的边和已选取的边构成了回路，则不选取这条边重新选取，直到连接完所有的结点。这样求出的树就是

13、最小生成树。现在学习的是第23页，共26页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=。现在学习的是第24页，共26页2001年1月计算题17 求图G的一棵最小生成树。解：现在学习的是第25页，共26页解法二：用克鲁斯特尔算法做，先去掉所有的边。从最小边(d,e)开始选取，再选取(d,a)，再选取(e,a)和(b,c)，但(e,a)构成回路，所以应去掉，再选取(c,a)，这时已连接了所有的结点，最小生成树求出。T=。现在学习的是第26页，共26页