《图论》课程教学大纲

PAGE图论课程教学大纲（GraphTheory）学时数：48其中：实验学时：0课外学时：0学分数：3适用专业：数学与应用数学一、课程的性质、目的和任务图论是数学与应用数学专业的一门选修课程。开这门课程的目的是让学生掌握图论的一些基本知识，并了解其在计算机科学中的作用。通过本课程的学习，可开阔学生的视野，培养学生应用数学知识解决实际问题的能力。二、课程教学的基本要求（一）图的基本概念1．理解图、有向图的概念，2．掌握顶点的度，掌握图的运算,3．理解完全图、二分图，熟练掌握图的矩阵表示。（二）图的连通性1．掌握路与回路、有向途经,2．理解悬挂点，3．掌握连通图的概念与判别法则，掌握连通度、顶点割与边割,掌握k连通图的判别法则，掌握最短路问题，4．掌握Dijkstra算法。（三）树1．理解树的概念，2．掌握生成树与最优生成树，3．掌握Kruskal算法，理解树形图，4．掌握最优二元树，了解Huffman算法。（四）Euler环游与Hamilton回路1．理解Euler环游，2．掌握Euler图与Fleury算法，3．了解中国邮路问题，4．掌握Hamilton图与判别法则，了解旅行售货员问题。（五）图的对集与独立集1．理解对集、最大对集，掌握完美对集、二分图的对集，2．掌握二分图最大对集算法，理解最优分派问题，3．了解Kuhn-Munkres算法，理解独立集与覆盖，了解Ramsey数。三、课程的教学内容、重点和难点第一章图的基本概念一、图的定义二、顶点的度三、子图与图的运算四、一些特殊的图五、图的矩阵表示重点：顶点的度，图的运算，图的矩阵表示。难点：顶点的度。第二章图的连通性一、路与回路二、连通图三、连通度四、最短路问题重点：连通度，最短路问题。难点：连通度。第三章树一、树的基本性质二、生成树三、最优生成树四、树形图重点：最优生成树，树形图。难点：最优生成树。第四章Euler环游与Hamilton回路一、Euler环游二、中国邮路问题三、Hamilton图四、旅行售货员问题重点：Euler环游，Hamilton图。难点：Hamilton图。第五章图的对集与独立集一、二分图二、对集三、二分图的对集四、二分图最大对集算法五、二分图的最大最小对集六、最优分派问题七、独立集与覆盖八、Ramsey数重点：二分图的对集，最大对集算法。难点：独立集与覆盖，Ramsey数。四、课程各教学环节要求（一）本课程以课堂教学为主，其中新内容讲授40课时，习题课8课时。（二）作业量48左右。（三）考试采取闭卷考试方式。五、学时分配教学内容各教学环节学时分配作业题量备注章节主要内容讲授实验讨论习题课外其它小计一图的基本概念5168二图的连通性821010三树71810四Euler环游与Hamilton回路1021210五图的对集与独立集1021210合计4084848六、课程与其它课程的联系图论是数学与应用数学专业的一门选修课程，它与高等代数，组合论有紧密联系，同时又在计算机科学中有重要应用。七、教材与教学参考书（一）教材卜月华等。图论及其应用。南京：东南大学出版社，2007年。（二）教学参考书[1]田丰，马仲蕃。图与网络流理论。北京：科学出版社，1987