《欧拉哈密顿通路》PPT课件.ppt

第六章 图 论 Graphs,图/Graph： 可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。,6.1 图的概述/Introduction of Graph 6.2 图的术语/Graph Terminology 6.3 图的表示与同构/ Representing Graph and Graph Isomorphism 6.4 连通性/Connectivity 6.5 欧拉通路与哈密顿通路 / Euler and Hamilton Paths 6.6 最短通路问题/Shortest Path Problem 6.7 平面图/Planar Graphs 6.8 图的着色/Graph Coloring,学习内容,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,Konigsberg(哥尼斯堡)七桥问题,问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。,Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向多重图，问题化为图论中简单回路的问题：,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,定义1欧拉通路（回路）： G=(V,E)，称包含E中所有边的简单通路为欧拉通路/Euler Path/E通路。 包含E中所有边的简单回路为欧拉回路/Euler Circuit/E回路。 注：包含欧拉回路的图称为欧拉图/E图,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,例1 图中是否存在欧拉回路？若无，存在欧拉通路？,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,G1存在欧拉回路 eabedce G2不存在欧拉回路和欧拉通路 G3存在欧拉通路 adcabdeb,例2 图中是否存在欧拉回路？若无，存在欧拉通路？,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,H1不存在欧拉回路和欧拉通路 H2存在欧拉回路 agcbedfa H3不存在欧拉回路,存在欧拉通路 cabcdb,定理1（欧拉定理）： 没有度为0的孤立顶点的无向图存在欧拉通路的充要条件是： (1)图是连通的； (2)图中奇度顶点个数是0个或2个。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,证明： 必要性： 若存在欧拉通路，且没有0度顶点，则每个顶点都有边关联，而边又全在欧拉通路上，故所有顶点都连通。 除了起点，终点外，欧拉通路每经过一个顶点，使顶点的度增加2，故只有起点和终点才可能成为奇度顶点，而一个奇度顶点是不可能的，当无奇度顶点时，是欧拉回路。,充分性： 若(1)，(2)成立，构造欧拉通路。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,若图G存在奇度顶点，任取一个作为起点，若不存在，则任取一个顶点作为起点。 若此图有n条边，总度为2n。每进入或离开一个顶点，让此顶点的度减1，由于除了两个（或没有）奇度顶点外，其余顶点度为偶数，只要进得去，一定出得来，直至进入另一个奇度顶点（或起点）作为终点。这样构造的是简单通路，如果经过所有的边，即得到一条欧拉通路。,不然，记走过的简单通路为p1，p1上顶点集V1，边集E1，G1=(V1, E1)是G的子图。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,若G2=(V2,E2)是G1的关于G的补图，E2=E-E1，但V1V2 ，否则G不连通，设CV1V2，从C出发，用上面方法作G2的简单回路p2 回到C, 这能做到。 因为作好p1后，留下顶点的度都是偶度。若p1p2经过所有边，则欧拉通路是p1走到C时，先把p2走完，最后走完p1的余下通路。 若p1p2仍未经过所有边，将p1p2视为p1重复上述过程，由于E边有限，故存在欧拉通路。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,例1：,1) 顶点的度：A(3) , B(2) , C(4) , D(2) , E(6), F(2) , G(6) , H(2) , I(4) , J(3)。其中奇度顶点A，J 2) 从A出发，走一条通路P1（A,C,E,A,B,C,D,E,F,G,H,I,J）,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,3) G1=(V1, E1) V1 =A,B,C,D,E,F,G,H,I,J E1 =(A,C),(C,E),(E,A),(A,B),(B,C),(C,D),(D,E),(E,F), (F,G),(G,H),(H,I),(I,J) 则 G2=(V2, E2) E2=(E,G),(E,J),(J,G),(G,I),(I,G) V2=E,G, I, J E(V1 V2),6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,4) 在G2中从E出发回到E的回路(E, J, G, E)，加入到P1中 P1=(A,C,E,A,B,C,D,E, J, G, E,F,G,H,I,J) 5) 还有未经过的边，重复上述过程 ，从G出发，(G,I,G)，再加入即得欧拉通路。 P1 =(A,C,E,A,B,C,D,E, J, G, E,F,G,I,G,H,I,J),6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,推论1（欧拉定理）： 没有度为0的孤立顶点的无向图存在欧拉回路的充要条件是： (1)图是连通的； (2)图中没有奇度顶点。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,定理2 有向图的欧拉定理： 不含出/入度为0的孤立顶点的有向图具有欧拉通路的充要条件是： （1）弱连通； （2）除了可能有2个顶点，一个入度比出度大1，一个出度比入度大1，其余顶点出度等于入度。 推论 不含出/入度为0的孤立顶点的有向图具有欧拉回路的充要条件是： （1）弱连通； （2）所有顶点出度等于入度。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,欧拉通路/回路的应用与推广： 1）一笔画问题 2）如果奇度顶点个数为2K个，此问题是K笔画问题 3）中国邮递员问题 4）电路布线、网络组播和分子生物学,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,欧拉通路/回路的应用与推广： 1）一笔画问题 2）如果奇度顶点个数为2K个，此问题是K笔画问题 3）中国邮递员问题 4）电路布线、网络组播和分子生物学,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,Hamilton(哈密顿)通路问题： 1857年发明的一种游戏。 在一个实心的正十二面体，20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。 这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本回路。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,定义1哈密顿通路/回路： G=(V, E)，G中经过V中所有顶点的基本通路称为哈密顿通路/Hamilton Path，简称H通路。 G=(V, E)，G中经过V中所有顶点的基本回路称为哈密顿回路/Hamilton Circuit，简称H回路。 注：存在哈密顿回路的图称为哈密顿图/H图,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,图A 每个顶点都是奇度的，不存在E通路，但有H通路。 图B存在E通路，不存在H通路。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,有哈密顿回路或通路吗？,图G1 有H回路；图G2 有H通路，无H回路； 图G3无H通路，也无H回路,定理3 设G=(V,E) 是n个顶点的简单图，如果任一对不相邻的顶点度之和n-1，则G中一定有H通路(n2)。,证明： 1） G一定连通，否则G分为二个不连通的分图G1，G2，其中G1有n1个顶点，G2有n2个顶点，G1中每个顶点度n1-1，G2中每个顶点度n2-1，从G1中取一个顶点，G2中取一个顶点，这一对顶点度之和n1-1 + n2-1n1 + n2 - 2n-2n-1，与定理的假设矛盾。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,注意:此定理条件显然不是必要条件，如n6的n边形，二个顶点度之和=4，4n-1，而n边形显然有H通路。,2）用归纳法证明G中存在H通路： 任取一条边(V1,V2)，是含2个顶点的基本通路。 如果已有p个顶点的基本通路 (V1,V2,Vp)，(pn-1) 必能构造p+1个顶点的基本通路。 a) 如果在V-V1,V2,Vp中存在与V1或Vp相邻的顶点，则基本通路自然可以扩充一个顶点。 b) 如果V1,Vp仅与V1,V2,Vp中顶点相邻，则V1,V2,Vp必可适当排列，形成回路。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,如果V1与Vp相邻，显然成了环。不然，由于V1,Vp仅与V1,V2,Vp中顶点相邻， V1,Vp的度p-1。不妨设V1的度为kp-1，分别记相邻顶点为Vi1，Vi2，Vik，它们前面的顶点（指在基本通路V1,V2,Vp中的序）为 ，Vp必与 中某顶点相邻，否则Vp的度p-1-k，V1与Vp的度之和k+p-1 k = p-1n-1，与任一对顶点度之和n-1矛盾。 不妨Vp与Vj-1相邻，V1与Vj相邻。将V1与Vj连起来，Vp与Vj-1连起来，并将Vj-1到Vj的边去掉，就形成一个环。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,又由G的连通性，总可在V-V1,V2,Vp中找到一个点Vx，与V1,V2,Vp中某一顶点相邻，不妨与Vk相邻，VkV1，VkVp，连上Vx与Vk的边，去掉Vk-1到Vk的边，可以从Vk-1为起点，一直走到Vk，再到Vx，这是一条p+1个顶点的基本通路。 如果p+1n，仍继续扩充基本通路内的顶点，直至达到n。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,推论 奥尔定理： G=(V,E)是n3的简单图，若任何一对不相邻顶点的度之和n，则G必有哈密顿回路。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,由于推论条件也必满足定理3条件，存在H通路，可类似于定理1的方法找到一条H回路。,定理5 无向/有向完全图一定存在H通路。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,定理4 狄拉克定理 若G是带n个顶点的连通简单图，n3，且G中每个顶点的度都至少为n/2，则G有哈密顿回路。,要判别一个图不存在H通路/H回路，也不是很容易的，只能对无向图给出一些必要条件： 1) H通路存在必要条件： 连通 至多只能有二个顶点的度2，其余顶点的度2。,6.5 欧拉通路与哈密顿通路 Euler and Hamilton Path,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,应用问题之一： Knights 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人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和