【大学课件】数学建模与数学实验 行遍性问题.ppt
《【大学课件】数学建模与数学实验 行遍性问题.ppt》由会员分享,可在线阅读,更多相关《【大学课件】数学建模与数学实验 行遍性问题.ppt(21页珍藏版)》请在三一文库上搜索。
1、行 遍 性 问 题,数学建模与数学实验,http:/ 遍 性 问 题,一、中 国 邮 递 员 问 题,二、推 销 员 问 题,三、建模案例:最佳灾情巡视路线,(一) 欧 拉 图,(二) 中 国 邮 递 员 问 题,(一) 哈 密 尔 顿 图,(二) 推 销 员 问 题,http:/ 是割边的充要条件是 不含在G的圈中,割边的定义:设G连通, E(G),若从G中删除边 后,图G- 不连通,则称边 为图G的割边,http:/ 拉 图,巡回:v1e1v2e2v3e5v1e4v4e3v3e5v1,欧拉道路:v1e1v2e2v3e5v1e4v4e3v3,欧拉巡回: v1e1v2e2v3e5v1e4v4e
2、3v3e6v1,http:/ 一条边时,先要进行检查如果可供访问的边不只 一条,则应选一条不是未访问的边集的导出子图的 割边作为访问边,直到没有边可选择为止.,http:/ 引入重复边(重复边与它平行的边具有相同的权), 使原图成为欧拉图,但希望所有添加的重复边的 权的总和为最小,http:/ 密 尔 顿 图,返回,http:/ 在加权图G=(V,E)中, ()权最小的哈密尔顿圈称为最佳H圈 ()经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路,一般说来,最佳哈密尔顿圈不一定是最佳推销员回路,同样最佳推销员回路也不一定是最佳哈密尔顿圈,H回路,长22,最佳推销员回路,长4,http:/ 对以下完备图,用二边逐次修正法求较优H圈,http:/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学课件 【大学课件】数学建模与数学实验 行遍性问题 大学 课件 数学 建模 实验 行遍性 问题
链接地址:https://www.31doc.com/p-3024115.html