第十五章欧拉图与哈密顿图s.pptVIP

第十五章 欧拉图与哈密顿图 15.1 欧拉图 1736年数学家欧拉发表了第一篇图论论文，解诀了哥尼斯堡七桥问题。 定义（欧拉通路和欧拉回路） 通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路 通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路 定义（欧拉图和半欧拉图） 具有欧拉回路的图称为欧拉图 具有欧拉通路无欧拉回路的图称为半欧拉图 规定平凡图是欧拉图 （1）欧拉图。 （2）半欧拉图。 （3）不存在欧拉通路，也不存在欧拉回路。 （4）欧拉图。 （5）不存在欧拉通路，也不存在欧拉回路。 （6）不存在欧拉通路，也不存在欧拉回路。 无向欧拉图与无向半欧拉图的判断方法 定理15.1（无向欧拉图的判定）无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。 定理15.2（无向半欧拉图的判定）无向图G是半欧拉图当且仅当G是连通图，且G中恰有两个奇度顶点。 有向欧拉图与有向半欧拉图的判断方法 定理15.3 （有向欧拉图的判定）有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。 定理15.4（有向半欧拉图的判定）有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。 欧拉图的性质：欧拉图可以分解成若干个边不重的圈。 中国的“一笔画”的问题 从图某一点出发，线可以相交但不能重合将图画完的问题。 可以看出在“一笔画”的问题中，终点与始点重合的图对应着欧拉图，不重合的对应半欧拉图。 例15.2（P296） Fleury算法 （1）任取v0?V(G)，令P0=v0。 （2）设Pi=v0e1v1e2…..eivi已经行遍，则按下面方法来从E(G)-{e1,e2,….,ei}中选取ei+1： （a）ei+1与vi相关联； （b）除非无别的边可供选择，否则ei+1不应该为 G-{e1,e2,….,ei}中的桥。 （3）当（2）不能再进行时，算法停止，得到的Pn=v0e1v1e2…..envn为G中的一条欧拉回路。 例15.2（P296） 例15.2（P296） 利用欧拉图可以解决哥尼斯堡七桥问题：从某地出发，对每座跨河桥只走一次，而在遍历了七座桥之后，却又能回到原地。 思考  如下图所示，从一房间出发，问能否不重复地穿过每一道门，通过所有房间？ 15.2 哈密顿图 1859年，爱尔兰数学家威廉·哈密尔顿发明了一个旅游世界的游戏。将一个正十二面体的20个顶点分别标上世界上大城市的名字，要求玩游戏的人从某城市出发沿12面体的棱，通过每个城市恰一次，最后回到出发的那个城市。 定义（哈密顿通路和哈密顿回路） 经过图（有向图或无向图）每个顶点一次且仅一次的通路称为哈密顿通路。 经过图每个结点一次且仅一次的回路（初级回路）称为哈密顿回路。 定义（哈密顿图和半哈密顿图） 存在哈密顿回路的图称为哈密顿图。 存在哈密顿通路但不存在哈密顿回路的图称为半哈密顿图。 平凡图是哈密顿图。 （1）（2）（3）（4）为哈密顿图 （5）为半哈密顿图 （6）既不是哈密顿图，又不是半哈密顿图。 到目前为止，还没有找到判断哈密顿图简单的充分必要条件。 下面介绍哈密顿图和半哈密顿图的必要条件 定理15.6 设无向图G=V,E是哈密顿图，V1是V的任意非空子集，则有p(G-V1)≤|V1|,其中p(G-V1)为G-V1的连通分支数。 推论 设无向图G=V,E是半哈密顿图，V1是V的任意非空子集，则有p(G-V1)≤|V1|+1。 注意： （1）定理15.6和推论是必要条件。 （2）两定理可以证明一个图不是哈密尔顿图或半哈密顿图。 易见p(G-{v1,v2})=3，|{v1,v2}|=2 p(G-{v1,v2})?|{v1,v2}| 不满足定理15.6，所以图G不是哈密顿图。 彼得松图满足定理15.6，但不是哈密顿图。 下面给出哈密顿图和半哈密顿图的充分条件 定理15.7 设G=V，E为n阶无向简单图，如G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)?n-1，则G中存在哈密顿通路，即G为半哈密顿图。 推论 设G=V，E为n（n?3）阶无向简单图，如G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)?n，则G是哈密