第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 歌尼斯堡七桥问题