1、行 遍 性 问 题撰写：刘伟 董小刚 林玎 制作：李慧玲 李刚健吉林建工学院基础科学系行 遍 性 问 题一、中 国 邮 递 员 问 题二、推 销 员 问 题三、建模案例：最佳灾情巡视路线（一） 欧 拉 图（二） 中 国 邮 递 员 问 题（一） 哈 密 尔 顿 图（二） 推 销 员 问 题V7e3v1 v2v3v4e1e2e4 e5V5V6e6e7 e8e9割边G的边 e是割边的充要条件是 e不含在 G的圈中割边的定义 ：设 G连通， e E(G),若从 G中删除边 e后，图 G-e不连通，则称边 e为图 G的割边e3v1 v2v3v4e1e2e4 e5e6欧 拉 图e3v1 v2v3v4e1
2、e2e4 e5巡回： v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路： v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e3v1 v2v3v4e1e2e4 e5e3v1 v2v3v4e1e2e4 e5e6欧拉图 非欧拉图返回中国邮递员问题 -定义中国邮递员问题 -算法Fleury算法 -基本思想 ：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边 作为访问边，直到没有边可选择为止 .V7e3v1 v2v3v4e1e2e4 e5V5V6e6e7 e8e9e10若 G不是欧拉图，则 G的任何一个巡回经过某些边必定多于一次解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小
