数学建模与数学实验 行遍性问题 后勤工程学院数学教研厔
行 遍 性 问 题 数学建模与数学实验 后勤工程学院数学教研室
行遍性问题 中国邮递员问题 (一)欧拉图 (二)中国邮递员问题 二、推销员问题 (一)哈密尔顿图 (二)推销员问题 三、建模案例:最佳灾情巡视路线
行 遍 性 问 题 一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例：最佳灾情巡视路线 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题
定义设图G=(V,E),McE,若M的边互不相邻, 则称M是G的一个匹配 若顶点v与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的每边正好一次的道路称为欧拉道路 欧拉道路:v;e1v2e2v3e3v1ev4e3V3欧拉巡回: 巡回:v;e1v2e2v3esv1eav4e3v2esyv V1e1v2e2v3es V1e4 v4e3 v3e6V1
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