⑨8.1.1歌尼斯堡七桥问题 欧拉图 经过图中每条边一次且仅一次的路径称为欧拉路径。 如果欧拉路径的起点和终点为图中的同一个顶点,这时 的欧拉路径称为欧拉回路。 包含有欧拉回路的图称为欧拉图。 计算机导论(2014)
计算机导论(2014) 欧拉图 经过图中每条边一次且仅一次的路径称为欧拉路径。 如果欧拉路径的起点和终点为图中的同一个顶点，这时 的欧拉路径称为欧拉回路。 包含有欧拉回路的图称为欧拉图。 8.1.1 歌尼斯堡七桥问题
⑨8.1.1歌尼斯堡七桥问题 欧拉的研究工作奠定了图论的基础 涉及到的后续课程 离散数学 数据结构 →应用领域 ↓计算机网络性能分析 交通运输网络调度 ↓地下管网配置 社会网络分析 航空网络 计算机导论(2014)
计算机导论(2014) 欧拉的研究工作奠定了图论的基础 涉及到的后续课程 离散数学 数据结构 应用领域 计算机网络性能分析 交通运输网络调度 地下管网配置 社会网络分析 8.1.1 歌尼斯堡七桥问题 航空网络
⑨8.1.2哈密顿回路问题 问题描述(周游世界游戏) 找一条从某个城市出发,经过每个城市恰好一次, 最后回到出发地的路径。 16 l1121 计算机导论(2014)
计算机导论(2014) 8.1.2 哈密顿回路问题 问题描述（周游世界游戏） 找一条从某个城市出发，经过每个城市恰好一次， 最后回到出发地的路径
⑨8.1.2哈密顿回路问题 哈密顿回路与欧拉回路的区别 哈密顿回路是访问图的每个顶点一次,而欧拉回路 是访问图的每条边一次 对于一个图是否存在欧拉回路,已给出充要条件; 而对于一个图是否存在哈密顿回路,至今仍未找到 充要条件。 计算机导论(2014)
计算机导论(2014) 哈密顿回路与欧拉回路的区别 哈密顿回路是访问图的每个顶点一次，而欧拉回路 是访问图的每条边一次。 对于一个图是否存在欧拉回路，已给出充要条件； 而对于一个图是否存在哈密顿回路，至今仍未找到 充要条件。 8.1.2 哈密顿回路问题
8.1.3中国邮路问题 问题描述 ↓一个邮递员应如何选择一条路线,使他能够从邮局出发 走遍他负责送信的所有街道,最后回到邮局,并且所走 的路程最短。 归结为图论问题:给定一个连通无向图,求该图的一条 经过每条边至少一次的最短回路。 对于欧拉图,找到一条欧拉回路即可。 对于非欧拉图,才是中国邮路问题的 研究重点。 计算机导论(2014)
计算机导论(2014) 问题描述 一个邮递员应如何选择一条路线，使他能够从邮局出发， 走遍他负责送信的所有街道，最后回到邮局，并且所走 的路程最短。 归结为图论问题：给定一个连通无向图，求该图的一条 经过每条边至少一次的最短回路。 对于欧拉图，找到一条欧拉回路即可。 对于非欧拉图，才是中国邮路问题的 研究重点。 8.1.3 中国邮路问题