《欧拉图于哈密顿图》PPT课件

《《欧拉图于哈密顿图》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Home}目录§15.1欧拉图§15.2哈密顿图第十五章欧拉图与哈密顿图一、历史背景－－哥尼斯堡七桥问题§15.1欧拉图二、定义欧拉通路(欧拉迹)——通过图中每条边一次且仅一次，并且过每一顶点的通路。欧拉回路(欧拉闭迹)——通过图中每条边一次且仅一次，并且过每一顶点的回路。欧拉图——存在欧拉回路的图。三、无向图是否具有欧拉通路或回路的判定有欧拉通路连通，中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有欧拉回路(为欧拉图)连通，中均为偶度顶点。例1、以下图形能否一笔画成？例1、以下图形能否一笔画成？四、有向图是否具有欧拉通路或回路的判定有欧拉通路连通，除两个顶点外，其余顶点的入度均等

2、于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。有欧拉回路(为欧拉图)连通，中所有顶点的入度等于出度。例3、判断以下有向图是否欧拉图。一、问题的提出1859年，英国数学家哈密尔顿，周游世界游戏。§15.2哈密尔顿图二、哈密尔顿图哈密尔顿通路——通过图中每个顶点一次且仅一次的通路。哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。哈密尔顿图——存在哈密尔顿回路的图。例1、判断下图是否具有哈密尔顿回路，通路。解：存在哈密尔顿通路，但不存在哈密尔顿回路。例1、判断下图是否具有哈密尔顿回路，通路。解：是哈密尔顿图，存在哈密尔顿回路和通路。例1、判断下图是否具有

3、哈密尔顿回路，通路。解：不存在哈密尔顿回路，也不存在哈密尔顿通路。例2、画一个无向图，使它(1)具有欧拉回路和哈密尔顿回路，解：(2)具有欧拉回路而没有哈密尔顿回路，解：例2、画一个无向图，使它(3)具有哈密尔顿回路而没有欧拉回路，(4)既没有欧拉回路，也没有哈密尔顿回路。解：解：作业习题十五2、11、14、15、20