复旦大学：《离散数学》课程教学讲义（图论）图论应用、图论算法

图论应用 2004数学建模竞赛辅导 复旦大学计算机科学与工程系 吴永辉博士 2004年7月12日

图论应用 2004数学建模竞赛辅导 复旦大学计算机科学与工程系 吴永辉 博士 2004年7月12日

基础知识 ■离散数学(图论) 程序设计语言 ■数据结构 算法设计与分析

基础知识  离散数学（图论）  程序设计语言  数据结构  算法设计与分析

主要参考书目 周咏基,王建德.金牌之路——竞赛解题指导. 陕西师范大学出版社.2001 2吴文虎,王建德.实用算法的分析与程序设计 电子工业出版社.1998 3吴文虎,王建德.图论的算法与程序设计.清华 大学出版社.1997 4朱洪等.离散数学教程.上海科技文献出版社. 1966. 5雷功炎.数学模型讲义.北京大学出版社.2000

主要参考书目 1 周咏基, 王建德. 金牌之路——竞赛解题指导. 陕西师范大学出版社. 2001. 2 吴文虎, 王建德. 实用算法的分析与程序设计. 电子工业出版社. 1998. 3 吴文虎, 王建德. 图论的算法与程序设计. 清华 大学出版社. 1997. 4 朱洪等. 离散数学教程. 上海科技文献出版社. 1966. 5 雷功炎. 数学模型讲义. 北京大学出版社. 2000

6 Thomas h, foremen etc introduction to Algorithm(算法导论)高等教育出版社, The mit press, 2002 7 Kenneth H. Rosen Discrete Mathematics and its applications(离散数学及其应用).(4th Edition).2002.机械工业出版社, MCGraw-Hil (中、英文版) 8 Bela bollobas. Modern graph Theory(现代图论) 科学出版社& Springer.2001

6 Thomas H. Coremen, etc. Introduction to Algorithm（算法导论）. 高等教育出版社， The MIT Press. 2002 7 Kenneth H. Rosen. Discrete Mathematics and its Applications（离散数学及其应用）. (4th Edition). 2002. 机械工业出版社, McGraw-Hill. (中、英文版 ) 8 Bela Bollobas. Modern Graph Theory (现代图论). 科学出版社 & Springer. 2001

图论综述 1图的基本概念 图的基本概念、路与回路、欧拉图、哈密顿图、最短路 ■2平面图 平面图与欧拉公式 3图的着色 顶点着色、平面图的着色、边的着色 4树 树的性质、生成树与割集、树的计数、有根树与二分树、最优 树 5网络流 连通度与块、网络最大流、图与二分图的匹配、独立集和覆盖、 Peti网

图论综述  1 图的基本概念 图的基本概念、路与回路、欧拉图、哈密顿图、最短路  2 平面图 平面图与欧拉公式  3 图的着色 顶点着色、平面图的着色、边的着色  4 树 树的性质、生成树与割集、树的计数、有根树与二分树、最优 树  5 网络流 连通度与块、网络最大流、图与二分图的匹配、独立集和覆盖、 Petri网

对应策略 将问题A对应另一个便于思考或有求 解方法的问题B,化繁为简,变未知为已 知 将现实生活中问题转化为图问题 1)经典图论问题解析 2)图论问题解析

对应策略  将问题A对应另一个便于思考或有求 解方法的问题B，化繁为简，变未知为已 知。  将现实生活中问题转化为图问题 1）经典图论问题解析 2）图论问题解析

经典图论问题解析 将现实生活中问题转化为图问题的 经典问题: 1中国邮递员问题 24X4的黑自格棋盘线受 3过河问题

一、经典图论问题解析  将现实生活中问题转化为图问题的 经典问题：  1 中国邮递员问题  2 44的黑白格棋盘跳马  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出发求一条经过每 条边至少一次的闭路径，使该闭路径所 带的权最小。  满足条件的闭路径称为最优投递路 线