《图与网络优化》教学大纲.doc

《图与网络优化》教学大纲 大纲说明 课程代码：4935071 总学时：48学时 总学分：3学分 开课对象：数学与应用数学专业 一、课程的性质、目的、任务： 《图与网络优化》是数学与应用数学专业的一门重要的应用性专业课程。图论是研究图的组合关系及结构的一个数学分支。图论在物理，化学，计算机科学，通讯科学，电气工程等学科有着广泛的应用。图论的发展与计算机技术和电子技术的发展密切相关。图论的各种思想和方法是进行网络优化的基础。 通过本课程的学习,使学生理解图与网络的基本概念和基本理论，掌握如何把实际问题转化为图论和网络问题来解决的数学技术，熟练地应用图和网络的基本算法来解决相关的实际问题。 学习本课程的大部分内容只需要初等数学、线性代数等基本数学知识。 二、课程教学的基本要求： 通过本课程的学习，要求学生掌握图和网络的基本概念和基本理论，包括图的基本概念、树及其应用、匹配及其应用、平面图及其应用、欧拉图和哈密顿图、有向图及其应用、网络及其应用，能够初步掌握图和网络中证明的方法和技巧，会使用至少一门计算机编程语言实现图的常用算法，初步运用所学的知识解决计算机中遇到一些实际问题。 三、教学方法和教学手段的建议： 该课程系统讲述图和网络的基本概念，基本理论，方法和算法。课内教学主要采用讲授和讨论相结合的教学方式，并辅以必要的教学辅助活动；另外，安排必要的时间进行上机编程，实现一些常用的算法。平时还应适当的给学生布置一些综合性较强的大作业作为训练。 四、大纲的使用说明： 本课程采用教材可参考如下：卢开澄、卢华明的《图论及其应用》（清华大学出版社） 大纲正文 第一章 图的基本概念 　　　　　 学时：4学时 本章讲授要点：与图相关的一些问题、图的基本概念、道路与回路、图的矩阵表示法、中国邮路问题、平面图、Petri网 重点：图的基本定义及其相关概念，图的表示，一些与图相关的实际问题 难点：图的表示及其数据结构，实际问题和图的关联 教学内容： §1.1 引论 §1.2 图的基本概念 §1.3 道路与回路 §1.4 图的矩阵表示法 §1.5 中国邮路问题 §1.6 平面图 §1.7 Petri网 习题：第一章习题及适当补充 第二章 树　　　　　　　　　 学时：6学时 本章讲授要点：树的概念及基本性质、关联矩阵与基本关联矩阵、回路矩阵与基本回路矩阵、割集矩阵与基本割集矩阵、树的计数，内向树外向树和Huffman树和有哪些信誉好的足球投注网站树等； 重点：有关树的一些内在结构的矩阵描述，树的算法； 难点：有关树的一些内在结构的矩阵描述，树的算法； 教学内容： §2.1树的概念 §2.2基本性质 §2.3关联矩阵和基本关联矩阵 §2.4回路矩阵和基本回路矩阵 §2.5关联矩阵和回路矩阵的关系 §2.6割集矩阵和基本割集矩阵 §2.7树的数目 §2.8内向树与外向树 §2.9二元树 §2.10 Huffman树 §2.11有哪些信誉好的足球投注网站树 §2.12流动商人问题与分支定界法 §2.13最佳匹配问题 习题：第二章习题及适当补充 第三章 图的算法　　　　　　　 学时: 8学时 本章讲授要点：图的一些常用算法：最佳路径算法、最短树算法、任意两点间的最短路算法、图的连通性判别、树的生成、DFS算法图的划分、强连通块的划分 重点：掌握图的一些基本算法，并能编程实现； 难点：掌握图的一些基本算法，并能编程实现； 教学内容： §3.1最佳路径问题及其算法 §3.2最短树问题及其算法 §3.3任意两点间的最短路及其算法 §3.4图的连通性判断 §3.5树的生成 §3.6 DFS算法 §3.7图的块划分 §3.8强连通块的划分 习题：第三章习题及适当的补充； 第四章 网络流图问题　　　　 学时: 6学时 本章讲授要点：网络流图问题与最大流、最小切割定理，最大流的标号算法及修正的标号算法 重点：网络流图、最大流.最小割切定理、标号算法 难点：网络流图、最大流.最小割切定理、标号算法 教学内客： §6.1网络流图与最大流 §6.2割切 §6.3 Ford-Fulkerson最大流.最小割切定理 §6.4标号算法 §6.5 Edmonds-Karp修正算法，Dinic算法及其它 §6.6开关网络简介 习题：第六章习题及适当的补充； 第五章 匹配理论、色数问题及其它　　　　　 学时: 12学时 本章讲授要点：匹配理论、色数理论及其算法 重点：最大匹配、匈牙利算法、最