图论应用.pdf

图论应用 2004数学建模竞赛辅导 复旦大学计算机科学与工程系 吴永辉 博士 2004年7月12日 基础知识  离散数学（图论）  程序设计语言  数据结构  算法设计与分析 主要参考书目 1 周咏基, 王建德. 金牌之路——竞赛解题指导. 陕西师范大学出版社. 2001. 2 吴文虎, 王建德. 实用算法的分析与程序设计. 电子工业出版社. 1998. 3 吴文虎, 王建德. 图论的算法与程序设计. 清华 大学出版社. 1997. 4 朱洪等. 离散数学教程. 上海科技文献出版社. 1966. 5 雷功炎. 数学模型讲义. 北京大学出版社. 2000. 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 网络流 连通度与块、网络最大流、图与二分图的匹配、独立集和覆盖、 Petri网 对应策略  将问题A 对应另一个便于思考或有求 解方法的问题B ，化繁为简，变未知为已 知。  将现实生活中问题转化为图问题 1）经典图论问题解析 2）图论问题解析 一、经典图论问题解析  将现实生活中问题转化为图问题的 经典问题：  1 中国邮递员问题  2 44的黑白格棋盘跳马  3 过河问题 1 中国邮递员问题  中国邮递员问题（中国数学家管梅谷） 背景： 一个邮递员从邮局出发投递信件， 他必须在所管辖范围内的所有街道至少 走一次，最后回到邮局。 问题： 选择一条最短的路线完成投递任务。 1）建立数学模型  用图描述问题 G=(V, E, ) 为一边带权的图。 V中元素为街道交叉点； E为街道集合； 街道的长度为街道对应边的权，显 然所有权均大于0 。 2）问题分析  如何选择路线？  设G=(V, E, ) 为一边带权的图，所 有权都非负。邮递员问题就转化为：  在G中，从某点v 出发求一条经过每 条边至少一次的闭路径，使该闭路径所 带的权最小。  满足条件的闭路径称为最优投递路 线 3）算法分析（解决问题的方法）：图论，分而治 之  若G为欧拉图，最优投递路线就是从指定 顶点出发的一条欧拉回路。  若G不是欧拉图，则最优投递路线必须要 有重复边出现，而要求重复边权之和达到最小。 G必有奇顶点，为了消除奇顶点，必须加若 干条重复边，使得重复边的权与原边的权相同， 设所得图为G*，则最优投递路线等价于求G*的 一条欧拉回路，使得重复边权之和   ( e ) 最小，