云南师范大学：《数学建模与数学实验》课程PPT教学讲义_第9讲 行遍性问题（费培之）

(数学模型 数学建模与数学实验 行遍性问题

行 遍 性 问 题 数学建模与数学实验

行遍性戶 (数学模 中国邮递员问题 (一)欧拉图 (二)中国邮递员问题 二、推销员问题 (一)哈密尔顿图 (二)推销员问题 三、建模案例:最仹灾情巡视路线

行 遍 性 问 题 一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例：最佳灾情巡视路线 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题

(数学模丝) 定义设图G=(V,E),M<E,若M的边互不相邻, 则称M是G的一个匹配 若顶点ⅴ与M的一条边关联,则称v是M-饱和的 设M是G的一个匹配,若G的每个顶点都是M一饱和的,则 称M是G的理想匹配

定义 设图 G =（V，E），M E，若 M 的边互不相邻， 则称 M 是 G 的一个匹配. 若顶点 v与 M 的一条边关联，则称 v是 M—饱和的 设 M 是 G 的一个匹配，若 G 的每个顶点都是 M—饱和的，则 称 M 是 G 的理想匹配

(数学模丝) 割边的定义:设G连通,e∈E(G)若从G中删除边e后, 图G-{e}不连通,则称边e为图G的割边 割边 G的边e是割边的充要条件是e不含在G的圈中

V7 e3 v1 v2 v3 v4 e1 e4 e5 e2 V5 V6 e6 e7 e8 e9 割边 G的边e是割边的充要条件是e不含在G的圈中． 割边的定义：设G连通，e E(G),若从G中删除边e后， 图G-{e}不连通，则称边e为图G的割边． 

(数学模型 欧拉图 定义1设G=(VE)是连通无向图 (1)经过G的每边至少一次的闭通路称为巡回 (2)经过G的每边正好一次的巡回称为欧拉巡回 (3)存在欧拉巡回的图称为欧拉图 (4)经过G的每边正好一次的道路称为欧拉道路 e 欧拉道路: Vielv e VaesvieaV,e? v 欧拉巡回: 巡回:v1e1v2e2v3e3v1e4ve3v3e3v1 Vieiv e v3esvieve3v3e6 V

e3 v1 v2 v3 v4 e1 e4 e5 e2 e6 欧 拉 图 定义１ 设 G=(V,E)是连通无向图 （１）经过 G 的每边至少一次的闭通路称为巡回． （２）经过 G 的每边正好一次的巡回称为欧拉巡回． （３）存在欧拉巡回的图称为欧拉图． （４）经过 G 的每边正好一次的道路称为欧拉道路． e3 v1 v2 v3 v4 e1 e4 e5 e2 巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1 欧拉道路：v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回： v1e1v2e2v3e5v1e4v4e3v3e6v1

(数学模型 定理1对于非空连通图G,下列命题等价: (1)G是欧拉图 (2)G无奇次顶点 (3)G的边集能划分为圈 欧拉图 非欧拉图 推论1设G是非平凡连通图,则G有欧拉道路的充要条 件是G最多只有两个奇次顶点 返回

定理１ 对于非空连通图 G，下列命题等价： （１）G 是欧拉图． （２）G 无奇次顶点． （３）G 的边集能划分为圈． 推论１ 设 G 是非平凡连通图，则 G 有欧拉道路的充要条 件是 G 最多只有两个奇次顶点． e3 v1 v2 v3 v4 e1 e4 e5 e2 e3 v1 v2 v3 v4 e1 e4 e5 e2 e6 欧拉图 非欧拉图 返回

(数学模型 中国邮递员问题-定义 邮递员发送邮件时,要从邮局出发,经过他投递范围内的 每条街道至少一次,然后返回邮局,但邮递员希望选择一条行 程最短的路线.这就是中国邮递员问题 若将投递区的街道用边表示,街道的长度用边权 表示,邮局街道交叉口用点表示,则一个投递区构成 个赋权连通无向图.中国邮递员问题转化为:在 个非负加权连通图中,寻求一个权最小的巡回.这样 的巡回称为最佳巡回

中国邮递员问题-定义 邮递员发送邮件时，要从邮局出发，经过他投递范围内的 每条街道至少一次，然后返回邮局，但邮递员希望选择一条行 程最短的路线．这就是中国邮递员问题. 若将投递区的街道用边表示，街道的长度用边权 表示，邮局街道交叉口用点表示，则一个投递区构成 一个赋权连通无向图．中国邮递员问题转化为：在一 个非负加权连通图中，寻求一个权最小的巡回．这样 的巡回称为最佳巡回．

(数学模型 中国邮递员问题一犷法 l、G是欧拉图 此时G的任何一个欧拉巡回便是最佳巡回.问题归结 为在欧拉图中确定一个欧拉巡回 Fleury算法:求欧拉图的欧拉巡回 Fleury算法基本思想:从任一点出发,每当访问 条边时,先要进行检查.如果可供访问的边不只 条,则应选一条不是未访问的边集的导出子图的 割边作为访问边,直到没有边可选择为止

中国邮递员问题-算法 1、G是欧拉图 此时 G 的任何一个欧拉巡回便是最佳巡回．问题归结 为在欧拉图中确定一个欧拉巡回． Fleury 算法：求欧拉图的欧拉巡回 Fleury算法-基本思想：从任一点出发，每当访问 一条边时，先要进行检查．如果可供访问的边不只 一条，则应选一条不是未访问的边集的导出子图的 割边作为访问边，直到没有边可选择为止

(数学模丝) Fleury算法算法步骤 (1)任选一个顶点v,令道路w0=v0 (2)假定道路w;=ν0emνe2…vν;已经选好,则从El{ep,e2,…;e;}中选 条边e+,使: )e;+r与v相关联 b)除非不能选择,否则一定要使e;+r不是G;=G[E-{eh,e2,…;e}] 的割边 (3)第(2)步不能进行时就停止 8 e V 6

V 7 e 3 v 1 v2 v3 v4 e 1 e 4 e 5 e 2 V 5 V 6 e 6 e 7 e 8 e 9 e10 Fleury 算法—算法步骤： （１）任选一个顶点 v0，令道路 w0 = v0 （２）假定道路 wi = v0e1v1e2…eivi 已经选好，则从 E\{e1 , e2 , …, ei}中选 一条边 ei+1，使： a）ei+1 与 vi 相关联 b）除非不能选择，否则一定要使 ei+1 不是 Gi = G[E-{e1 , e2 , …,ei }] 的割边． （３）第（２）步不能进行时就停止．

(数学模型 2、G不是欧拉图 若G不是欧拉图,则G的任何一个巡回经过某 些边必定多于一次 解决这类问题的一般方法是,在一些点对之间 引入重复边(重复边与它平行的边具有相同的权) 使原图成为欧拉图,但希望所有添加的重复边的 权的总和为最小

2、G 不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某 些边必定多于一次． 解决这类问题的一般方法是，在一些点对之间 引入重复边（重复边与它平行的边具有相同的权）， 使原图成为欧拉图，但希望所有添加的重复边的 权的总和为最小．