数学建模与数学实验 行遍性问题
行 遍 性 问 题 数学建模与数学实验
行遍性问题 、中国邮递员问题 (一)欧拉图 (二)中国邮递员问题 、推销员问题 (一)哈密尔顿图 (二)推销员问题 三、建模案例:最佳灾情巡视路线
行 遍 性 问 题 一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例：最佳灾情巡视路线 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题
定义设图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是割边的充要条件是不含在G的圈 中
7 3 1 2 3 4 1 4 5 2 5 6 6 7 8 9 割边 G的边 是割边的充要条件是 不含在G的圈 中． 割边的定义：设G连通， E(G),若从G中删除边 后， 图G-{ }不连通，则称边 为图G的割边． e e e e e e v v v v v v v e e e e e e e e e
欧抗图 定义1设G=(V,E)是连通无向图 (1)经过G的每边至少一次的闭通路称为巡回 (2)经过G的每边正好一次的巡回称为欧拉巡回 3)存在欧拉巡回的图称为欧拉图. (4)经过G的每边正好一次的道路称为欧拉道路. e e2 e5 2 V4 V3 欧拉道路:ve1v2e2l3esve4ve3v3欧拉巡回 巡回:v1e1v2e2v3esyv1e4v4e3v3ev1 V1e1v2e2v3esvie4v4e3v3e6v1
e3 v1 v2 v3 v4 e1 e4 e5 e2 e6 欧 拉 图 定义１ 设 G=(V,E)是连通无向图 （１）经过 G 的每边至少一次的闭通路称为巡回． （２）经过 G 的每边正好一次的巡回称为欧拉巡回． （３）存在欧拉巡回的图称为欧拉图． （４）经过 G 的每边正好一次的道路称为欧拉道路． e3 v1 v2 v3 v4 e1 e4 e5 e 2 巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1 欧拉道路：v1e1v2e2v3e5v1e4v4e3v3 欧拉巡回： v1e1v2e2v3e5v1e4v4e3v3e6v1