资源描述：
《《欧拉哈密顿通路》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章图论Graphs图/Graph：可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。6.1图的概述/IntroductionofGraph6.2图的术语/GraphTerminology6.3图的表示与同构/RepresentingGraphandGraphIsomorphism6.4连通性/Connectivity6.5欧拉通路与哈密顿通路/EulerandHamiltonPaths6.6最短通路问题/ShortestPathProblem6.7平面图/PlanarGraphs6.8图
2、的着色/GraphColoring学习内容6.5欧拉通路与哈密顿通路EulerandHamiltonPathKonigsberg(哥尼斯堡)七桥问题问题：能否从河岸或小岛出发，通过每一座桥，而且仅仅通过一次回到原地。Euler(欧拉)1736年对这个问题，给出了否定的回答。将河岸和小岛作为图的顶点，七座桥为边，构成一个无向多重图，问题化为图论中简单回路的问题：6.5欧拉通路与哈密顿通路EulerandHamiltonPath[定义1]欧拉通路（回路）：G=(V,E)，称包含E中所有边的简单通路为欧拉通路/EulerP
3、ath/E通路。包含E中所有边的简单回路为欧拉回路/EulerCircuit/E回路。注：包含欧拉回路的图称为欧拉图/E图6.5欧拉通路与哈密顿通路EulerandHamiltonPath例1图中是否存在欧拉回路？若无，存在欧拉通路？6.5欧拉通路与哈密顿通路EulerandHamiltonPathG1存在欧拉回路eabedceG2不存在欧拉回路和欧拉通路G3存在欧拉通路adcabdeb例2图中是否存在欧拉回路？若无，存在欧拉通路？6.5欧拉通路与哈密顿通路EulerandHamiltonPathH1不存在欧拉回路和
4、欧拉通路H2存在欧拉回路agcbedfaH3不存在欧拉回路,存在欧拉通路cabcdb[定理1]（欧拉定理）：没有度为0的孤立顶点的无向图存在欧拉通路的充要条件是：(1)图是连通的；(2)图中奇度顶点个数是0个或2个。6.5欧拉通路与哈密顿通路EulerandHamiltonPath证明：必要性：若存在欧拉通路，且没有0度顶点，则每个顶点都有边关联，而边又全在欧拉通路上，故所有顶点都连通。除了起点，终点外，欧拉通路每经过一个顶点，使顶点的度增加2，故只有起点和终点才可能成为奇度顶点，而一个奇度顶点是不可能的，当无奇度顶
5、点时，是欧拉回路。充分性：若(1)，(2)成立，构造欧拉通路。6.5欧拉通路与哈密顿通路EulerandHamiltonPath若图G存在奇度顶点，任取一个作为起点，若不存在，则任取一个顶点作为起点。若此图有n条边，总度为2n。每进入或离开一个顶点，让此顶点的度减1，由于除了两个（或没有）奇度顶点外，其余顶点度为偶数，只要进得去，一定出得来，直至进入另一个奇度顶点（或起点）作为终点。这样构造的是简单通路，如果经过所有的边，即得到一条欧拉通路。不然，记走过的简单通路为p1，p1上顶点集V1，边集E1，G1=(V1,E1
6、)是G的子图。6.5欧拉通路与哈密顿通路EulerandHamiltonPath若G2=(V2,E2)是G1的关于G的补图，E2=E-E1，但V1∩V2≠，否则G不连通，设C∈V1∩V2，从C出发，用上面方法作G2的简单回路p2回到C,这能做到。因为作好p1后，留下顶点的度都是偶度。若p1∪p2经过所有边，则欧拉通路是p1走到C时，先把p2走完，最后走完p1的余下通路。若p1∪p2仍未经过所有边，将p1∪p2视为p1重复上述过程，由于E边有限，故存在欧拉通路。6.5欧拉通路与哈密顿通路EulerandHamilto
7、nPath例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欧拉通路与哈密顿通路EulerandHamiltonPath3)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)}则
8、G2=(V2,E2)E2={(E,G),(E,J),(J,G),(G,I),(I,G)}V2={E,G,I,J}E∈(V1∩V2)6.5欧拉通路与哈密顿通路EulerandHamiltonPath4)在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)还有未经
