资源简介

《计算机数学》课程教案
教案编写人：
课程名称 计算机数学 本次内容 欧拉图与哈密顿图
授课班级 时 间 第 周 第 次 教学课时 /单元课时 /项目课时
学习目标 知识目标： 1.欧拉图 2.哈密顿图 能力目标： 1.能够掌握“一笔画”问题 2.能够理解欧拉图和哈密顿图的简单应用 素质目标： 1.培养学生动手动脑的能力 2.培养学生应用知识解决实际问题的能力
教学 重难点 欧拉图与哈密顿图的简单应用
课后总结 建议学时2课时
一、欧拉图
定义6.3.1 在无向图中，包含了所有边的一条简单通（回）路称为欧拉通（回）路.具有欧拉回路的图叫做欧拉图.
定理6.3.1 非平凡无向图存在欧拉通路的充分必要条件是非平凡无向图是连通图并且有零个或两个结点的度数为奇数，其余结点的度数为偶数.
度数为奇数点的结点是该欧拉通路中的起点和终点.
定理6.3.2 非平凡无向图是欧拉图的充分必要条件是非平凡无向图是连通图并且所有结点的度数为偶数.
例6.3.1 利用上述定理说明“哥尼斯堡七桥问题”是否有解.
解 利用上述定理可以“哥尼斯堡七桥问题”无解.因为哥尼斯堡七桥问题对应的非平凡无向图中的每个结点的度数都为奇数，而且结点数是4（如图6.3.1,6.3.2）.
图6.3.1 图6.3.2
定义6.3.2 在有向图中，包含了所有有向边的一条简单通（回）路称为欧拉通（回）路.具有欧拉回路的图叫做欧拉图.
定理6.3.2 有向图存在欧拉通路的充分必要条件是有向图是单向连通的并且图中恰有两个结点的度数为奇数，其中一个入度比出度大1，另一个出度比入度大1，而其余结点的入度与出度相等.
定理6.3.3 有向图是欧拉图的充分必要条件是有向图是强连通的并且图中每个结点的入度与出度相等.
二、哈密顿(Hamilton)图
课堂行动：由学生分组汇报自己查阅哈密顿图相关资料的情况，与同学分享其在实际生活中的应用
定义6.3.1 经过图中所有结点一次且仅一次的通（回）路称为哈密顿通（回）路.具有哈密顿回路的图称为哈密顿图.
如果图是一个图，则图中的哈密顿通路有条边，哈密顿回路有条边.
定理6.3.4 若简单无向图中任意两个不相邻的结点，的度数
，则该简单无向图存在哈密顿通路.
定理6.3.5 设简单无向图是图（其中），若图中任意两个不相邻的顶点，的度数，则该简单无向图存在哈密顿回路.图是哈密顿图.
三、应用拓展
例6.3.2 洒水车在城市街道执行洒水任务，
所负责街道的分布图如右，如果该洒水车从
装水点出发，能否通过所有的街道不重复而回
到停车点用.
解 要解决这个问题就是判断这个街道分布
图是否存在从装水点到停车点的欧拉通路.
由各点度数及定理6.3.1可知，这样的欧拉通路是存在的，比如，当然这条欧拉通路不是唯一的.
例6.3.3 某国际会议共有8人参加，他们都来自不同的国家.若他们中任何两个无共同语言的人中的每一个人与其余有共同语言的人数之和大于或等于8，问能否将这8个参会人员排在圆桌就坐，使其任何人都能与两边的人交谈？
解 我们分别用，，，，， 来表示参加该会议的8个人，若与有共同语言，就用无向边连接与，这样由点集和边集就组成了8阶简单无向图，那么就表示与有共同语言的人数.现假设与没有共同语言，则由题意知，.由定理6.3.5可知，该图中存在哈密顿回路，按此回路的顺序安排座次就可以达到任何人都能与两边的人交谈的目的.
课堂动手：同学分组讨论课后习题
《计算机数学》课程教案
教案编写人：
课程名称 计算机数学 本次内容 最短路径问题
授课班级 时 间 第 周 第 次 教学课时 /单元课时 /项目课时
学习目标 知识目标： 最短路径的概念 最短路径的算法 能力目标： 1.能够应用Dijkstra（迪克斯特拉）法求解简单的最短路径问题 素质目标： 1.培养学生逻辑思维能力 2.培养学生观察理解力
教学 重难点 1. Dijkstra（迪克斯特拉）法
课后总结 建议学时2课时
一、最短路径问题
对于简单图的每一条边，可以赋予一个实数，称为边的权，图连同它边上的权叫做赋权图.图的权为，而要解决最短路径的问题，实际上就是在一个赋权图中找出满足条件的具有最小权的子图，及求出最小的.
在简单图中求最短路径的Dijkstra算法其基本思想是：若某条线路是最短路径，那么从这条线路的起点到该线路上其它任意一点的线路也是最短路径.因此，求最短路径的基本方法可以归纳为：从起点开始，在以起点为顶点的所有线路上，找出与起点构成最短路径的相邻顶点，起点到该顶点的线路应该是整个最短路径中的一部分，然后再以该相邻顶点为新的起点，再找出一个与它有最短路径的相邻顶点，依次循环下去，直至到问题要求的终点为止，最后得出从起点到终点的一条最短路径.
我们可以将上述基本方法的步骤作简要描述：现假设从某一加权图的顶点出发，求到其余各顶点的最短路径.
（1）以表示顶点的集合，即对于，从起点到顶点的最短路径已经求出.再用表示图中除属于中的顶点以外的所有顶点的集合，即.即从起点到中的每一点的最短路径是待求的.显然，一开始时有，.用表示计算步骤，此时令.
（2）先给中的每一个顶点赋予一个指数，而指数是指如果从到有边，则，否则.求出，则有.然后求出和.则得到从到的最短路.若，则，继续进行下一步.否则终止计算.
（3）再为中的每一个顶点赋予一个新的指数=，求出=，则有，然后求出和，则得到从到的最短路径，.若，则，返回第（3）步继续进行重复的运算.否则终止计算.
例6.4.1 在下图的赋权图（图6.4.1）中，求出从到的最短路.
图6.4.1
解：详见书上例题，可将过程用表格表示如下
0 [0] 1 [1] 3 2 [2] 6 3 3 6 [3] 4 [4] 8 5 [7] 6
0 1 2 4 3 7
二、用拓展
例6.4.2 某物流公司要将货物从市 C
运往市，若到市的公路网如右图 B D
所示，该如何确定路线使路程最短呢？ A G
解 用Dijkstra算法解决这个问题. E F
借助表格表示
k A B C D E F G
0 0 1 [1] 2 2 A 5 6 [2] 8 3 [5] 6 A 8 4 B [6] 8 5 B,C [8] 10 6 B,E 10 D,F
因此最短路径为AEFG或者ABFG或者ABDG或者ABCDG，其长度均为10.

展开更多......

收起↑