《离散数学》课程教学大纲一、课程信息课程名称：离散数学Discrete Mathematics课程编码：06S1021B课程类别：专业选修课适用专业：数学与应用数学专业（师范类）课程学时：32学时课程学分：2学分修读学期：第5学期先修课程：数学分析、高等代数、MATLAB语言或C语言二、课程目标（一）具体目标通过本课程的学习，使学生达到以下目标：1.掌握逻辑运算的基本概念和基本法则，能够运用逻辑运算法则判断逻辑命题的正确性，能够运用逻辑运算法则构建复杂的逻辑命题，能够运用逻辑运算法则进行逻辑推理；掌握集合、映射等基本概念，掌握集合运算、映射运算的基本法则，能够熟练地进行集合运算和映射运算；掌握图论的基本概念，掌握图和树的基本性质，能够分析图的简单性质。【支撑毕业要求3、4】2.能够正确地理解现有程序背后的逻辑关系，能够正确地设计具有复杂逻辑关系的新型程序；能够用集合、映射的观点看待和分析程序；能够用图论的观点组织复杂数据。【支撑毕业要求3、4、7】3.在分析问题、解决问题的过程中，能够自觉地运用逻辑运算法则进行思考，从而保证结论的正确性；在分析问题、解决问题的过程中，能够自觉地运用集合论的观点界定讨论的内涵与外延，能够自觉地运用映射的观点洞察不同问题之间的内在联系；在分析问题、解决问题的过程中，能够自觉地运用图论的观点看待对象之间的复杂关系。【支撑毕业要求3、4、7】（二）课程目标与毕业要求的对应关系
《离散数学》课程教学大纲 一、课程信息 课程名称：离散数学 Discrete Mathematics 课程编码：06S1021B 课程类别：专业选修课 适用专业：数学与应用数学专业（师范类） 课程学时：32学时 课程学分：2学分 修读学期：第5学期 先修课程：数学分析、高等代数、MATLAB语言或C语言 二、课程目标 （一）具体目标 通过本课程的学习，使学生达到以下目标： 1. 掌握逻辑运算的基本概念和基本法则，能够运用逻辑运算法则判断逻辑 命题的正确性，能够运用逻辑运算法则构建复杂的逻辑命题，能够运用逻辑运算 法则进行逻辑推理；掌握集合、映射等基本概念，掌握集合运算、映射运算的基 本法则，能够熟练地进行集合运算和映射运算；掌握图论的基本概念，掌握图和 树的基本性质，能够分析图的简单性质。【支撑毕业要求3、4】 2. 能够正确地理解现有程序背后的逻辑关系，能够正确地设计具有复杂逻 辑关系的新型程序；能够用集合、映射的观点看待和分析程序；能够用图论的观 点组织复杂数据。【支撑毕业要求3、4、7】 3. 在分析问题、解决问题的过程中，能够自觉地运用逻辑运算法则进行思 考，从而保证结论的正确性；在分析问题、解决问题的过程中，能够自觉地运用 集合论的观点界定讨论的内涵与外延，能够自觉地运用映射的观点洞察不同问题 之间的内在联系；在分析问题、解决问题的过程中，能够自觉地运用图论的观点 看待对象之间的复杂关系。【支撑毕业要求3、4、7】 （二）课程目标与毕业要求的对应关系
表1 课程目标与毕业要求的对应关系课程目标支撑的毕业要求支撑的毕业要求指标点3-1具有丰富的数学专业知识和专业核心素养，具有较强的空间抽象、逻辑思维、合情推理和计算能力，对数学学科知识结构体系的3.学科素养课程目标1建构有正确、清晰、合理的认识。4.教学能力4-3了解数学教学研究的基本思想和基本方法，了解数学科学的新发展和教学领域的一些最新研究成果，具有一定的教学研究能力。3-1具有丰富的数学专业知识和专业核心素养，具有较强的空间抽象、逻辑思维、合情推理和计算能力，对数学学科知识结构体系的3.学科素养建构有正确、清晰、合理的认识。课程目标 24.教学能力4-3了解数学教学研究的基本思想和基本方法，了解数学科学的新7.学会反恩发展和教学领域的一些最新研究成果，具有一定的教学研究能力。7-1具有自主学习、终身学习和专业发展意识，有不断学习和适应发展的能力。3-1具有丰富的数学专业知识和专业核心素养，具有较强的空间抽象、逻辑思维、合情推理和计算能力，对数学学科知识结构体系的3.学科素养建构有正确、清晰、合理的认识。课程目标34.教学能力4-3了解数学教学研究的基本思想和基本方法，了解数学科学的新7.学会反思发展和教学领域的一些最新研究成果，具有一定的教学研究能力。7-1具有自主学习、终身学习和专业发展意识，有不断学习和适应发展的能力。三、课程内容（一）课程内容与课程目标的关系表2课程内容与课程目标的关系教学方法学时安排课程内容支撑的课程目标第一部分数理逻辑12课堂讲授，课堂讨论，上机实验课程目标1、2、3第二部分集合论8课堂讲授，上机实验课程目标1、2、3第三部分图论12课堂讲授，专题研讨，上机实验课程目标1、2、3合计32学时（二）具体内容
表1 课程目标与毕业要求的对应关系 课程目标 支撑的毕业要求 支撑的毕业要求指标点 课程目标 1 3.学科素养 4.教学能力 3-1 具有丰富的数学专业知识和专业核心素养，具有较强的空间抽 象、逻辑思维、合情推理和计算能力，对数学学科知识结构体系的 建构有正确、清晰、合理的认识。 4-3 了解数学教学研究的基本思想和基本方法，了解数学科学的新 发展和教学领域的一些最新研究成果，具有一定的教学研究能力。 课程目标 2 3.学科素养 4.教学能力 7.学会反思 3-1 具有丰富的数学专业知识和专业核心素养，具有较强的空间抽 象、逻辑思维、合情推理和计算能力，对数学学科知识结构体系的 建构有正确、清晰、合理的认识。 4-3 了解数学教学研究的基本思想和基本方法，了解数学科学的新 发展和教学领域的一些最新研究成果，具有一定的教学研究能力。 7-1 具有自主学习、终身学习和专业发展意识，有不断学习和适应 发展的能力。 课程目标 3 3.学科素养 4.教学能力 7.学会反思 3-1 具有丰富的数学专业知识和专业核心素养，具有较强的空间抽 象、逻辑思维、合情推理和计算能力，对数学学科知识结构体系的 建构有正确、清晰、合理的认识。 4-3 了解数学教学研究的基本思想和基本方法，了解数学科学的新 发展和教学领域的一些最新研究成果，具有一定的教学研究能力。 7-1 具有自主学习、终身学习和专业发展意识，有不断学习和适应 发展的能力。 三、课程内容 （一）课程内容与课程目标的关系 表2 课程内容与课程目标的关系 课程内容 教学方法 支撑的课程目标 学时安排 第一部分 数理逻辑 课堂讲授，课堂讨论，上机实验 课程目标 1、2、3 12 第二部分 集合论 课堂讲授，上机实验 课程目标 1、2、3 8 第三部分 图论 课堂讲授，专题研讨，上机实验 课程目标 1、2、3 12 合计 32 学时 （二）具体内容
第一部分数理逻辑（12学时）第一章命题逻辑的基本概念（2学时）【教学目标与要求】1、教学目标：数理逻辑是用数学方法来研究逻辑推理规律的方法。本章主要介绍命题、联结词、真值等概念，学会将命题符号化的基本方法，是学习后面章节的基础2、教学要求：掌握命题的定义，并会判断一个描述是否是命题：明确五个基本联结词否定、合取、析取、蕴含、等价的逻辑含义，熟练掌握五个基本真值表；掌握命题的符号化方法；理解命题公式的递归定义，会建立公式的真值表，用真值表判断公式的真假，熟练判断一个公式是否是重言式、可满足式与矛盾式。【教学重点与难点】1、教学重点：命题符号化，真值表，判断公式的类型。2、教学难点：命题的正确符号化。【教学内容】1.1命题与联结词1.2命题公式及其赋值第二章命题逻辑等值演算（4学时）【教学目标与要求】1、教学目标：本章主要介绍命题公式的等值式、析取范式、合取范式等概念，通过本章学习，会求命题公式的主析取范式和主合取范式的方法，应用主析取范式或主合取范式求公式的成真赋值，判断公式的类型。2、教学要求：理解等值式的必要性、会进行等值变换；理解析取范式与合取范式的定义及构成，熟练地求命题公式的主析取范式或主合取范式；明确联结词的完备集的概念，会判断一个联结词集是否是完备的【教学重点与难点】1、教学重点：等值演算，求主析取范式，联结词完备集的判断。2、教学难点：求主析取范式
第一部分 数理逻辑（12 学时） 第一章 命题逻辑的基本概念（2 学时） 【教学目标与要求】 1、教学目标： 数理逻辑是用数学方法来研究逻辑推理规律的方法。本章主要介绍命题、联 结词、真值等概念，学会将命题符号化的基本方法，是学习后面章节的基础。 2、教学要求： 掌握命题的定义，并会判断一个描述是否是命题；明确五个基本联结词否定、 合取、析取、蕴含、等价的逻辑含义，熟练掌握五个基本真值表；掌握命题的符 号化方法；理解命题公式的递归定义，会建立公式的真值表，用真值表判断公式 的真假，熟练判断一个公式是否是重言式、可满足式与矛盾式。 【教学重点与难点】 1、教学重点：命题符号化，真值表，判断公式的类型。 2、教学难点：命题的正确符号化。 【教学内容】 1.1 命题与联结词 1.2 命题公式及其赋值 第二章 命题逻辑等值演算（4 学时） 【教学目标与要求】 1、教学目标： 本章主要介绍命题公式的等值式、析取范式、合取范式等概念，通过本章学 习，会求命题公式的主析取范式和主合取范式的方法，应用主析取范式或主合取 范式求公式的成真赋值，判断公式的类型。 2、教学要求： 理解等值式的必要性、会进行等值变换；理解析取范式与合取范式的定义及 构成，熟练地求命题公式的主析取范式或主合取范式；明确联结词的完备集的概 念，会判断一个联结词集是否是完备的。 【教学重点与难点】 1、教学重点： 等值演算，求主析取范式，联结词完备集的判断。 2、教学难点： 求主析取范式
【教学内容】2.1等值式2.2析取范式与合取范式2.3联结词的完备集第三章命题逻辑的推理理论（2学时）【教学目标与要求】1、教学目标：本章从逻辑推理角度理解命题演算，给出了推理形式结构的三种形式，通过学习，会有不同的方法判断推理的正确性，对自然推理系统、推理规则有一定的认识。2、教学要求：理解并掌握推理形式结构的三种形式，熟练掌握判断推理是否正确的不同方法，如真值表法、等值演算法与主析取范式法等；理解形式系统、自然推理系统、公理推理系统的概念；掌握12种规则进行推理；掌握附加前提证明法、归谬法的构造性证明方法。【教学重点与难点】1、教学重点：推理的三种形式与结构；判断推理是否正确；会构造自然推理系统中的推理过程；附加前提证明法、归谬法的来源及应用。2、教学难点：判断推理是否正确的三种方法；附加前提证明法、归谬法证明。【教学内容】3.1推理的形式结构3.2自然推理系统第四章一阶逻辑基本概念（1学时）【教学目标与要求】1、教学目标：本章是将命题演算扩充，引入个体词、谓词、量词的概念，进一步将命题符号化，构成一阶逻辑公式，学会在确定的解释下判断公式的真假。2、教学要求：理解个体词、谓词、量词的含义：能够准确地将给定的命题符号化；深刻理
【教学内容】 2.1 等值式 2.2 析取范式与合取范式 2.3 联结词的完备集 第三章 命题逻辑的推理理论（2 学时） 【教学目标与要求】 1、教学目标： 本章从逻辑推理角度理解命题演算，给出了推理形式结构的三种形式，通过 学习，会有不同的方法判断推理的正确性，对自然推理系统、推理规则有一定的 认识。 2、教学要求： 理解并掌握推理形式结构的三种形式，熟练掌握判断推理是否正确的不同方 法，如真值表法、等值演算法与主析取范式法等；理解形式系统、自然推理系统、 公理推理系统的概念；掌握 12 种规则进行推理；掌握附加前提证明法、归谬法 的构造性证明方法。 【教学重点与难点】 1、教学重点：推理的三种形式与结构；判断推理是否正确；会构造自然推 理系统中的推理过程；附加前提证明法、归谬法的来源及应用。 2、教学难点：判断推理是否正确的三种方法；附加前提证明法、归谬法证 明。 【教学内容】 3.1 推理的形式结构 3.2 自然推理系统 第四章 一阶逻辑基本概念（1 学时） 【教学目标与要求】 1、教学目标： 本章是将命题演算扩充，引入个体词、谓词、量词的概念，进一步将命题符 号化，构成一阶逻辑公式，学会在确定的解释下判断公式的真假。 2、教学要求： 理解个体词、谓词、量词的含义；能够准确地将给定的命题符号化；深刻理
解永真式、矛盾式、可满足式的概念及判别方法；深刻理解闭式的概念及性质；对于给定解释I，会在解释I下解释公式并判断真假。【教学重点与难点】1、教学重点：给定命题符号化、一阶逻辑公式的解释与判断。2、教学难点：谓词公式类型的判别。【教学内容】4.1一阶逻辑命题符号化4.2一阶逻辑公式及其解释第五章一阶逻辑等值演算与推理（1学时）【教学目标与要求】1、教学目标：本章要学会利用一阶逻辑等值式、置换规则，会进行一阶逻辑演算，求一阶逻辑前束范式，知道在自然推理系统中的推理规则，并能进行有效推理的证明。2、教学要求：深刻理解一阶逻辑等值式的定义；理解二足基本等值式的来源及意义，并会熟练地使用这些等值式；熟练使用等值规则，能分别换名规则及代替规则；会求一阶逻辑前束范式；深刻理解自然推理系统的定义，牢记自然推理系统中各条推理规则，正确使用_、+、三和3和规则；能正确地给出有效推理的证明。【教学重点与难点】1、教学重点：有效推理证明方法。2、教学难点：有效推理的证明。【教学内容】5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论实验目的与要求：（实验2学时）加深对命题推理逻辑方法的理解，要求会用计算机对命题逻辑公式化简，会用命题逻辑推理的方法解决逻辑推理问题，要求用MATLAB或C语言实现
解永真式、矛盾式、可满足式的概念及判别方法；深刻理解闭式的概念及性质； 对于给定解释 I，会在解释 I 下解释公式并判断真假。 【教学重点与难点】 1、教学重点： 给定命题符号化、一阶逻辑公式的解释与判断。 2、教学难点：谓词公式类型的判别。 【教学内容】 4.1 一阶逻辑命题符号化 4.2 一阶逻辑公式及其解释 第五章 一阶逻辑等值演算与推理（1 学时） 【教学目标与要求】 1、教学目标： 本章要学会利用一阶逻辑等值式、置换规则，会进行一阶逻辑演算，求 一阶逻辑前束范式，知道在自然推理系统中的推理规则，并能进行有效推理的证 明。 2、教学要求： 深刻理解一阶逻辑等值式的定义；理解二足基本等值式的来源及意义，并会 熟练地使用这些等值式；熟练使用等值规则，能分别换名规则及代替规则；会求 一阶逻辑前束范式； 深刻理解自然推理系统的定义，牢记自然推理系统中各条 推理规则，正确使用 、 、 和 和 规则；能正确地给出有效推理的证明。 【教学重点与难点】 1、教学重点：有效推理证明方法。 2、教学难点：有效推理的证明。 【教学内容】 5.1 一阶逻辑等值式与置换规则 5.2 一阶逻辑前束范式 5.3 一阶逻辑的推理理论 实验目的与要求：（实验 2 学时） 加深对命题推理逻辑方法的理解，要求会用计算机对命题逻辑公式化简，会 用命题逻辑推理的方法解决逻辑推理问题，要求用 MATLAB 或 C 语言实现
实验内容：1、命题逻辑公式的化简2、命题逻辑推理【思政元素融入点】马克思主义唯物论与辩证论：寻找各种事物发展变化的基本规律，在人类自身思维认知过程中发现新事实、新原理、新规律，体会马克思主义辩证唯物主义与历史唯物主义世界观与方法论。逻辑联结词演算规则体现事物之间的联系性、数理逻辑部分在人工智能方面专家系统的直接应用体现了认识的本质、实践与认知的辩证原理。第二部分集合论（8学时）第六、七章集合代数（5学时）【教学目标与要求】1、教学目标：集合论是现代各学科的基础。第六章介绍集合论的基础知识，要求熟悉集合的概念、性质及其运算，在此基础上学习二元关系，第七章研究集合内元素之间的关系和集合之间元素的关系，要求领会关系的概念、性质、各种运算，以及会使用关系图、关系矩阵解决相关问题2、教学要求：深刻理解集合的概念，特别是注意与初级集合的区分；会进行初级并、交运算，深刻理解广义并、交；理解并掌握集合的恒等式并会应用；理解有序对、二元关系、集合A到BI的关系、集合A上关系的定义；熟练掌握关系的表达式、关系矩阵、关系图的表示法；熟练掌握关系的定义域、值域、逆、右复合的计算方法：熟练掌握判断关系五种性质的方法，利用数学简单原理解决数学问题：掌握求关系的自反、对称、传递闭包的方法；理解等价关系的概念，会判断一个关系是否是等价关系、明确等价关系与划分之间的一一对应关系；熟练掌握偏序关系、偏序集、哈斯图、偏序集中特殊元素的确定等。【教学重点与难点】1、教学重点：集合恒等式的应用；关系的性质、等价关系偏序关系定义与性质。2、教学难点：包含排斥原理；等价关系与划分之间的关系、偏序集中特殊
实验内容： 1、命题逻辑公式的化简 2、命题逻辑推理 【思政元素融入点】 马克思主义唯物论与辩证论：寻找各种事物发展变化的基本规律，在人类自 身思维认知过程中发现新事实、新原理、新规律，体会马克思主义辩证唯物主义 与历史唯物主义世界观与方法论。逻辑联结词演算规则体现事物之间的联系性、 数理逻辑部分在人工智能方面专家系统的直接应用体现了认识的本质、实践与认 知的辩证原理。 第二部分 集合论（8 学时） 第六、七章 集合代数（5 学时） 【教学目标与要求】 1、教学目标： 集合论是现代各学科的基础。第六章介绍集合论的基础知识，要求熟悉集合 的概念、性质及其运算，在此基础上学习二元关系，第七章研究集合内元素之间 的关系和集合之间元素的关系，要求领会关系的概念、性质、各种运算，以及会 使用关系图、关系矩阵解决相关问题。 2、教学要求： 深刻理解集合的概念，特别是注意与初级集合的区分；会进行初级并、交运 算，深刻理解广义并、交；理解并掌握集合的恒等式并会应用；理解有序对、二 元关系、集合 A 到 B\的关系、集合 A 上关系的定义；熟练掌握关系的表达式、 关系矩阵、关系图的表示法；熟练掌握关系的定义域、值域、逆、右复合的计算 方法；熟练掌握判断关系五种性质的方法，利用数学简单原理解决数学问题；掌 握求关系的自反、对称、传递闭包的方法；理解等价关系的概念，会判断一个关 系是否是等价关系、明确等价关系与划分之间的一一对应关系；熟练掌握偏序关 系、偏序集、哈斯图、偏序集中特殊元素的确定等。 【教学重点与难点】 1、教学重点：集合恒等式的应用；关系的性质、等价关系偏序关系定义与 性质。 2、教学难点：包含排斥原理；等价关系与划分之间的关系、 偏序集中特殊
元素的认定。【教学内容】6.1集合的基本概念6.2集合的运算6.3有穷集的计数6.4集合恒等式7.1有序对与笛卡儿积7.2二元关系7.3关系的运算7.4关系的性质7.5关系的闭包7.6等价关系与划分7.7偏序关系第八章函数（1学时）【教学目标与要求】1、教学目标：本章把函数做为集合上的一种特殊关系研究，介绍复合函数、反函数、双射函数的概念，引出集合的势、基数等概念，知道常用无限集合的基数及之间的关系。2、教学要求：理解函数的定义及性质；理解函数的复合与反函数定义及计算，会用双射证明集合元素的相同；了解自然数集与自然数集和的概念；了解集合的势与基数，明确常见集合的势；了解康托生平及集合论相关知识；【教学重点与难点】1、教学重点：双射方法证明集合元素相等；无限集合的势。2、教学难点：无穷集合势的理解。【教学内容】8.1函数的定义及性质8.2函数的复合与反函数8.3双射函数与集合的基数
元素的认定。 【教学内容】 6.1 集合的基本概念 6.2 集合的运算 6.3 有穷集的计数 6.4 集合恒等式 7.1 有序对与笛卡儿积 7.2 二元关系 7.3 关系的运算 7.4 关系的性质 7.5 关系的闭包 7.6 等价关系与划分 7.7 偏序关系 第八章 函数（1 学时） 【教学目标与要求】 1、教学目标： 本章把函数做为集合上的一种特殊关系研究，介绍复合函数、反函数、双射 函数的概念，引出集合的势、基数等概念，知道常用无限集合的基数及之间的关 系。 2、教学要求： 理解函数的定义及性质；理解函数的复合与反函数定义及计算，会用双射证 明集合元素的相同；了解自然数集与自然数集和的概念；了解集合的势与基数， 明确常见集合的势；了解康托生平及集合论相关知识； 【教学重点与难点】 1、教学重点： 双射方法证明集合元素相等；无限集合的势。 2、教学难点： 无穷集合势的理解。 【教学内容】 8.1 函数的定义及性质 8.2 函数的复合与反函数 8.3 双射函数与集合的基数
实验目的与要求：（实验2学时）学会用计算机求集合的交、并、补、差等运算，掌握二元关系在计算机上的表示方法，并会根据关系矩阵判断关系的各种性质。要求用MATLAB或C语言实现。实验内容：1、求集合的交、并、补、差2、判断关系的自反性与非自反性、对称性与非对称性、传递性等。【思政元素融入点】1、康托处理了数学上最棘手的对象---无穷集合，抛弃了一切经验和直观，强烈的使命感始终带给他以勇气和信心，他用坚定、乐观的信念无返顾地走向数学家之路并真正取得了成功。2、集合论二元关系抽象理论体现了联系的普遍性，性质不同的关系提下世界的多样性、条件性和多变性等等。3、等价关系、偏序关系在人工智能、数据挖掘领域的应用展现了理论与实践辩证关系，现实模型的很多关联性促使数学家提取关联性的本质一一关系；而关系理论的研究应用到实践中解决生活难题。第三部分图论（12学时）第九章图的基本概念（4学时）【教学目标与要求】1、教学目标：图的基本概念包括有向图、无向图、通路、回路、连通性等，是学习图论的基础。通过学习，要会使用图的代数表示、矩阵表示，解决图论的一些简单问题2、教学要求：理解图的相关概念，明确图的矩阵表示方法；会判断通路与回路、明确图的连通性的概念及性质，掌握握手定理；掌握图的矩阵表示的方法；了解图的运算【教学重点与难点】1、教学重点：图的连通性、握手定理
实验目的与要求：（实验 2 学时） 学会用计算机求集合的交、并、补、差等运算，掌握二元关系在计算机上的 表示方法，并会根据关系矩阵判断关系的各种性质。要求用 MATLAB 或 C 语言 实现。 实验内容： 1、求集合的交、并、补、差 2、判断关系的自反性与非自反性、对称性与非对称性、传递性等。 【思政元素融入点】 1、康托处理了数学上最棘手的对象-无穷集合，抛弃了一切经验和直观， 强烈的使命感始终带给他以勇气和信心，他用坚定、乐观的信念无返顾地走向数 学家之路并真正取得了成功。 2、集合论二元关系抽象理论体现了联系的普遍性，性质不同的关系提下世 界的多样性、条件性和多变性等等。 3、等价关系、偏序关系在人工智能、数据挖掘领域的应用展现了理论与实 践辩证关系，现实模型的很多关联性促使数学家提取关联性的本质——关系；而 关系理论的研究应用到实践中解决生活难题。 第三部分 图论（12 学时） 第九章 图的基本概念(4 学时) 【教学目标与要求】 1、教学目标： 图的基本概念包括有向图、无向图、通路、回路、连通性等，是学习图论的 基础。通过学习，要会使用图的代数表示、矩阵表示，解决图论的一些简单问题 。 2、教学要求： 理解图的相关概念，明确图的矩阵表示方法；会判断通路与回路、明确图的 连通性的概念及性质，掌握握手定理；掌握图的矩阵表示的方法；了解图的运算 。 【教学重点与难点】 1、教学重点： 图的连通性、握手定理
2、教学难点：图的连通性、握手定理【教学内容】9.1图9.2通路与回路9.3图的连通性9.4图的矩阵表示9.5图的运算第十章 树(2 学时)【教学目标与要求】1、教学目标：树是图论的重要内容，在计算机科学技术中有广泛的应用。通过学习本章，对树有基本的认识，理解最小生成树的含义及应用。2、教学要求：理解并掌握无向树的定义及性质；会求图的最小生成树；会求根树并了解其在计算机学科中的应用。【教学重点与难点】1、教学重点：树的定义、最小生成树的定义及性质。2、教学难点：求最小生成树。【教学内容】10.1无向树及其性质10.2生成树10.3根数及应用第十一章欧拉图与哈密顿图（2学时）【教学目标与要求】1、教学目标：欧拉图和哈密顿图是图论中的重要概念。通过学习本章，会认识欧拉图与哈密顿图，能解决生活中的一笔画问题和货郎的最短路问题。2、教学要求：
2、教学难点： 图的连通性、握手定理。 【教学内容】 9.1 图 9.2 通路与回路 9.3 图的连通性 9.4 图的矩阵表示 9.5 图的运算 第十章 树(2 学时) 【教学目标与要求】 1、教学目标： 树是图论的重要内容，在计算机科学技术中有广泛的应用。通过学习本 章，对树有基本的认识，理解最小生成树的含义及应用。 2、教学要求： 理解并掌握无向树的定义及性质；会求图的最小生成树；会求根树并了解其 在计算机学科中的应用。 【教学重点与难点】 1、教学重点：树的定义、最小生成树的定义及性质。 2、教学难点： 求最小生成树。 【教学内容】 10.1 无向树及其性质 10.2 生成树 10.3 根数及应用 第十一章 欧拉图与哈密顿图(2 学时) 【教学目标与要求】 1、教学目标： 欧拉图和哈密顿图是图论中的重要概念。通过学习本章，会认识欧拉图 与哈密顿图，能解决生活中的一笔画问题和货郎的最短路问题。 2、教学要求：
了解欧拉图的性质会判断一个图是否是欧拉图；了解哈密顿图的性质会判断一个图是否是哈密顿图：了解最短路问题与货郎担问题。【教学重点与难点】1、教学重点：欧拉图、哈密顿图的性质与判定。2、教学难点：欧拉图、哈密顿图的判定。【教学内容】11.1欧拉图11.2哈密顿图实验目的与要求：（实验4学时）学会用计算机解决图论问题的方法，会判断一个图是否是欧拉图，并能求出欧拉路，掌握求图的最小生成树的算法，会用计算机解决实际生活中的最短路问题。要求用MATLAB或C语言实现。实验内容：1、欧拉图的判断2、求最小生成树3、求最短路【思政元素融入点】1、大数学家欧拉欧拉为数学发展而奋斗的一生，其杰出的智慧，顽强的毅力，孜孜不倦的奋斗精神和高尚的科学道德，是永远值得学习的榜样。2、图论是展现理论联系实际的良好范本。图论在路线规划上的应用为社会节约能源用途意义深远，激发学生学好图论知识、扎实理论，为进一步深造和服务社会打好坚实的基础。3、汉密顿图以及欧拉图路线的寻找、二部图、图配色的一题多解性，渗透学生在遇到实际问题时应灵活处理问题，具体问题具体分析。表3课程实验教学一览表实验所需主要仪器必做/选是否为开放序号实验项目名称实验类型备注学时设备做实验2电脑1数理逻辑实验22电脑集合论实验32图论实验一电脑
了解欧拉图的性质会判断一个图是否是欧拉图；了解哈密顿图的性质会判断 一个图是否是哈密顿图；了解最短路问题与货郎担问题。 【教学重点与难点】 1、教学重点： 欧拉图、哈密顿图的性质与判定。 2、教学难点： 欧拉图、哈密顿图的判定。 【教学内容】 11.1 欧拉图 11.2 哈密顿图 实验目的与要求：（实验4学时） 学会用计算机解决图论问题的方法，会判断一个图是否是欧拉图，并能求出 欧拉路，掌握求图的最小生成树的算法，会用计算机解决实际生活中的最短路问 题。要求用MATLAB或C语言实现。 实验内容： 1、欧拉图的判断 2、求最小生成树 3、求最短路 【思政元素融入点】 1、大数学家欧拉欧拉为数学发展而奋斗的一生，其杰出的智慧，顽强的毅 力，孜孜不倦的奋斗精神和高尚的科学道德，是永远值得学习的榜样。 2、图论是展现理论联系实际的良好范本。图论在路线规划上的应用为社会 节约能源用途意义深远，激发学生学好图论知识、扎实理论，为进一步深造和服 务社会打好坚实的基础。 3、汉密顿图以及欧拉图路线的寻找、二部图、图配色的一题多解性，渗透 学生在遇到实际问题时应灵活处理问题，具体问题具体分析。 表3 课程实验教学一览表 序号 实验项目名称 实验 学时 实验类型 所需主要仪器 设备 必做/选 做 是否为开放 实验 备注 1 数理逻辑实验 2 电脑 2 集合论实验 2 电脑 3 图论实验一 2 电脑