山东政法学院信息科学技术系教学大纲
8.1二分图
8.1.1二分图与完全二分图 8.1.2（Hall）定理
基本要求：了解二分图与完全二分图的定义；掌握完美匹配和完备匹配的区别和完备匹配成为完美匹配的条件。
重点：二分图，完美匹配和完备匹配 难点：完美匹配和完备匹配
教学设计：采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 8.2欧拉图与哈密顿图 8.2.1、欧拉路与欧拉图 8.2.2、哈密顿回路与哈密顿图
基本要求：理解欧拉通路、回路和欧拉图的概念。熟练掌握判定和证明欧拉图的方法。理解哈密尔顿通路、回路和哈密尔顿图的概念。会判断或证明某些图是或不是哈密尔顿图。能够应用欧拉图或者哈密顿图解决实际问题。
重点：欧拉通路、回路和欧拉图的概念；哈密尔顿通路、回路和哈密尔顿图的概念 难点：判断或证明某些图是或不是哈密尔顿图。能够应用欧拉图或者哈密顿图解决实际问题。 教学设计：采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 8.3平面图 8.3.1平面图的概念 8.3.2平面图的一些性质
基本要求：掌握平面图、平面图的对偶等概念，掌握平面图的性质了解平面图的着色问题。 重点：平面图与平面图的嵌入，平面图的面与次数，极大平面图，极小非平面图，平面图的对偶图；平面图的相关定理。
难点：平面图的性质与相关定理。
教学设计：采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 3、本章小结：
通过本章的学习应该达到下面的基本要求：
1、 弄清完美匹配与完备匹配的区别并弄清完备匹配成为完美匹配的条件。
2、 要明确图中只存在欧拉通路而无欧拉回路的图不是欧拉图，类似的图中只存在哈密顿 通路不含哈密顿回路的图不是哈密顿图；
3、 注意定理8.8是哈密顿图的必要条件而不是充分条件，；二定理8.9中的任何两个不相
邻的顶点度数之和大于等于阶数n的条件是哈密顿图的充分条件而不是必要条件。 4、 平面图中定理较多，但是许多定理与欧拉公式有关，所有是比较容易记忆和理解的。
第9树(授课6学时)
1、教学目标：
1、深刻理解无向树的定义及性质； 2、熟练地求解无向树；
3、准确地求出给定带权连通图的最小生成树；
4、深刻理解基本回路、基本割集的概念，并对给定的生成树会求出它们； 5、理解根树及其分类等概念；
16
山东政法学院信息科学技术系教学大纲
6、会画n阶（n较小）非同构的无向树及根树（1?n?6）； 7、熟练掌握求最优树及最佳前缀码的方法。 2、教学内容 9.1无向树及生成树 9.1.1无向树 9.1.2生成树 9.1.3最小生成树
基本要求：掌握树、生成树的概念以及图是树的几个等价命题 重点：树及其性质、无向树的等价定义与性质、生成树、最小生成树 难点：生成树存在条件、基本割集与基本割集系统
教学设计：采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 9.2根树及其应用 9.2.1、根树及其分类 9.2.2、根树的应用
基本要求：掌握根树，n叉树完全n叉树，二叉树完全二叉树的概念；会求完全二叉树。掌握求最优树的Huffman算法
重点：根树定义，根树的分类，最优树，前缀码与最佳前缀码，Huffman算法 难点：根树的分类，最优树，Huffman算法
教学设计：采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 3、本章小结：
1、 在求解无向树时注意将树的主要性质之一，m=n-1(m，n分别为边数和定点数)，与握手2、 在画n(?6)阶非同构的无向树时也要用到①中的性质
3、在用Huffman算法求最佳前缀码时若现将各符号出现频率乘以100，所得数作为权求最优树，则最优树的权位传输100个按给定频率出现的符号所用二进制数字的个数另外，还应该注意，最优树不一定唯一，因而所得的前缀码可能不同。但一般来说各符号的码长度不变，特别是，最优树的权是固定不变的。
定理配合在一起使用。
三、各教学环节学时分配
17
山东政法学院信息科学技术系教学大纲
章节 第1章 第2章 第3章 第4章 第5章 第6章 第7章 第8章 第9章 合计 内容 命题逻辑 一阶逻辑 集合的基本概念和运算 二元关系和函数 代数系统的一般性质 几个典型的代数系统 图的基本概念 一些特殊的图 树 学时分配 讲课 习题课 8 5 4 6 5 6 4 4 4 46 2 1 2 1 2 8 讨论课 实验（上机） 其他 合计 10 6 4 8 5 7 4 4 6 54 五、教学形式与考核方式
（一）教学形式
多种媒体教学，在课堂教学中，采用黑板粉笔和电子教案相结合的方式。电子教案中可包含讲课的梗概，算法，节省抄写黑板的时间；对于算法描述和存储描述等问题的讲解采用板书形式，动态演示分析过程，两者结合使学生对所学知识更易理解和接受。
（二）考核方式
本课程的考核分为平时作业成绩以及期末考试成绩两大部分，其中期末考试以闭卷笔试为
主。总成绩按以下公式计算：
总成绩＝作业成绩×20%＋期末成绩×80%
六、推荐教材和教学参考书
1、教材：耿素云等，离散数学，清华大学出版社，2008 2.参考书
左孝琳、李为槛、刘永才，离散数学（上海科技文献版）
七、其他说明
1．修订大纲的指导思想：根据专业特点，使学生掌握必备的离散数学基本理论
18
山东政法学院信息科学技术系教学大纲
和基本方法，为学习后继专业课程、从事科学研究或工程技术打下一定的基础。
2．本课程与先修课程和后续课程的联系与分工：先修课程解决该课程所必须的数学基础问题；本课程着重研究离散结构和相互关系；后续课程着重处理离散结构信息。
附:试题与参考答案
19