图论及其应用

1、图论及其应用学时：40 学分：2课程属性：专业选修课 开课单位：理学院先修课程：高等代数 后续课程：无一、课程的性质图论及其应用是数学与应用数学专业的专业选修课程。二、教学目的通过教学，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。三、教学内容1. 图的基本概念2. 图的连通性3. 树的基本性质及其应用4. Euler Graphs and Hamilton Graphs with Applications 5. 平面图性质6. 匹配，求最大匹配算法及应用7. 图的染色及应用8. 极图理论四、学时分配章课程内

2、容学时1图的基本概念42图的连通性63树的基本性质及其应用64Euler Graphs and Hamilton Graphs with Applications 45平面图性质66匹配，求最大匹配算法及应用67图的染色及应用48极图理论4合计40五、教学方式本课程采用多媒体课堂讲授，结合实际范例深入浅出讲解讨论。六、考核方式本课程考核采用平时与期末考核相结合的办法，特别注重平时的考核，作业采用简单练习、论文等形式，期末考试采用简单考题或论文形式。七、教材及教学参考书参考教材：2 蒋长浩图论与网络流北京：中国林业出版社，2000参考书目：1 Bela BollobasModern Graph

3、Theory（现代图论，影印版）北京：科学出版社，20012 殷剑宏、吴开亚图论及其算法合肥：中国科学技术大学出版社，20033 谢金星、邢文训网络优化北京：清华大学出版社20004 程理民、吴江、张玉林运筹学模型与方法教程北京：清华大学出版社，20005 三味工作室SPSS V10.0 for Windows 实用基础教程北京：北京希望电子出版社 2001 孙魁明、张海彤Mathematica工具软件大全北京：中国铁道出版社，1994 楼顺天、于卫、闫华梁MATLAB程序设计语言西安：西安电子科技大学出版社，1997八、教学基本内容及要求第一章 图的基本概念1教学基本要求掌握的图的基本概念、

4、特殊图概念，了解最短路问题。2教学具体内容图的基本概念，路和圈，最短路问题。重点：图的概念；难点：最短路问题。第二章 图的连通性1教学基本要求掌握割点、桥、块、连通度等概念，并了解连通图的基本特征。2教学具体内容割点、桥和块，连通图。重点：连通度、连通图等；难点：连通图的特征描述。第三章 树的基本性质及其应用1教学基本要求掌握树的基本性质、Cayley公式等，了解连线问题、图的无圈子图分解等。2教学具体内容树的基本性质，Cayley公式，连线问题，图的无圈子图分解。重点：树的基本性质；难点：连线问题及无圈子图分解。第四章 Euler Graphs and Hamilton Graphs wit

5、h Applications 1教学基本要求掌握Euler图、Hamilton图等概念，了解中国邮递员问题。2教学具体内容Euler图，Hamilton图，中国邮递员问题。重点：Euler图、Hamilton图；难点：应用。第五章 平面图性质1教学基本要求掌握Euler公式，了解平面图特征、不可平面图特征。2教学具体内容Euler公式，平面图特征，不可平面图。重点：Euler公式、平面图特征；难点：平面图特征、不可平面图。第六章 匹配，求最大匹配算法及应用1教学基本要求掌握匹配、最大匹配、覆盖等概念，掌握最大匹配算法及应用。2教学具体内容匹配，最大匹配的算法，覆盖，图的支配集。重点：匹配、最大匹配；难点：最大匹配算法。第七章 图的染色及应用1教学基本要求掌握顶点染色、边染色、面染色等概念，并能简单应用。2教学具体内容顶点染色，边染色，面染色。重点：顶点染色；难点：应用。第八章