三联ppt模板 1.pptVIP

华北电力大学 华北电力大学 汉密尔顿图 判断是否是哈密顿图的可行方法 (1)观察出一条哈密顿回路 (2) 满足充分条件。 (3) 不满足必要条件。 (4) 标注法。 汉密尔顿图 考虑在七天内安排七门课程的考试，使得同一位教师所任的两门课程考试不排在接连的两天中，试证如果没有教师担任多于四门课程，则符合上述要求的考试安排总是可能的。 设G是含有7个结点的简单图，每个结点对应一门 课程考试；结点间的连线表示两个结点表示的课程由 不同的教师担任。由于每个教师担任不多于四门课 程，则图G中每个结点的度至少为3，因此任意两结点 度之和大于等于6，故G中存在哈密顿路，它对应一个 7门课程的考试安排。 汉密尔顿图 汉密尔顿图 货郎担/旅行推销员(TSP)问题： 旅行商问题(Travling Salesman Problem)： 给定n个城市之间的所有距离， 求推销员走遍所有城市的最短路线。 又名货郎担问题，巡回售货员问题，TSP TSP： 给定带权完全图G=V,E,W，求最短汉密尔顿回路。 汉密尔顿图 在一个赋权的完全图中，找出一个具有最小权的汉密尔顿回路，也即回路边的权之和最小对该赋权图上的边，满足三角不等式（距离不等式） W(a,b) ? W(a,c) + W(c,b) 汉密尔顿图 模型 构造无向带权图G， VG中的元素对应于每个城市， EG中每个元素对应于城市之间的道路，道路长度用相应边的权表示。 则问题的解对应于G中包含所有边的权最小的哈密尔顿回路。 G是带权完全图，总共有n!/2条哈密尔顿回路。因此，问题是如何从这n!/2条中找出最短的一条 eg：含20个顶点的完全图中不同的哈密尔顿回路有约6000万亿条-(1.21645?1017)/2，若机械地检查，每秒处理10万条，需2万年 汉密尔顿图 近似算法 1)由任一点v0开始，找一条与之相关联的权最小的边(V0 ,V1 )，形成初始回路v0 v1 2)设v0 v1 ??? vi 已选定，从V— {v0 v1 ???vi}中找一点 vi+1 与 vi 距离最近 3)重复2)直到所有节点都在通路中 4)连接始点与终点 不一定是最佳解 平面图 平面图的概念 定义1 如果图G 能画在曲面S 上，使得任意两边互不交叉，则称G 可嵌入曲面S。若图G 可嵌入平面，则称G 是可平面图或平面图，画出的无交叉边的图形称为图G 的平面嵌入。 平面图 定义2 设图G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg(R)。 平面图 定理1 若图 G 是平面图，则G 的任何子图都是平面图。 定理2 若图 G 是非平面图，则G 的任何母图都是非平面图。 定理3 若图 G 是平面图, 则在G 中添加重边或环边后所得之图仍是平面图。 定理4 平面图G 中所有面的次数之和等于G 的边数的两倍，即 其中是 是G的所有面。 * * * * * * * * * * 欧拉图、汉密尔顿图、平面图 作者： 指导老师： 课目： 欧拉图 哥尼斯堡七桥问题 欧拉图 欧拉图 无向图的欧拉通路、欧拉图（即一笔画问题） 经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路),称为欧拉通路或欧拉迹(欧拉回路或欧拉闭迹).存在欧拉回路的图,称为欧拉图。 欧拉图 定理 无向图G具有欧拉通路，当且仅当G是连通图且有零个或两个奇度顶点，若无奇度顶点，则通路为回路；若有两个奇度顶点，则它们是每条欧拉通路的端点。 推论 无向图G为欧拉图(具有欧拉回路)当且仅当G是连通的，且G中无奇度顶点。 欧拉图 1）是欧拉图； 2）不是欧拉图，但存在欧拉通路； 3）即不是欧拉图，也不存在欧拉通路。 欧拉图 总结： 1）凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。 2）凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成；画时必须把一个奇点为起点，另一个奇点终点。 3）其他情况的图都不能一笔画出。（奇点数除以二便可算出此图需几笔画成）。 中国邮递员问题： 题：邮递员从邮局出发，走过辖区内每条街道至少一次，如何选择最短路线？ 1）每街一次/至少一次 2）环游最短 欧拉图 中国邮递员问题-模型 数学模型： 1）构造无向权图G，以道路为边，路长为权 2）问题的解——G中包含所有边的回路权最小，称为最优回路(未必是简单回路)。 3）当G是欧拉图，则最优回路即欧拉回路。 4）若G不是欧拉图，则通过加边来消除G中的奇度顶点，要求使加边得到的欧拉图G中重复边的权和最小。