对应策略 将问题A对应另一个便于思考或有求 解方法的问题B,化繁为简,变未知为已 知 将现实生活中问题转化为图问题 1)经典图论问题解析 2)图论问题解析
对应策略 将问题A对应另一个便于思考或有求 解方法的问题B，化繁为简，变未知为已 知。 将现实生活中问题转化为图问题 1）经典图论问题解析 2）图论问题解析
经典图论问题解析 将现实生活中问题转化为图问题的 经典问题: 1中国邮递员问题 24X4的黑自格棋盘线受 3过河问题
一、经典图论问题解析 将现实生活中问题转化为图问题的 经典问题： 1 中国邮递员问题 2 44的黑白格棋盘跳马 3 过河问题
1中国邮递员问题 中国邮递员问题(中国数学家管梅谷) 背景: 个邮递员从邮局出发投递信件, 他必须在所管辖范围内的所有街道至少 走一次,最后回到邮局 问题: 选择一条最短的路线完成投递任务
1 中国邮递员问题 中国邮递员问题（中国数学家管梅谷） 背景： 一个邮递员从邮局出发投递信件， 他必须在所管辖范围内的所有街道至少 走一次，最后回到邮局。 问题： 选择一条最短的路线完成投递任务
1)建立数学模型→用图描述问题 G=E,O)为一边带权的图 中元素为街道交叉点; E为街道集合; 街道的长度为街道对应边的权,显 然所有权均大于0
1）建立数学模型 用图描述问题 G=(V, E, )为一边带权的图。 V中元素为街道交叉点； E为街道集合； 街道的长度为街道对应边的权，显 然所有权均大于0
2)问题分析→如何选择路线? 设G=V,E,O为一边带权的图,所 有权都非负。邮递员问题就转化为: 在G中,从某点ν出发求一条经过每 条边至少一次的闭路径,使该闭路径所 带的权最小。 满足条件的闭路径称为最优投递路 线
2）问题分析 如何选择路线？ 设G=(V, E, )为一边带权的图，所 有权都非负。邮递员问题就转化为： 在 G中，从某点 v出发求一条经过每 条边至少一次的闭路径，使该闭路径所 带的权最小。 满足条件的闭路径称为最优投递路 线