资源描述:
《《欧拉哈密顿通路》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)还有未经