离散数学教案 编号.C1501 课时安排： 2学时 教学课型：理论课了 实验课口 习题课口实践课口其它口 题目（教学章、 节或主题)： Ch15欧拉图与哈密顿图 s15.1欧拉图 教学目的要求（分掌握、熟悉、了解三个层次） 理解Euler图的概念 2.掌握Euler图的判定： 教学重点、难点： I)重点：Euler图的概念、Euler图的判定 2)难点：Euler图的判定 教学方 利用黑板，CAI课件等教学 教学用具： 黑板.CAI课件及其辅助设备 教学内容（注明：重点#难点 ?疑点)： 、欧拉图基本概念(405分钟 1定义经过图中每条边一次且仅一次并且行遍图中每个顶点的通路（回路），称为欧拉通路或做拉迹（欧 拉回路或欧拉闭迹).存在欧拉回路的图，称为欧拉图 2定理无向图G具有欧拉通路，当且仅当G是连通图且有零个或两个奇度顶点若无奇度顶点，则通路为 回路：若有两个奇度顶点，则它们是每条欧拉通路的端点 3.推论无向图G为欧拉图（具有欧拉回路）当且仅当G是连通的，且G中无奇度顶点 4.定义给定G是一个无孤立结点的有向图，若存在一条单向通路（回路），经过图中每边一次且仅仅一次 则称此单向通路（回路）为该图的一条单向欧拉通路（回路）。具有单向欧拉回路的图称为欧拉图。 5.定理一个有向图D具有欧拉通路，当且仅当D是连通的，且除了两个顶点外，其余顶点的入度均等于出 度这两个特殊的顶点中，一个顶点的入度比出度大1另一个顶点的入度比出度小1 6.推论一个有向图D是欧拉图（具有欧拉回路），当且仅当D是连通的，且所有顶点的入度等于出度. 只具欧拉通路，无欧拉回路的图不是欧拉图.。 例15.1 (15.1) 例152(s15.1) 二、求欧拉回路的Fleury算法(40分钟) 三、课堂小结（约5分钟） 1501
1501 离 散 数 学 教 案 编号：C1501 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch15 欧拉图与哈密顿图 §15.1 欧拉图 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解 Euler 图的概念 2. 掌握 Euler 图的判定； 教学重点、难点： 1） 重点：Euler 图的概念、Euler 图的判定 2） 难点：Euler 图的判定 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、欧拉图基本概念（405 分钟） 1.定义 经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路),称为欧拉通路或欧拉迹(欧 拉回路或欧拉闭迹).存在欧拉回路的图,称为欧拉图. 2.定理 无向图 G 具有欧拉通路,当且仅当 G 是连通图且有零个或两个奇度顶点.若无奇度顶点,则通路为 回路;若有两个奇度顶点,则它们是每条欧拉通路的端点. 3.推论 无向图 G 为欧拉图(具有欧拉回路)当且仅当 G 是连通的,且 G 中无奇度顶点. 4.定义 给定 G 是一个无孤立结点的有向图，若存在一条单向通路(回路)，经过图中每边一次且仅仅一次， 则称此单向通路(回路)为该图的一条单向欧拉通路(回路)。具有单向欧拉回路的图称为欧拉图。 5.定理 一个有向图 D 具有欧拉通路,当且仅当 D 是连通的,且除了两个顶点外,其余顶点的入度均等于出 度.这两个特殊的顶点中,一个顶点的入度比出度大⒈另一个顶点的入度比出度小 1. 6.推论 一个有向图 D 是欧拉图(具有欧拉回路),当且仅当 D 是连通的,且所有顶点的入度等于出度. 只具欧拉通路,无欧拉回路的图不是欧拉图. 例 15.1 (§15.1 ) 例 15.2 (§15.1 ) 二、求欧拉回路的 Fleury 算法（40 分钟） 三、课堂小结（约 5 分钟）
离散数学教案 编号：C1502 课时安排： 2学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Ch15欧拉图与哈密顿图 15.2哈密顿图 §153货邮担问颗 教学目的要求（分掌握、熟悉、了解三个层次）： L.掌握Hamilton图的概念， 2.掌据Hamilton图判定的必要条件以及几个常见的充分条件 3.了解图论中的优化问题，特别是货郎担问题。 教学重点、难点： l.重点：Hamilton图的概念及判定， 2.难点：Hamilton图的判定： 教学方法： 利用黑板，CAI课件等教学 教学用具： 黑板，CA课件及其辅助设备 教学内容（注明：·重点#难点 ?疑点)： *一、哈密尔顿基本概念(45分钟) 1.定义经过图中每个顶点一次且仅一次的通路（回路）称为哈密尔顿通路（回路）.存在哈密尔顿回路的医 称为哈密尔顿图」 2.定理（必要条件1）设无向图G=是哈密尔顿图，V1是V的任意的非空子集 台G-VI)≤IV1L. 其中，p(G-VI)为从G中删除VI(删除V1中各顶点及关联的边)后所得图的连通分支数 3.定理（充分条件）设G=是简单无向图。如果对任意两个不相邻的结点u,vV,均有： deg(u+degv)≥IVM1, 则G中存在哈密尔烦通路！ 如果对任意两个不相邻的结点, veV,均有：degfu)+de()2. 则G中存在哈密尔顿回路，即G是哈密尔顿图。 4.推论n阶简单无向图G中，n>2.任意顶点的度数大于等于n/2,则G有Hamilton回路。 5. 定理在n≥2)阶有向图D-<Y,E中，如果所有有向边均用无向边代替，所得无向图中含生成子图K 则有向图D中存在哈密尔顿通路。 推论n(n≥3)阶有向完全图为哈密尔顿图
1502 离 散 数 学 教 案 编号：C1502 课时安排： 2 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch15 欧拉图与哈密顿图 §15.2 哈密顿图 §15.3 货郎担问题 教学目的要求（分掌握、熟悉、了解三个层次）： 1． 掌握 Hamilton 图的概念， 2． 掌握 Hamilton 图判定的必要条件以及几个常见的充分条件 3． 了解图论中的优化问题，特别是货郎担问题。 教学重点、难点： 1． 重点：Hamilton 图的概念及判定， 2． 难点：Hamilton 图的判定； 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、哈密尔顿基本概念（45 分钟） 1．定义 经过图中每个顶点一次且仅一次的通路(回路)称为哈密尔顿通路(回路).存在哈密尔顿回路的图 称为哈密尔顿图. 2．定理(必要条件 1) 设无向图 G=是哈密尔顿图,V1 是 V 的任意的非空子集, p(G-V1)≤V1. 其中, p(G-V1)为从 G 中删除 V1(删除 V1 中各顶点及关联的边)后所得图的连通分支数. 3．定理(充分条件 1) 设 G＝是简单无向图。如果对任意两个不相邻的结点 u，vV，均有： deg(u) + deg(v) | V|-1， 则 G 中存在哈密尔顿通路； 如果对任意两个不相邻的结点 u，vV，均有：deg(u)+deg(v)|V|， 则 G 中存在哈密尔顿回路，即 G 是哈密尔顿图。 . 4．推论 n 阶简单无向图 G 中， n>2,任意顶点的度数大于等于 n/2，则 G 有 Hamilton 回路。 5．定理 在 n(n≥2)阶有向图 D=中,如果所有有向边均用无向边代替,所得无向图中含生成子图 Kn, 则有向图 D 中存在哈密尔顿通路. 推论 n(n≥3)阶有向完全图为哈密尔顿图
例153 (15.2 例15.4（§15.2） 例15.5(s152) 例15.6(S15.2) 货郎担问题(40分钟 1,问题实质 在赋权完全图中找最小权Hamilton圈（最优圈）。 (NP-hard prob.) 2.算法：代替办法找一reasonably good solution。 例如，先找一Hamilton圈C=vlv2vvvl, 再加以改进：对任i与j,1<i+1j<v,对应有一Hamilton圈 Cij=v1v2.vivJvj-I.vi+1vj+1vj+2. 若对某i与j有(viy)+w(vi+1yj+I)<w(vivi+)+(vjWj+I) 则Cj是C的一个改进。反复进行上述步骤，直到不能再改进为止。所得Hamilton圈一般不会是 最优圈，但可能是比较好的。上述步骤也可从不同的Hamilton圈作为开始，反复进行之。令W'为所求 得最小权，它可作为最优圈C*的权的上界。 w(C+)2w. 3.下界的估计式 设v为最优圈C*上任取的一个顶点，则C*-v为G-v中的一生成树。令T为G-V中的最优树， 则w(T+w(©)+()≤w(C*),其中e,f为G中与v相关联的边中权之和为最小的二边。 三、课堂小结（约5分钟） 1503
1503 例 15.3 (§15.2 ) 例 15.4 (§15.2 ) 例 15.5 (§15.2 ) 例 15.6 (§15.2 ) 二、货郎担问题（40 分钟） 1. 问题实质 在赋权完全图中找最小权 Hamilton 圈（最优圈） 。 （NP-hard prob。） 2．算法：代替办法 找一 reasonably good solution。 例如，先找一 Hamilton 圈 C=v1v2 .v v1 ， 再加以改进： 对任 i 与 j, 1<i+1<j< , 对应有一 Hamilton 圈 Cij＝ v1v2 .vivJ vj-!.vi+1vj+1vj+2 .v v1 。 若对某 i 与 j 有 w(vi vj ) + w(vi+1vj+1) < w(vivi+1) + w(vjvj+1) 则 Cij 是 C 的一个改进。 反复进行上述步骤，直到不能再改进为止。所得 Hamilton 圈 一般不会是 最优圈，但可能是比较好的。上述步骤也可从不同的 Hamilton 圈作为开始，反复进行之。令 W’为所求 得最小权，它可作为最优圈 C*的权的上界。 w(C*) W’ 3．下界的估计式 设 v 为最优圈 C*上任取的一个顶点，则 C* - v 为 G - v 中的一生成树。令 T 为 G - v 中的最优树， 则 w(T)+w(e)+w(f) w(C*) ，其中 e，f 为 G 中与 v 相关联的边中权之和为最小的二边。 三、课堂小结（约 5 分钟）