欧拉图于哈密顿图

,*,Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,*,Home,目录,Home,目录,Home,目录,15,.,1,欧拉图,15,.,2,哈密顿图,第十五章 欧拉图与哈密顿图,一、历史背景哥尼斯堡七桥问题,15.1 欧拉图,二、定义,欧拉通路,(,欧拉迹,),通过图中每条边一次,且仅一次，并且过每一顶点的通路。,欧拉回路,(,欧拉闭迹,),通过图中每条边一次,且仅一次，并且过每一顶点的回路。,欧拉图,存在欧拉回路的图。,三、无向图是否具有欧拉通路或回路的判定,有欧拉通路,连通，,中只有两个奇度,顶点,(,它们分别是欧拉通路的,两个端点,),。,有欧拉回路,(,为欧拉图,),连通，,中均,为偶度顶点。,例,1,、,以下图形能否一笔画成？,例,1,、,以下图形能否一笔画成？,四、有向图是否具有欧拉通路或回路的判定,有欧拉通路,连通，除两个顶点外，其,余顶点的入度均等于出度，,这两个特殊的顶点中，一个,顶点的入度比出度大,1,，另一,个顶点的入度比出度小,1,。,有欧拉回路,(,为欧拉图,),连通，,中所有,顶点的入度等于出度。,例,3,、,判断以下有向图是否欧拉图。,一、问题的提出,1859,年，英国数学家哈密尔顿，周游世界游戏。,15.,2,哈密尔顿图,二、哈密尔顿图,哈密尔顿通路,通过图中每个顶点一次且仅,一次的通路。,哈密尔顿回路,通过图中每个顶点一次且仅,一次的回路。,哈密尔顿图,存在哈密尔顿回路的图。,例,1,、,判断下图是否具有哈密尔顿回路，通路。,解：,存在哈密尔顿通路，,但不存在哈密尔顿回路。,例,1,、,判断下图是否具有哈密尔顿回路，通路。,解：,是哈密尔顿图，,存在哈密尔顿回路和通路。,例,1,、,判断下图是否具有哈密尔顿回路，通路。,解：,不存在哈密尔顿回路，,也不存在哈密尔顿通路。,例,2,、,画一个无向图，使它,(1),具有欧拉回路和哈密尔顿回路，,解：,(2),具有欧拉回路而没有哈密尔顿回路，,解：,例,2,、,画一个无向图，使它,(3),具有哈密尔顿回路而没有欧拉回路，,(4),既没有欧拉回路，也没有哈密尔顿回路。,解：,解：,作业,习题十五2、11、14、15、20,