《《欧拉哈密顿通路》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《欧拉哈密顿通路》PPT课件.ppt（39页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 图图 论论 Graphs图/Graph： 可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。6.1 图的概述/Introduction of Graph6.2 图的术语/Graph Terminology6.3 图的表示与同构/ Representing Graph and Graph Isomorphism6.4 连通性/Connectivity6.5 欧拉通路与哈密顿通路 / Euler and Hamilton Paths6.6 最短通路问题/Shortest Path Problem6.7 平面图/Planar Graphs6.8 图的着色/Gr
2、aph Coloring学习内容6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathKonigsberg(哥尼斯堡哥尼斯堡)七桥问题七桥问题问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。 Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向多重图，问题化为图论中简单回路的问题：6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path定义定义1欧拉通路（回路）：欧拉通路（回路）： G=(V,E)，称包含，称包含E中所有边的简单通路为中所
3、有边的简单通路为欧拉通路欧拉通路/Euler Path/E通路通路。 包含包含E中所有边的简单回路为中所有边的简单回路为欧拉回路欧拉回路/Euler Circuit/E回路回路。注：包含欧拉回路的图称为欧拉图/E图6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path例1 图中是否存在欧拉回路？若无，存在欧拉通路？6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathG1存在欧拉回路 eabedceG2不存在欧拉回路和欧拉通路 G3存在欧拉通路 adcabdeb例2 图中是否存在欧拉回路？若无，存在欧拉通路？6
4、.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathH1不存在欧拉回路和欧拉通路H2存在欧拉回路 agcbedfaH3不存在欧拉回路,存在欧拉通路 cabcdb定理定理1（欧拉定理欧拉定理）：）： 没没有有度度为为0的的孤孤立立顶顶点点的的无无向向图图存存在在欧欧拉拉通通路路的的充要条件是：充要条件是： (1)图是连通的；图是连通的； (2)图中奇度顶点个数是图中奇度顶点个数是0个或个或2个。个。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path证明： 必要性： 若存在欧拉通路，且没有0度顶点，则每个顶点都
5、有边关联，而边又全在欧拉通路上，故所有顶点都连通。 除了起点，终点外，欧拉通路每经过一个顶点，使顶点的度增加2，故只有起点和终点才可能成为奇度顶点，而一个奇度顶点是不可能的，当无奇度顶点时，是欧拉回路。充分性： 若(1)，(2)成立，构造欧拉通路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path 若图G存在奇度顶点，任取一个作为起点，若不存在，则任取一个顶点作为起点。 若此图有n条边，总度为2n。每进入或离开一个顶点，让此顶点的度减1，由于除了两个（或没有）奇度顶点外，其余顶点度为偶数，只要进得去，一定出得来，直至进入另一个奇度顶点（或起点）作为
6、终点。这样构造的是简单通路，如果经过所有的边，即得到一条欧拉通路。 不然，记走过的简单通路为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重复上
7、述过程，由于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，J2) 从A出发，走一条通路P1（A,C,E,A,B,C,D,E,F,G,H,I,J）6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path3) G1=(V1, E1) V1 =A,B,C,D,E,F,G,H,I,J E1 =(A,C),(C,E),(
8、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 Path4) 在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
9、,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的孤立顶点的有向图具有欧拉通路的
10、孤立顶点的有向图具有欧拉通路的充要条件是：的充要条件是：（1）弱连通；）弱连通；（2）除了可能有）除了可能有2个顶点，一个入度比出度大个顶点，一个入度比出度大1，一个出，一个出度比入度大度比入度大1，其余顶点出度等于入度。，其余顶点出度等于入度。推论推论 不含出不含出/入度为入度为0的孤立顶点的有向图具有欧拉回路的孤立顶点的有向图具有欧拉回路的充要条件是：的充要条件是：（1）弱连通；）弱连通；（2）所有顶点出度等于入度。）所有顶点出度等于入度。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path欧拉通路欧拉通路/回路的应用与推广：回路的应用与推广：1
11、）一笔画问题2）如果奇度顶点个数为2K个，此问题是K笔画问题3）中国邮递员问题4）电路布线、网络组播和分子生物学 6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path欧拉通路欧拉通路/回路的应用与推广：回路的应用与推广：1）一笔画问题2）如果奇度顶点个数为2K个，此问题是K笔画问题3）中国邮递员问题4）电路布线、网络组播和分子生物学 6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton PathHamilton(哈密顿哈密顿)通路问题：通路问题： 1857年发明的一种游戏。在一个实心的正十二面体，20个顶点标上世界著
12、名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。这就是“绕行世界”问题。即找一条经过所有顶点（城市）的基本回路。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
13、 Path图A 每个顶点都是奇度的，不存在E通路，但有H通路。 图B存在E通路，不存在H通路。6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path6.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分为
14、二个不连通的分图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
15、)，(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
16、的度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，仍继续扩充基本
17、通路内的顶点，直至达到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 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Eule
18、r and Hamilton Path定理定理4 狄拉克定理狄拉克定理 若若G是是带带n个个顶顶点点的的连连通通简简单单图图，n3，且且G中中每每个个顶顶点的度都至少为点的度都至少为n/2，则，则G有哈密顿回路。有哈密顿回路。 要判别一个图不存在H通路/H回路，也不是很容易的，只能对无向图给出一些必要条件：1) H通路存在必要条件： 连通 至多只能有二个顶点的度2，其余顶点的度2。bcda6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path2) H回路存在必要条件： 对V的任一非空真子集S，G-S的连通分支个数|S|。 6.5 欧拉通路与哈密顿通路欧
19、拉通路与哈密顿通路 Euler and Hamilton Path解：取S=A1, A2G-S存在3个连通分支根据H回路存在的必要条件之二，可知H回路不存在！6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path应用问题之一：应用问题之一： Knights tour应用问题之二：应用问题之二： Gray Code应用问题之三：应用问题之三： Tower of Hanoi6.5 欧拉通路与哈密顿通路欧拉通路与哈密顿通路 Euler and Hamilton Path旋转的指针的位置可以表示成数字的形式。一种方式是把圆周等分成2n段弧并且用长度为n的位串给
20、每段弧赋值。格雷码格雷码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,vjV，且ij，若vi与vj有共同语言，就在vi,vj之间连无向边(vi,vj)，由此组成边集合E，则G为8阶无向简单图，viV，d(vi)为与vi有共同语言的人数。由已知条件可知，vi,vjV且ij，均有d(vi)+d(vj)8。由定理3可知，G中存在哈密顿回路，设Cvi1vi2vi8为G中一条哈密顿回路，按这条回路的顺序安排座次即可。作作 业业 P274：3、10、17
