行 遍 性 问 题,数学建模与数学实验,后勤工程学院数学教研室,行 遍 性 问 题,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,三、建模案例：最佳灾情巡视路线,（一） 欧 拉 图,（二） 中 国 邮 递 员 问 题,（一） 哈 密 尔 顿 图,（二） 推 销 员 问 题,G的边e是割边的充要条件是e不含在G的圈中,割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边,欧 拉 图,巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1,欧拉道路：v1e1v2e2v3e5v1e4v4e3v3,欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1,欧拉图,非欧拉图,返回,中国邮递员问题-定义,中国邮递员问题-算法,Fleury算法-基本思想：从任一点出发，每当访问 一条边时，先要进行检查如果可供访问的边不只 一条，则应选一条不是未访问的边集的导出子图的 割边作为访问边，直到没有边可选择为止.,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是，在
