第8章计算机领域的典型问题 +8.1图论问题 +8.2算法复杂性问题 +8.3计算机智能问题 +8.4并发控制问题 计算机导论(2014)
计算机导论(2014) 第8章 计算机领域的典型问题 8.1 图论问题 8.2 算法复杂性问题 8.3 计算机智能问题 8.4 并发控制问题
ERS 8.1图论问题 +歌尼斯堡七桥问题 +哈密尔顿回路问题 +中国邮路问题 B 首都经济面易学校 清华大学美术学院 大里路站 ©万达广场 兰 ⊙万达广场根示中心 气家园站 ●八王找帖 国贸地铁站 大题路地铁站 同东郊代本站 计算机导论(2014)
计算机导论(2014) 8.1 图论问题 歌尼斯堡七桥问题 哈密尔顿回路问题 中国邮路问题
8.1.1歌尼斯堡七桥问题 +问题描述 ◆一个人怎样不重复地走完七座桥，最后还能回到原出 发地点？ 北区 东区 岛区 南区 计算机导论(2014)
计算机导论(2014) 8.1.1 歌尼斯堡七桥问题 问题描述 一个人怎样不重复地走完七座桥，最后还能回到原出 发地点？
8.1.1歌尼斯堡七桥问题 +欧拉研究了哥尼斯堡七桥问题 ·1736年，欧拉论证了该问题无解。 ·从一点出发不重复地走遍7座桥，最后又回到原来出发点 是不可能的。 ·欧拉对问题进行了抽象 描述：用4个字母A、B、 C、D代表4个城区，并用 7条边表示7座桥。 计算机导论(2014)
计算机导论(2014) 8.1.1 歌尼斯堡七桥问题 欧拉研究了哥尼斯堡七桥问题 1736年，欧拉论证了该问题无解。 从一点出发不重复地走遍7座桥，最后又回到原来出发点 是不可能的。 欧拉对问题进行了抽象 描述：用4个字母A、B、 C、D代表4个城区，并用 7条边表示7座桥
8.1.1歌尼斯堡七桥问题 +欧拉的3条判定规则 ·如果通奇数座桥的地方不止两个，满足要求的路径是找 不到的。 ·如果只有两个地方通奇数座桥，可以从这两个地方之一 出发，找到所要求的路径。 ·如果没有一个地方是通奇数座桥的，则无论从哪里出发， 所要求的路径都能实现。 计算机导论(2014)
计算机导论(2014) 欧拉的3条判定规则 如果通奇数座桥的地方不止两个，满足要求的路径是找 不到的。 如果只有两个地方通奇数座桥，可以从这两个地方之一 出发，找到所要求的路径。 如果没有一个地方是通奇数座桥的，则无论从哪里出发， 所要求的路径都能实现。 8.1.1 歌尼斯堡七桥问题
8.1.1歌尼斯堡七桥问题 +欧拉图 ·经过图中每条边一次且仅一次的路径称为欧拉路径。 如果欧拉路径的起点和终点为图中的同一个顶点，这时 的欧拉路径称为欧拉回路。 ·包含有欧拉回路的图称为欧拉图。 计算机导论(2014)
计算机导论(2014) 欧拉图 经过图中每条边一次且仅一次的路径称为欧拉路径。 如果欧拉路径的起点和终点为图中的同一个顶点，这时 的欧拉路径称为欧拉回路。 包含有欧拉回路的图称为欧拉图。 8.1.1 歌尼斯堡七桥问题
8.1.1歌尼斯堡七桥问题 +欧拉的研究工作奠定了图论的基础 ◆涉及到的后续课程 →离散数学 数据结构 ◆ 应用领域 ◆计算机网络性能分析 74 1464 802 090 ◆交通运输网络调度 1258 1121 ◆地下管网配置 234 ◆社会网络分析 航空网络 计算机导论(2014)
计算机导论(2014) 欧拉的研究工作奠定了图论的基础 涉及到的后续课程 离散数学 数据结构 应用领域 计算机网络性能分析 交通运输网络调度 地下管网配置 社会网络分析 8.1.1 歌尼斯堡七桥问题 航空网络
8.1.2哈密顿回路问题 +问题描述（周游世界游戏) 找一条从某个城市出发，经过每个城市恰好一次， 最后回到出发地的路径。 19 12 13 18 17 计算机导论(2014)
计算机导论(2014) 8.1.2 哈密顿回路问题 问题描述（周游世界游戏） 找一条从某个城市出发，经过每个城市恰好一次， 最后回到出发地的路径
8.1.2哈密顿回路问题 +哈密顿回路与欧拉回路的区别 ·哈密顿回路是访问图的每个顶点一次，而欧拉回路 是访问图的每条边一次。 ·对于一个图是否存在欧拉回路，已给出充要条件； 而对于一个图是否存在哈密顿回路，至今仍未找到 充要条件。 计算机导论(2014)
计算机导论(2014) 哈密顿回路与欧拉回路的区别 哈密顿回路是访问图的每个顶点一次，而欧拉回路 是访问图的每条边一次。 对于一个图是否存在欧拉回路，已给出充要条件； 而对于一个图是否存在哈密顿回路，至今仍未找到 充要条件。 8.1.2 哈密顿回路问题
8.1.3中国邮路问题 +问题描述 ·一个邮递员应如何选择一条路线，使他能够从邮局出发 走遍他负责送信的所有街道，最后回到邮局，并且所走 的路程最短。 ·归结为图论问题：给定一个连通无向图，求该图的一条 经过每条边至少一次的最短回路。 ·对于欧拉图，找到一条欧拉回路即可。 对于非欧拉图，才是中国邮路问题的 研究重点。 计算机导论(2014)
计算机导论(2014) 问题描述 一个邮递员应如何选择一条路线，使他能够从邮局出发， 走遍他负责送信的所有街道，最后回到邮局，并且所走 的路程最短。 归结为图论问题：给定一个连通无向图，求该图的一条 经过每条边至少一次的最短回路。 对于欧拉图，找到一条欧拉回路即可。 对于非欧拉图，才是中国邮路问题的 研究重点。 8.1.3 中国邮路问题