图论及其应用(精).doc

图论及其应用(精) 图论及其应用(精) PAGE / NUMPAGES 图论及其应用(精) 图论及其应用 学时 ：40 学分： 2 课程属性： 专业选修课 开课单位： 理学院 先修课程： 高等代数 后续课程： 无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教课目标 经过教课，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应 用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。 三、教课内容 图的基本观点 图的连通性 树的基天性质及其应用 Euler Graphs and Hamilton Graphs with Applications 平面图性质 般配，求最大般配算法及应用 图的染色及应用 极图理论 四、学时分派 章 课程内容 学时 1 图的基本观点 4 2 图的连通性 6 3 树的基天性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 般配，求最大般配算法及应用 6 7 图的染色及应用 4 8 极图理论 4 共计 40 五、教课方式 本课程采纳多媒体讲堂解说，联合实质典范深入浅出解说议论。 六、查核方式 本课程查核采纳平常与期末查核相联合的方法，特别着重平常的查核，作业采纳简单练习、论 文等形式，期末考试采纳简单考题或论文形式。 七、教材及教课参照书 参照教材： J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. 蒋长浩．图论与网络流．北京：中国林业第一版社，2000． 参照书目： [1] Bela Bollobas ．Modern Graph Theory （现代图论，影印版） ．北京：科学第一版社， 2001 ． [2] 殷剑宏、吴开亚．图论及其算法．合肥：中国科学技术大学第一版社， 2003． [3] 谢金星、邢文训．网络优化．北京：清华大学第一版社． 2000． [4] 程理民、吴江、张玉林．运筹学模型与方法教程．北京：清华大学第一版社， 2000． [5] 三味工作室． SPSS V10.0 for Windows 适用基础教程．北京：北京希望电子第一版社 2001． [ ６] 孙魁明、张海彤． Mathematica 工具软件大全．北京：中国铁道第一版社， 1994． [ ７] 楼顺天、 于卫、 闫华梁． MATLAB 程序设计语言． 西安：西安电子科技大学第一版社， 1997． 八、教课基本内容及要求 第一章 图的基本观点 1．教课基本要求 掌握的图的基本观点、特别图观点，认识最短路问题。 2． 教课详细内容 图的基本观点，路和圈，最短路问题。 要点：图的观点；难点：最短路问题。 第二章 图的连通性 1．教课基本要求 掌握割点、桥、块、连通度等观点，并认识连通图的基本特点。 2．教课详细内容 割点、桥和块，连通图。 要点：连通度、连通图等；难点：连通图的特点描绘。 第三章 树的基天性质及其应用 1．教课基本要求 掌握树的基天性质、 Cayley 公式等，认识连线问题、图的无圈子图分解等。 2．教课详细内容 树的基天性质， Cayley 公式，连线问题，图的无圈子图分解。 要点：树的基天性质；难点：连线问题及无圈子图分解。 第四章 Euler Graphs and Hamilton Graphs with Applications 1．教课基本要求 掌握 Euler 图、 Hamilton 图等观点，认识中国邮递员问题。 2．教课详细内容 Euler 图， Hamilton 图，中国邮递员问题。 要点： Euler 图、 Hamilton 图；难点：应用。 第五章 平面图性质 1．教课基本要求 掌握 Euler 公式，认识平面图特点、不行平面图特点。 2．教课详细内容 Euler 公式，平面图特点，不行平面图。 要点： Euler 公式、平面图特点；难点：平面图特点、不行平面图。 第六章 般配，求最大般配算法及应用 1．教课基本要求 掌握般配、最大般配、覆盖等观点，掌握最大般配算法及应用。 2．教课详细内容 般配，最大般配的算法，覆盖，图的支配集。 要点：般配、最大般配；难点：最大般配算法。 第七章 图的染色及应用 1．教课基本要求 掌握极点染色、边染色、面染色等观点，并能简单应用。 2．教课详细内容 极点染色，边染色，面染色。 要点：极点染色；难点：应用。 第八章 极图理论 1．教课基本要求 掌握 Ramsey数观点及应用。 2．教课详细内容 Ramsey数观点及应用，广义 Ramsey数。 要点： R