离散数学-第十五章的PPT课件

.,1,15.1欧拉图,历史背景：哥尼斯堡七桥问题与欧拉图,18世纪中叶在欧洲普鲁士的哥尼斯堡城内有一条贯穿全市的普雷格尔河，河中有两个小岛，由7座桥相连接。当时人们热衷于一个难题：一个人怎么不重复走完七座桥，最后回到出发地点？这就是所谓的哥尼斯堡七桥问题。很长时间没有人能解决这个难题。,.,2,15.1欧拉图,历史背景：哥尼斯堡七桥问题与欧拉图,1763年，瑞士数学家欧拉发表论文，他用四个点分别表示两个小岛和两岸，用连接两点的线段表示桥。于是，哥尼斯堡七桥问题就是要求在这个图中走一条欧拉回路（即经过图中每条边一次且仅一次行遍所有顶点的回路）。,.,3,15.1欧拉图,定义15.1(1)欧拉通路经过图中每条边一次且仅一次行遍所有顶点的通路.(2)欧拉回路经过图中每条边一次且仅一次行遍所有顶点的回路.(3)欧拉图具有欧拉回路的图.(4)半欧拉图具有欧拉通路而无欧拉回路的图.几点说明：规定平凡图为欧拉图.欧拉通路是生成的简单通路，欧拉回路是生成的简单回路.环不影响图的欧拉性.,.,4,上图中，(1),(4)为欧拉图，(2)为半欧拉图，(3),(5),(6)既不是欧拉图，也不是半欧拉图.,欧拉图判断实例,.,5,要求掌握无向欧拉图的判定,定理15.1无向图G是欧拉图当且仅当G连通且无奇度顶点.,在以上三个无向图（三个图都是连通图）中，只有图（1）中没有奇度顶点，因此图（1）是欧拉图。而图（2）和图（3）中都存在奇度顶点，因而它们都不是欧拉图。,.,6,半欧拉图的判别法,定理15.2无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点.,在以上两个无向图（两个图都是连通图）中，只有（2）中有两个奇度顶点，因此（2）是半欧拉图。而（3）中有4个奇度顶点，因而（3）不是半欧拉图。,.,7,有向欧拉图的判别法,定理15.3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度.定理15.4有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度.定理15.5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的初级回路（圈）之并.,.,8,求欧拉回路的算法Fleury算法,算法：(1)任取v0V(G)，令P0=v0，i=0.(2)设Pi=v0e1v1e2eivi已经行遍如果E(G)e1,e2,ei中没有与vi关联的边，则计算停止；否则按下述条件从E(G)e1,e2,ei中选取一条边ei+1：(a)ei+1与vi相关联；(b)除非无别的边可供选择，否则ei+1不应该为Gi=Ge1,e2,ei中的桥.设ei+1=(vi，vi+1)，把ei+1vi+1加入Pi得到Pi+1.(3)令i=i+1，返回(2).可以证明算法停止时所得简单回路Pm=v0e1v1e2emvm(vm=v0)为G中的一条欧拉回路.能够一笔画出的图欧拉图。要求掌握使用定理15.1，要会判断一个图是否为欧拉图。要求理解Fleury算法和应用它一笔画出欧拉图。,.,9,15.2哈密顿图,历史背景：哈密顿周游世界问题与哈密顿图,(1)(2),1859年，爱尔兰数学家哈密顿提出一个周游世界问题：有20个城市，城市之间的交通路线如（2）所示。问能否从某个城市出发沿交通路线经过每个城市一次并且仅一次，最后回到出发点？用现在的语言，就是问这个图中是否有哈密顿回路？哈密顿自己做了肯定的回答。哈密顿回路和哈密顿图即由此得名。,.,10,15.2哈密顿图,历史背景：哈密顿周游世界问题与哈密顿图,(1)(2),.,11,15.2哈密顿图,定义15.2(1)哈密顿通路经过图中所有顶点一次仅一次的通路.(2)哈密顿回路经过图中所有顶点一次仅一次的回路.(3)哈密顿图具有哈密顿回路的图.(4)半哈密顿图具有哈密顿通路且无哈密顿回路的图.几点说明：平凡图是哈密顿图.哈密顿通路是初级通路，哈密顿回路是初级回路.环与平行边不影响哈密顿性.,.,12,上图中，(1),(2),(3)三个无向图都有哈密顿回路，都是哈密顿图。在有向图中，(4)有哈密顿回路，是哈密顿图。(5)只有哈密顿通路，没有哈密顿回路，是半哈密顿图，而(6)中既无哈密顿回路，也没有哈密顿通路，因而不是哈密顿图，也不是半哈密顿图.,要求掌握哈密顿图的判定,.,13,无向哈密顿图的一个必要条件,定理15.6设无向图G=是哈密顿图，对于任意V1V且V1，均有p(GV1)|V1|,推论设无向图G=是半哈密顿图，对于任意的V1V且V1均有p(GV1)|V1|+1,定理15.6中的条件是哈密顿图的必要条件，但不是充分条件。常利用定理15.6判断某些图不是哈密顿图.,.,14,哈密顿图和半哈密顿图的几个充分条件,定理15.7设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有d(vi)+d(vj)n1(15.1)则G中存在哈密顿通路.,推论设G为n(n3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)n(15.2)则G中存在哈密顿回路，从而G为哈密顿图.,定理15.7是半哈密顿图的充分条件，但不是必要条件.长度为n1（n5）的初级通路构成的图不满足(15.1)的条件，但它显然是半哈密顿图.,定理15.7的推论同样不是哈密顿图的必要条件，G为长为n（n4）的初级回路，不满足(15.2)条件，但它当然是哈密顿图.由定理15.7的推论可知，Kn（n3）均为哈密顿图.,.,15,哈密顿图和半哈密顿图的几个充分条件,定理15.8设u,v为n阶无向简单图G中两个不相邻的顶点，且d(u)+d(v)n，则G为哈密顿图当且仅当G(u,v)为哈密顿图（(u,v)是加的新边）.,定理15.9n（n2）阶竞赛图中都有哈密顿通路若D为n（n2）阶竞赛图，则D中具有哈密顿通路。,.,16,判断某图是否为哈密顿图的方法,判断某图是否为哈密顿图至今还是一个难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.观察出哈密顿回路.例3下图(周游世界问题)是哈密顿图易知abcdefghijklmnopqrsta为图中的一条哈密顿回路.注意，此图不满足定理15.7推论的条件.,.,17,2满足定理15.7推论的条件（15.2）.例4完全图Kn(n3)中任何两个顶点u,v，均有d(u)+d(v)=2(n1)n（n3），所以Kn为哈密顿图.3破坏定理15.6的条件的图不是哈密顿图.,判断某图是否为哈密顿图的方法,.,18,设GG，称为G的权，并记作W(G)，即,定义15.3给定图G=，(G为无向图或有向图)，设W:ER(R为实数集)，对G中的每一条边e=(vi,vj)(G为有向图时，e=)，设W(e)=wij，称实数wij为边e上的权，并将wij标注在边e上，称G为带权图，记作G=.当e=(vi,vj)()，把W(e)记作W(vi,vj).,15.3最短路问题与货郎担问题,设P是G中的一条通路，P中所有边的权之和称为P的长度，记作W(P)，即。类似可定义回路C的长度W(C)。,.,19,最短路问题,设带权图G=（无向图或有向图），其中每一条边e的权W(e)为非负实数。u,vV，当u和v连通时（即u可达v），称从u到v长度最短的路径为从u到v的最短路径，称其长度为从u到v的距离，记作d(u,v)。约定：d(u,u)=0；当u和v不连通时（即u不可达v），d(u,v)=+。,.,20,最短路问题,最短路问题：给定带权图G=及顶点u和v，其中每一条边e的权W(e)为非负实数，求从u到v的最短路径。如果uvi1vi2vikv是从u到v的最短路径，则对每一个l（1lk），uvi1vi2vil是从u到vil的最短路径。根据该性质，E.W.Dijkstra于1959年给出下述最短路径算法。最短路径算法给出从给定的起点s到每一点的最短路径。在计算过程中，赋予每一个顶点v一个标号l(v)=(l1(v),l2(v)。标号分为永久标号和临时标号：在v的永久标号l(v)中，l1(v)表示s到v的最短路径上v的前一个顶点，l2(v)表示从s到v的距离（即从s到v的最短路径的长度）。当l(v)是临时标号时，l1(v)表示当前从s经过永久标号的顶点到v的长度最短的路径上v的前一个顶点；l2(v)表示当前从s经过永久标号的顶点到v的长度最短的路径的长度。,.,21,Dijkstra标号法,输入：带权图G=和sV，其中|V|=n，eE，W(e)0输出：s到G中每一点的最短路径及距离1.令l(s)=(s,0)，l(v)=(s,+)(vVs)，i=1，l(s)是永久标号，其余标号均为临时标号，u=s（l(u):永久标号）2.for与u关联的临时标号的顶点v（l(v):临时标号）3.ifl2(u)+W(u,v)l2(v)l(v)=(u,l2(u)+W(u,v)4.计算l2(t)=minl2(v)|vV且有临时标号，把l(t)改为永久标号5.ifi|V1|=6,练习2,方法二.G为二部图，互补顶点子集V1=a,c