(数学模型 数学建模与数学实验 行遍性问题
行 遍 性 问 题 数学建模与数学实验
行遍性戶 (数学模 中国邮递员问题 (一)欧拉图 (二)中国邮递员问题 二、推销员问题 (一)哈密尔顿图 (二)推销员问题 三、建模案例:最仹灾情巡视路线
行 遍 性 问 题 一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例：最佳灾情巡视路线 （一） 欧 拉 图 （二） 中 国 邮 递 员 问 题 （一） 哈 密 尔 顿 图 （二） 推 销 员 问 题
(数学模丝) 定义设图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