牡丹江师范学院教案教研室应用数学教研室教师姓名赵宝江授课

牡丹江师范学院教案牡丹江师范学院教案 教研室 教研室 应用数学教研室 教师姓名 教师姓名 赵宝江 授课时间授课时间 课程名称数学模型 授课专业 和班级 授课内容 第六章 图论实验 6 1 图论的基本概念 6 2 最短路算法 授课学时2 学时 教学目的了解图论的基本概念 掌握 Dijkstra 算法 教学重点关联矩阵 联接矩阵 Dijkstra 算法 教学难点Dijkstra 算法 教具和媒体使用PPT 黑板 教学方法讲授法 练习法 包括复习旧课 引入新课 重点难点讲授 作业和习题布 置 问题讨论 归纳总结及课后辅导等内容 时间分配 90 分钟 教 学 过 程 一 简介图论 二 新课 1 图的概念 引入简单介绍图 关联函数 顶点 边 集 顶点集等概念 为以后的理解进行铺垫 2 图的矩阵表示 介绍关联矩阵和邻接矩阵作为处理 图问题的基本工具 3 重点讲授 Dijkstra 算法 让学生理解并掌握基本思 想 并会用其解决问题 辅以例题进行说明 三 小结 10 70 10 板 书 设 计 一 图的概念 1 图的定义 2 顶点的次数 二 图的矩阵表示 1 关联矩阵 2 邻接矩阵 三 Dijkstra 算法 1 基本概念 2 固定起点的最短路 Dijkstra 算法 3 例题 讲授新 拓展内容 课后总结 教研室主任签字教研室主任签字 年 月 日 讲讲 授授 内内 容容备注备注 一 一 图图 的的 概概 念念 1 图的定义 图的定义 有序三元组 G V E 称为一个图图 1 V 是有穷非空集 称为顶点集顶点集 21n vvv 其中的元素叫图 G 的顶点顶点 2 E 称为边集边集 其中的元素叫图 G 的边边 3 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射 称为关联函数关联函数 例例 1设 G V E 其中 V v1 v2 v3 v4 E e1 e2 e3 e4 e5 335414413312211 vvevvevvevvevve G 的图解如图 二 二 图图 的的 矩矩 阵阵 表表 示示 1 关联矩阵关联矩阵 对无向图 其关联矩阵 其中 ij m 不关联与若 相关联与若 ji ji ij ev ev m 0 1 M 4 3 2 1 54321 10110 01100 01011 10001 v v v v eeeee 对有向图 其关联矩阵 其中 ij m 不关联与若 的终点是若 的起点是若 ji ji ji ij ev ev ev m 0 1 1 2 邻接矩阵邻接矩阵 对无向图 其邻接矩阵 其中 ij aA 不相邻与若 相邻与若 ji ji ij vv vv a 0 1 注 假设图为简单图 A 4 3 2 1 4321 0111 1010 1101 1010 v v v v vvvv 对有向图 其邻接矩阵 其中 ij aA Evv Evv a ji ji ij 若 若 0 1 对有向赋权图 其邻接矩阵 其中 ij aA Evv ji wEvvw a ji ijjiij ij 0 若 若 为其权且若 无向赋权图的邻接矩阵可类似定义 A 4 3 2 1 4321 0537 508 3802 720 v v v v vvvv 三 三 DijkstraDijkstra 算法算法 1 基基 本本 概概 念念 定义定义 在无向图 G V E 中 顶点与边相互交错且 i 1 2 k 的有限非空序列 iii vve 1 称为一条从到的通路通路 记为 12110kkk vevevevw 0 v k v k vv W 0 边不重复但顶点可重复的通路称为道路道路 记为 k vv T 0 边与顶点均不重复的通路称为路径路径 记为 k vv P 0 通路 441125441 41 vevevevevW vv 道路 43322645211 41 vevevevevevT vv 路径 45211 41 vevevP vv 定义定义 1 设 P u v 是赋权图 G 中从 u 到 v 的路径 则称为路径 P 的权权 PEe ewPw 2 在赋权图 G 中 从顶点 u 到顶点 v 的具有最小权的路 称为 u 到 v 的最短路最短路 vuP 2 固固 定定 起起 点点 的的 最最 短短 路路 最短路是一条路径 且最短路的任一段也是最短路 假设在 u0 v0 的最短路中只取一条 则从 u0 到其余顶点的最短路将构成一棵以 u0 为 根的树 因此 可采用树生长的过程来求指定顶点到其余顶点的最短路 Dijkstra 算法算法 求 G 中从顶点 u0到其余顶点的最短路 设 G 为赋权有向图或无向图 G 边上的权均非负 对每个顶点 定义两个标记 其中 l v z v 表从顶点 u0到 v 的一条路的权 l v v 的父亲点 用以确定最短路的路线z v 算法的过程就是在每一步改进这两个标记 使最终为从顶点 u0到 v 的l v 最短路的权 S 具有永久标号的顶点集 输入 G 的带权邻接矩阵 vuw 算法步骤 算法步骤 赋初值 令 S 0u0l u 0 令 vSVS l v W u v 0 z v u0u u0 2 更新 若 l v z v vSVS l v l uW u v 则令 l v l uW u v z v u 3 设是使取最小值的中的顶点 则令 S S v l v Sv u v 4 若 转 2 否则 停止 S 用上述算法求出的就是到的最短路的权 从的父亲标记 vz 追溯到 就得到到的最 短路的路线 例例 求下图从顶点 u1到其余顶点的最短路 先写出带权邻接矩阵 0 30 640 930 2150 970 160 8120 W 因 G 是无向图 故 W 是对称阵 参考文献 1 萧树铁 数学实验 高等教育出版社 2 赵静等 数学建模与数学实验 第 2 版 高等教育出版社 3 朱道元等 数学建模案例精选 科学出版社 4 刘来福等 数学模型与实验 北京师范大学出版社 5 姜启源 何青等 数学实验 高等教育出版社 牡丹江师范学院教案牡丹江师范学院教案 教研室 教研室 应用数学教研室 教师姓名 教师姓名 赵宝江 授课时间授课时间 课程名称数学模型 授课专业 和班级 授课内容 6 2 最短路算法 实验 选址问题 中心问题 授课学时2 学时 教学目的掌握用 Floyd 算法求每对顶点之间的最短路算法及其应用 教学重点Floyd 算法及其应用 教学难点Floyd 算法的应用 教具和媒体使用黑板和 PPT 教学方法启发式 讲授法 练习法 讨论法 包括复习旧课 引入新课 重点难点讲授 作业和习题布 置 问题讨论 归纳总结及课后辅导等内容 时间分配 90 分钟 教 学 过 程 一 复习 二 新课 1 练习 Floyd 算法 以分组讨论的形式进行 2 Floyd 算法的 matlab 实现 主要让学生领会循环的思想 处理的手段和怎样 联系到实例 3 综合应用 应用所学的算法解决实际问题 分组讨论 三 小结 10 70 5 板 书 设 计 一 练习 二 Floyd 算法的 matlab 实现 三 综合应用 讲授新 拓展内容 课后总结 教研室主任签字教研室主任签字 年 月 日 87 讲 授 内 容备注 一一 练习练习 求任一两点间的距离与路径 写出矩阵形式 二二 FloydFloyd 算法的算法的 matlabmatlab 实现实现 n size a 1 D a path zeros n n for i 1 n for j 1 n if D i j inf path i j j j 是 i 的后续点 end end end for k 1 n for i 1 n for j 1 n if D i j D i k D k j D i j D i k D k j path i j path i k end end end end p sp mp sp for k 1 n if mp ep d path mp ep p p d mp d end end d D sp ep path p 三三 综合应用 中心选址问题 综合应用 中心选址问题 1 某城市要建立一个消防站 为该市所属的七个区服务 如图所示 问应设在 88 那个区 才能使它至最远区的路径最短 解 1 用 Floyd 算法求出距离矩阵 D ij d 2 计算在各点设立服务设施的最大服务距离 i v i vS max 1 ij j i dvS 2 1 i 3 求出顶点 使 k v min 1 i i k vSvS 则就是要求的建立消防站的地点 此点称为图的中心点中心点 k v 05 15 55 8647 5 10475 45 25 5 5 5403247 5 87305710 65 425025 45 247203 75 5730 0 D S v1 10 S v2 7 S v3 6 S v4 8 5 S v5 7 S v6 7 S v7 8 5 S v3 6 故应将消防站设在 v3处 算法 a 0 3 inf inf inf inf inf 3 0 2 inf 18 2 5 inf inf 2 0 6 2 inf inf inf inf 6 0 3 inf inf inf 18 2 3 0 4 inf inf 2 5 inf inf 4 0 1 5 inf inf inf inf inf 1 5 0 D R floyd a 参考文献 1 萧树铁 数学实验 高等教育出版社 2 赵静等 数学建模与数学实验 第 2 版 高等教育出版社 3 朱道元等 数学建模案例精选 科学出版社 4 刘来福等 数学模型与实验 北京师范大学出版社 5 姜启源 何青等 数学实验 高等教育出版社 05 15 55 8647 5 10475 45 25 5 5 5403247 5 87305710 65 425025 45 247203 75 5710530 D 89 牡丹江师范学院教案牡丹江师范学院教案 教研室 应用数学教研室教研室 应用数学教研室 教师姓名 赵宝江教师姓名 赵宝江 授课时间授课时间 课程名称数学模型 授课专业 和班级 授课内容 6 2 最短路算法 实验 设备更新问题 授课学时2 学时 教学目的掌握 Dijkstra 和 floyd 算法的的 matlab 实现过程 教学重点算法的基本思想和主题的实现过程 教学难点算法的基本思想 教具和媒体使用PPT 和黑板 教学方法讲练结合 包括复习旧课 引入新课 重点难点讲授 作业和习题布 置 问题讨论 归纳总结及课后辅导等内容 时间分配 90 分钟 教 学 过 程 一 复习 两种算法基本原理 二 新课 1 基于 matlab Dijkstra 算法 强调程序的主题实现过程 2 基于 matlab 的 floyd 算法 强调程序的主题实现过程 3 练习 三 小结与答疑和作业 10 70 10 板 书 设 计 讲授新 拓展内容 课后总结 教研室主任签字教研室主任签字 年 月 日 90 讲讲 授授 内内 容容备注备注 1 基于 matlab Dijkstra 算法的实现 一般模式 function l z Dijkstra W w n size W 1 for i 1 n l i W 1 i z i 1 end i 1 while il j W j i l i l j W j i z i j if jD i k D k j D i j D i k D k j path i j path i k end end end end p sp mp sp for k 1 n if mp ep d path mp ep p p d mp d end end d D sp ep path p 实验 如图 有一批货物要从 v1 运到 v9 弧旁数字表示该段路长 求最短运输路线 v v v 1 1 1 v v v 9 9 9 v v v 5 5 5 v v v 4 4 4 v v v 8 8 8 v v v 7 7 7 v v v 6 6 6 v v v 3 3 3 v v v 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 2 52 52 5 5 5 5 2 2 2 2 2 2 2 2 2 1 1 1 4 4 4 0 0 0 答案 v1v1v1 v v v 9 9 9 v8v8v8 v v v 7 7 7 v6v6v6 v v v 5 5 5 v4v4v4 v3v3v3 v2v2v2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 2 52 52 5 5 5 5 2 2 2 2 2 2 2 2 2 1 1 1 4 4 4 0 0 0 3 3 3 4 4 4 6 6 6 7 7 7 5 5 5 6 6 6 8 8 8 5 5 5 9 9 9 92 4 作业 任选其一 1 下表为某工程的全部工序以及工序时间与 紧前工序 工 序ABCDEFGHIJK 工序时间 天 247310243232 紧前工序 AAABC D KE