6-5欧拉-哈密顿通路.ppt

2) H回路存在必要条件： 对V的任一非空真子集S，G-S的连通分支个数≤|S|。 6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path 解：取S={A1, A2} G-S存在3个连通分支 根据H回路存在的必要条件之二，可知H回路不存在！ 6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path 应用问题之一： Knight’s tour 应用问题之二： Gray Code 应用问题之三： Tower of Hanoi 6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path 旋转的指针的位置可以表示成数字的形式。 一种方式是把圆周等分成2n段弧并且用长度为n的位串给每段弧赋值。 格雷码Gray Code 在指针上用n个接触点来确定指针位置，每个接触点用来读出位置的数字表示中的一位 格雷码Gray Code 当指针靠近两段弧的边界时，读出指针的位置可能出错 格雷码Gray Code 3位都错 最多1位错 可用n立方体Qn来为问题建模 弧的满足要求的标记就是求Qn的一个哈密顿回路。 格雷码Gray Code Q3 格雷码是上世纪40年代弗兰克·格雷为把数字信号传送过程中错误的影响降到最低而发明的。 思考题 在某次国际会议的预备会议中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。 思考题 解：设8个人分别为v1,v2,…,v8，作无向简单图G=(V,E)，其中V={v1,v2,…,v8}，?vi,vj∈V，且i≠j，若vi与vj有共同语言，就在vi,vj之间连无向边(vi,vj)，由此组成边集合E，则G为8阶无向简单图，?vi∈V，d(vi)为与vi有共同语言的人数。 由已知条件可知，?vi,vj∈V且i≠j，均有d(vi)+d(vj)≥8。 由定理3可知，G中存在哈密顿回路，设C＝vi1vi2…vi8为G中一条哈密顿回路，按这条回路的顺序安排座次即可。 作 业 P274：3、10、17 在学习欧拉通路之前，思考一个问题：格尼斯堡七桥问题 现名加里宁格勒，俄罗斯，被普雷格尔河分成4个部分，18世纪分用七座桥连接起来。人们在散步时就思考可否从镇的某个位置除法不重复地经过所有桥并且返回出发点呢？ * 即在这个多重图里是否存在着包含每一条边的简单回路？ 进一步的在任意一个多重图里是否存在？ * 实际就是判断欧拉通路/回路的问题，给出定义1 * 实际就是判断欧拉通路/回路的问题，给出定义1 * 问题：是否存在一个简便的方法来判断一个图是否存在欧拉回路和通路呢？ * 给出欧拉定理 * 当无奇度顶点时，该欧拉通路时欧拉回路。 * 图1因为每个顶点都为偶度顶点，故该图存在欧拉回路，左图为欧拉图/E图 哥尼斯堡七桥问题，由于四个顶点都是奇度的，不可能有欧拉通路，也就更不可能有欧拉回路。 * 另外对于有向图，也同样有可能存在欧拉通路/回路 欧拉通路，从出度大的顶点出发到达入度大的那个顶点的简单通路 * 一笔画问题(笔不离开纸,不重复地画遍纸上图形的所有的边),实质上是一个求欧拉通路问题 K5 穆罕默德短弯刀 * 8个顶点均为3度，至少要4笔画完。 许多应用需要求一个通路或回路，恰好经过一个街区的每一条街道、一个交通网里的每一条道路、一个高压输电网的每一个连接、一个通信网络的每个链接等，这都可以使用求解适当图模型的欧拉通路/回路的方法解决。 具体一个典型的例子就是：中国数学家管梅谷先生（山东师范大学数学系教授）在1962年首次提出的中国邮递员问题：一名邮递员带着要分发的邮件从邮局出发，经过要分发的每个街道，送完邮件后又返回邮局。如果他必须至少一次走过他管辖范围内的每一条街道，如何选择投递路线，使邮递员走尽可能少的路程。 用图论的术语：求一个加权连通图的权值之和最小的欧拉回路。 * 为了方便查找和理解，构造一个与该正十二面体同构的图形 * 这样的经过图的每个顶点恰好一次的通路或回路，我们称之为哈密顿通路/回路 * 同样的问题 一个图是否有哈密顿回路或通路，是否有简单的方法判定呢?感觉可能有，实际上现在还没人找出一个图有H通路或H回路的充要方法，只找到了充分条件，即满足一定有H~，但有，并不一定满足这个条件 * 有向完全图一定存在H通路 * 有向完全图一定存在H通路 * 许多实际应用中需要求一条通路或回路，它要恰好一次的访问每一个城市里的每个路口、一个设备网格里的每个管道交汇处或者一个通信网络里的每个节点。等等，这些问题都是求解H通路或H回路的问题。 比较典型的应用有爵士旅行问题、