清华大学：《计算机导论》课程电子教案（PPT教学课件）第8章 计算机领域的典型问题

⑨第8章计算机领域的典型问题 8.1图论问题 8.2算法复杂性问题 8.3计算机智能问题 8.4并发控制问题 计算机导论(2014)

计算机导论(2014) 第8章 计算机领域的典型问题 8.1 图论问题 8.2 算法复杂性问题 8.3 计算机智能问题 8.4 并发控制问题

81图论问题 歌尼斯堡七桥问题 哈密尔顿回路问题 中国邮路问题 首都经济贸易学校 清华大学美术学院 ●大望路站 ⑨万达广场 万达广场展示中心 郎家园站 八王站 国贸地铁站 东郊汽车站 计算机导论(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歌尼斯堡七桥问题 欧拉的研究工作奠定了图论的基础 涉及到的后续课程 离散数学 数据结构 →应用领域 ↓计算机网络性能分析 交通运输网络调度 ↓地下管网配置 社会网络分析 航空网络 计算机导论(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 中国邮路问题